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

Problem Statement.
A main() with the examples compiled in.
A skeleton that compiles with main.cpp.
tests.sh MD5 hash: be4f5fb26b199befabb20d2c8a5e9c4e
answers.txt MD5 hash: 3be9a5188c4a2c83fd65f29c793b5811
Problem Given in Topcoder: October, 2018
Competitors who opened the problem: 166
Competitors who submitted a solution: 138
Number of correct solutions: 95
Accuracy (percentage correct vs those who opened): 57.2%
Average Correct Time: 18:55.

In case the topcoder servers are down

Here is a summary of the problem:

You are given the location of cows on the X-Axis. This is a vector of integers, where each integer is between -10⁹ and 10⁹.
You are also given the location of barns, which are also on the X-Axis. This is also a vector of integers, where each integer is between -10⁹ and 10⁹.
Each cow is going to go to its nearest barn. If two barns are equidistant from a cow, it will go to the one with the lower coordinate.
Barns may hold arbitrarily many cows.
Return a vector v of integers, where v[i] is the index (not the coordinate, but the index) in the barns vector of the barn to which cow i goes.
Although the Topcoder parameters say that each vector will have a maximum of 50 elements, my testing scripts have up to 10,000 elements for each.

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))).