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.

My Solution

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

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.

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!

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