SRM 721, D1, 250-Pointer (RememberWords)

James S. Plank

Sat Sep 30 16:58:34 EDT 2017

Problem Statement.
A main() with the examples compiled in.
A skeleton that compiles with main.cpp.
Problem Given in Topcoder: September, 2017
Competitors who opened the problem: 266
Competitors who submitted a solution: 209
Number of correct solutions: 98
Accuracy (percentage correct vs those who opened): 36.8
Average Correct Time: 29 minutes, 58 seconds.

This problem takes a little logic and a little math. And, in my case, not too much math. I'm guessing that most of the programmers used too much math, and that's why more than 50 percent of the submissions were wrong. Given a number of days, d_i, and a number of words, w_i, you can calculate two values:

min_i -- the fewest number of words that can be memorized in a day.
max_i -- the largest number of words that can be memorized in a day.

For example, suppose d_i equals 5 and w_i equals 24. Then min_i equals 3 (3-4-5-6-6) and max_i equals 6. Now, convince yourself of this -- the number of words memorized on the first or last day can be any number between min_i and max_i. I'm not going to prove that formally, but if you put a gun to my head, I could. So, if there's any overlap in the two intervals: [min₁-1, max₁] and [min₂-1, max₂], then it's possible. Otherwise, it is not. So, your strategy is:

Determine min₁, max₁, min₂ and max₂.
Determine if there is overlap in those intervals, and return "Possible" or "Impossible."

Now, to determine min_i, you will be tempted to resort to algebra. My guess is that this is where most coders had problems. I didn't bother. min_i is going to be the smallest value of x such that x + (x+1) + ... + (x+d-1) is greater than or equal to w. That value is (d (d-1))/2 + dx. Perhaps you can determine min_i using algebra. I used binary search -- it's guaranteed to converge in 32 iterations, and I know the answer's right.

Similarly, max_i is going to be the largest value of x such that x + (x-1) + ... + (x-d+1) is less than or equal to w. Of course, in that sum, you can't have a negative term, so you have to calculate it differently for when x ≥ d and x < d. Once again, I determined max_i using binary search.

I'm going to let you do this one yourself, with no solution. To help you, here are the steps:

Step 1: Write a procedure with the following prototype:
long long findmin(long long d, long long w);
The job of this procedure is to return min_i. You should use binary search to write this: Start with low = 0 and high = w+1. Then iterate until high equals low+1. Calculate x, which is the average of high and low (truncated to an integer). Calculate x + (x-1) + ... + (x-d+1) and if it is greater than or equal to w, set high to x. Otherwise, set low to x. When you're done, return high.
Test yourself on the examples:
- Example 0: min₁ = 3, and min₂ = 5.
- Example 1: min₁ = 3, and min₂ = 5.
- Example 2: min₁ = 99, and min₂ = 98.
- Example 3: min₁ = 0, and min₂ = 2.
- Example 4: min₁ = 1, and min₂ = 1.
Step 2: Write a procedure with the following prototype:
long long findmax(long long d, long long w);
The job of this procedure is to return max_i. This is a similar binary search, but now you'll return low (and you have a different calculation).
Test yourself on the examples:
- Example 0: max₁ = 4, and max₂ = 7.
- Example 1: max₁ = 3, and max₂ = 5.
- Example 2: max₁ = 101, and max₂ = 102.
- Example 3: max₁ = 0, and max₂ = 2.
- Example 4: max₁ = 44720, and max₂ = 44720.
Step 3: Determine if there is the proper overlap, and you're done!