SRM 739, D2, 250-Pointer (HungryCowsEasy)

James S. Plank

Wed Oct 10 13:23:37 EDT 2018
Latest revision: Thu Oct 8 10:15:02 EDT 2020

In case the topcoder servers are down

Here is a summary of the problem:

Examples

#  Cows           Barns              Answer
-  -------------  -----------------  ---------------
0 {0}             {-5, 5}            {0} -- The cow is equidistant to both barns, so return the smaller one.
1 {7, 7}          {7, 10000}         {0, 0} -- Both cows are already at their barn.
2 {2, 6, 0, 4, 8} {3, -1, 5, 1, 7}   {3, 2, 1, 0, 4 } -- Note that the neither vector has to be sorted.

Testing Yourself

This one has a standard testing methodology -- when you run tests.sh, your output should be identical to answers.txt.

Hints

With the Topcoder constraints being so low, you can perform a nested for() loop, and simply traverse the barns for each cow. However, let's instead use the correct data structure for the job -- a map.

Create a map for the barns. Each map entry contains the coordinate of a barn as its key, and the id of the barn as it's value. Since those coordinates can be pretty large (and small), I would have the keys be long long's, rather than integers.

Go ahead and sentinelize your map as well -- insert a gigantic value into the barn with a value of -1, and also a gigantic negative value. I created that value as follows:

  long long bignum = 1000000000;
  bignum *= 1000;

Now, for each cow, find the nearest barn whose value is greater than or equal to the cow's coordinate with lower_bound(). That lets you calculate the closest barn greater than or equal to the cow. Decrement that iterator, and that gives you the nearest barn whose value is less than the cow's value. The sentinels mean that you don't have to test whether the iterators are valid -- they are always valid!

What's the running time of this? O(n log(n)). That's the time that it takes to create the map, and it's also the time that it takes to calculate each cow's best barn (n cows, and each lower_bound() call is O(log(n))).