SRM 728, D1, 250-Pointer (Halving)

James S. Plank

Tue Nov 12 17:30:55 EST 2019

Problem Statement.
A main() with the examples compiled in.
A skeleton that compiles with main.cpp.
Problem Given in Topcoder: January, 2018
Competitors who opened the problem: 226
Competitors who submitted a solution: 209
Number of correct solutions: 164
Accuracy (percentage correct vs those who opened): 72.6%
Average Correct Time: 20 minutes, 29 seconds.

In case Topcoder's servers are down

Here is a summary of the problem:

You are given a collection of sticks with integer lengths between 1 and 10⁹.
Your goal is to break each stick, potentially zero times or potentially multiple times, so that each stick ends up being the same length.
When you break a stick whose length is even, you get two sticks that are the same length. Keep one and discard the other.
When you break a stick whose length is odd, you get two sticks whose lengths differ by one. Keep one and discard the other.
Return the minimum number of total breaks that it takes to make each stick the same length.
The topcoder constraints has the number of sticks between 2 and 50. I'm going to bump that up to 10,000.

Examples

Example 0: { 11, 4 }. Answer = 3 (Break 11 to 5, break 5 to 2, break 4 to 2)
Example 1: { 1000000000, 1000000000, 1000000000, 1000000000 }. Answer = 0 (they are all the same size already)
Example 2: { 1, 2, 3, 4, 5, 6 }. Answer = 10
Example 3: { 13, 13, 7, 11, 13, 11 }. Answer = 11
Example 4: { 1, 1 }. Answer = 0

The driver in main.cpp has the examples compiled in, and if you enter "-" as a command line argument, you can read the values of the stick lengths on standard input.

Testing yourself

Like the Cryptography Problem, I have a shell script tests.sh, that you can use to test your program. When you run tests.sh, your answer should be identical to answers.txt. Mine runs in about 2.5 seconds.

Observation #1

Let's suppose we have one of these stick lengths. Call it s. How many different lengths can it create? I'm going to propose that the answer is under 100. Think about it -- suppose that s is roughly 2³⁰. Then, when you halve it, you're going to get one or two numbers that are around 2²⁹. Suppose you now have two numbers from halving. When you halve them, you are only going to get two more distinct numbers. There won't be more than a few distinct numbers for each round of halving. For example:


17 -> 8   -> 4   -> 2   -> 1   -> 1
   -> 9   -> 5   -> 3   -> 2

You can get more than two per round, but it won't be by much. To verify this, I wrote a quick and dirty program that calculated how many lengths were generated by each s from 1 to 100,000. The maximum value was 33. That's a proof by cosmo, but I'll take it.

Strategy

Given this observation, your strategy should be straightforward:

You are going to maintain two maps over the course of this program. Both will have integer keys and vals.
1. canbreak is keyed on stick lengths, and its val is the number of original sticks that can achieve the length by being broken 0 or more times.
2. numbreaks is also keyed on stick lengths, and its val contains the total number of breaks that it takes to break each stick to this length.
Your answer is going to be the stick length where canbreak is equal to the number of sticks (meaning each stack may be broken to this length), and numbreaks is minimized.

Let's go over example zero to illustrate. Sticks 11 and 4 may be broken as follows, which will generate the two maps canbreak and numbreaks:

   Stick 11          Stick 4        canbreak       numbreaks
--------------    --------------    ---------      ---------
Length  Breaks    Length  Breaks    Key   Val      Key   Val 
  11       0         4       0       11     1       11     0
   6       1         2       1        6     1        6     1
   5       1         1       2        5     1        5     1
   3       2                          4     1        4     0
   2       2                          3     1        3     2
   1       3                          2     2        2     3
                                      1     2        1     5

As you can see, the only stick lengths where canbreak is equal to the number of sticks are 2 and 1. Of these, the length with the minimum value of numbreaks is 2, whose val is 3, so the answer is 3.

A recursive procedure to call on each stick length

I wrote a recursive procedure with the following prototype:

void all_breaks(int length, int breaks, map <int, int> &breakmap);

For each stick length len in the input array, I called all_breaks(len, 0, m), where m was an empty map.

What all_breaks() does is check to see if the length is in the map. If it is, and if its val is less than or equal to breaks, then all_breaks() returns. That's its base case.

If it doesn't return, then it either adds length to the map with a val of breaks, or it updates length's entry in the map to equal breaks. Then, if length is greater than one, it calls itself recursively on the two values that you get when you break length. (You'll note that if length is even, it gets two of the same lengths, but you don't really need to test for this -- if you make the same recursive call twice, it will return instantly on the second one, because the first one has put the length into the map.).

When all_breaks(len, 0, m) returns, the map m will contain all of the information that you need to update canbreak and numbreaks.

If the recursion is confusing to you -- here's what happens when you call all_breaks(11, 0, {}):

all_breaks(11, 0, {}) puts [11,0] into the map and then calls all_breaks recursively on 5 and 6.
  all_breaks(5, 1, {[11,0]}) puts [5,1] into the map and then calls all_breaks recursively on 2 and 3.
    all_breaks(2, 2, {[5,1],[11,0]}) puts [2,2] into the map and then calls all_breaks recursively on 1 and 1.
      all_breaks(1, 3, {[2,2],[5,1],[11,0]}) puts [1,3] into the map and returns.
      all_breaks(1, 3, {[1,3],[2,2],[5,1],[11,0]}) returns because 1 is in the map.
    all_breaks(2, 2, ..) returns
    all_breaks(3, 2, {[1,3],[2,2],[5,1],[11,0]}) puts [3,2] into the map and then calls all_breaks recursively on 2 and 1.
      all_breaks(2, 3, {[1,3],[2,2],[3,2],[5,1],[11,0]}) returns, because 2 is in the map with a smaller value.
      all_breaks(1, 3, {[1,3],[2,2],[3,2],[5,1],[11,0]}) returns, because 1 is in the map with the same value.
    all_breaks(3, 2, ..) returns
  all_breaks(5, 1, ..) returns
  all_breaks(6, 1, {[1,3],[2,2],[3,2],[5,1],[11,0]}) puts [6,1] into the map and then calls all_breaks recursively on 3 and 3.
    all_breaks(3, 2, {[1,3],[2,2],[3,2],[5,1],[6,1],[11,0]}) returns, because 3 is in the map with the same value.
    all_breaks(3, 2, {[1,3],[2,2],[3,2],[5,1],[6,1],[11,0]}) returns for ibid.
  all_breaks(6, 1, ..) returns
all_breaks(11, 0, ..) returns

The final map is {[1,3],[2,2],[3,2],[5,1],[6,1],[11,0]}.  You'll note how it matchs the "stick 11" table above.

Putting the pieces together

I would start by writing all_breaks() and testing it by printing it out -- you can see the resulting maps for 11 and 4 above. For 1000000000, the map is in the file big.txt. You'll note that there are 50 elements in the map.

After you are sure you have written all_breaks() correctly, go ahead and finish the program.

Running time

Calculating this one's running time is a pain to do in detail. However, with the maximum stick length capped at 10, this means that the maximum size of breakmap will be roughly 40. That allows us to saly that all_breaks() will run in O(1) time. If the number of sticks is n, the size of canbreak and minbreaks will be capped at 40n, which is O(n).

This means that the running time is n times the sum of:

Calling all_breaks(), which is O(1).
Updating canbreak and minbreaks after calling all_breaks(). That is O(log n).

So this is O(n log n).