Topcoder problem analysis - Birds (CC 2002 REG Semi 500 pointer)

Problem statement

https://community.topcoder.com/stat?c=problem_statement&pm=330&rd=62

This is not a very hard problem once you figure out the right algorithm. I spent a lot of time chasing a solution after having misread the problem.
I assumed that a bird is migratory if it spends its time in two regions for 90 days or more each in any 365 day period, rather than just the specified start date to December 31st.

Lesson #1 : Read the problem statement carefully!

---

Subtask - Find the number of days between two dates in a year

The naive way to do this is to calculate it by summing up the months upto the current and adding the date.
Instead of doing this in a loop every time, we can precalculate this with partial_sum():

---

The algorithm itself

My solution was as follows:

• Put the locations in an array and sort by date.
• Find all pairs of locations the bird stays which are at least 1000 KM distant
• For every pair of locations say A and B, walk the array starting from A;
• Keep walking the array as long as every location is within 1000 KM of A and more than 1000 KM from B. Sum up the time spent along this sequence.
• The entries that were walked are all in the same region and we have the total time spent in that region.
• Repeat the same process vice versa starting from B
• Now we have the total time spent in both the regions, if both are > 90 days were have a migration!

The third step finds the longest time spent in any one region - there is a lot of redundant computation - For e.g. if we have ABCDEFG as locations, and G happens to be 1000 Km away from the rest, while all the others are close to each other, we will be walking from A to G, B to G, C to G and so on - but we don't care, since all that matters is that the time spent in some subset of [A to F] is 90 days and the stay in G itself is 90 days.

There is only one tricky detail - time spent at any location is given by t[d + 1] - t[d] - but obviously the last element of the locations array doesn't have a successor.
It's implicitly assumed that if a bird no longer moves, it stays where it was until December 31st.
So we put in a January 1st (next year or day 366) sentinel at the end of the locations array, so we have a way for the loop to be within bounds.

Perversely, the problem statement explicitly says the same is not the case for the beginning of the year - in other words, if a bird migrated on March 1st, you don't assume it lived at that location before that. I assumed the opposite the first time I read the problem and didn't figure it out until one system test case failed!

---

Final code


The code seems quite verbose, but the essence of the algorithm is only about 10 lines.
Note the simplicity of using FOR_EVERY_UNIQUE_PAIR()
Also notice the use of stoi() - C++11 onwards has string to numeric conversion functions and vice versa. The only alternative before that was istringstream or -- Dog forbid! -- the sprintf() family