February 12

TopCoder – AttackOfTheClones

0  comments

Problem NameCompetitionDifficulty
AttackOfTheClonesSRM 678Medium

Analysis

Full source code is available here.

This problem is quite interesting!

It is immediately clear that the number of possible combinations is so high that the solution must use a sort of greedy algorithm. A brute force approach to identify all possible sequences is impractical.

However, if given a fixed number of weeks we can tell if at least one solution is possible in a reasonable time, a brute force approach on the weeks seems possible. The worst case scenario is when lastWeek is firstWeek in reverse order and in that case the solution is equal to the number of days in a week. That number, from the problem constrains, is a most 2500.

Here are some test cases, that include the worse case scenario I just mentioned.2016-02-11 23_10_19-Action center

My Solution

The skeleton of such algorithm is the following (please ignore lastWeekMap, we’ll come back to it later).

2016-02-11 23_12_20-Start

So then, how can we tell if a mission is possible in a fixed number of weeks?

My greedy intuition is the following. I try to use each shirt immediately after is ready to be used again. For every shirt I calculate the position that it would have after wearing that shirt for as many times as the current fixed weeks. If this final position happens to be before the actual final position and this is true for every shirt a solution to the problem must exist. I don’t have a proof of that, that was just my intuition that turned out to be true (at least it pass all TopCoder system tests).

This is the code that does that.

2016-02-11 23_21_28-Start

lastWeekMap contains the position of a shirt in the final week. I had to calculate that just once outside the IsMissionPossible method for performance reasons. Failing to do that would fail the worse case scenario exceeding the maximum allowed time. Unfortunately I had to learnt this the hard way during the competition because I didn’t have enough time to refactor the code to extract this. It is very annoying to do that 30 seconds after the competition ended!

Anyway, forget this…

A better solution

Amazingly, you can solve this problem with just a single line code!

2016-02-11 23_34_36-Action center

Oh my god, really?

The key idea is to notice that the day position of a shirt can only decrease by one in the next week and can always increase. As an example, a shirt at day 6 in the first week can only be moved in day 5 or later in the second week.

The idea is to calculate how many day-left-moves a shirt need to do to arrive in final position and return the maximum value.

A proof of this is documented very well in the TopCoder SRM 678 Editorial so I am not going to repeat it here. I highly recommend you to have a look because it is a great proof.

It turned out that a greedy approach was not required. A perfect solution was possible!

Personal Notes

Some valuable lessons:

  • Intuition sometimes pay off. So “follow your gut” sometimes is good especially if you can’t find a more proved solution
  • Think about the worse case scenario to identify possible performance problems
  • The SequenceEqual method can be useful in other problems

 


Tags


You may also like

The best way to stay up to date with C# 10 features

My Technical Journey from my first program to Lead Software Engineer

Top 10 C# Developer News from Microsoft Build 2020

Agile Estimation

{"email":"Email address invalid","url":"Website address invalid","required":"Required field missing"}

Subscribe to our newsletter now!

Get instant access to the Master C# 9 webinar to learn all the new exciting C# 9 features quickly.
Get regular videos and news on C# and .NET and offers on products and services to master C#.

We will collect, use and protect your data in accordance with our Privacy Policy.

>