**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

**365 day period, rather than just the specified start date to December 31st.**

*any*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

## No comments:

## Post a Comment