SRM 721, D1, 250Pointer (RememberWords)
James S. Plank
Sat Sep 30 16:58:34 EDT 2017
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 (34566) 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}1, max_{1}]
and [min_{2}1, max_{2}], then it's possible. Otherwise, it is
not. So, your strategy is:
 Determine
min_{1},
max_{1},
min_{2} and
max_{2}.
 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+d1) is greater than or equal to w. That value
is (d (d1))/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 + (x1) + ... + (xd+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 + (x1) + ... + (xd+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_{1} = 3, and min_{2} = 5.
 Example 1: min_{1} = 3, and min_{2} = 5.
 Example 2: min_{1} = 99, and min_{2} = 98.
 Example 3: min_{1} = 0, and min_{2} = 2.
 Example 4: min_{1} = 1, and min_{2} = 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_{1} = 4, and max_{2} = 7.
 Example 1: max_{1} = 3, and max_{2} = 5.
 Example 2: max_{1} = 101, and max_{2} = 102.
 Example 3: max_{1} = 0, and max_{2} = 2.
 Example 4: max_{1} = 44720, and max_{2} = 44720.
 Step 3: Determine if there is the proper overlap, and you're done!