SRM 721, D1, 250-Pointer (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,
and a number of words,
you can calculate two values:
For example, suppose
di equals 5 and
wi equals 24. Then
mini equals 3 (3-4-5-6-6) and
maxi equals 6.
Now, convince yourself of this -- the number of words memorized on the first or last day can
be any number between
maxi. I'm not going to prove that formally, but if you put a gun to my head,
So, if there's any overlap in the two intervals: [min1-1, max1]
and [min2-1, max2], then it's possible. Otherwise, it is
not. So, your strategy is:
- mini -- the fewest number of words that can be memorized in a day.
- maxi -- the largest number of words that can be memorized in a day.
Now, to determine mini, you will be tempted to resort to algebra.
My guess is that this is where most coders had problems. I didn't bother.
mini 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
mini using algebra.
I used binary search -- it's guaranteed to converge in 32 iterations, and I know the answer's
- Determine if there is overlap in those intervals, and return "Possible" or "Impossible."
maxi 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 maxi using
I'm going to let you do this one yourself, with no solution. To help you, here are the
- 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 mini. 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: min1 = 3, and min2 = 5.
- Example 1: min1 = 3, and min2 = 5.
- Example 2: min1 = 99, and min2 = 98.
- Example 3: min1 = 0, and min2 = 2.
- Example 4: min1 = 1, and min2 = 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 maxi. 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: max1 = 4, and max2 = 7.
- Example 1: max1 = 3, and max2 = 5.
- Example 2: max1 = 101, and max2 = 102.
- Example 3: max1 = 0, and max2 = 2.
- Example 4: max1 = 44720, and max2 = 44720.
- Step 3: Determine if there is the proper overlap, and you're done!