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, di, and a number of words, wi, you can calculate two values:
  1. mini -- the fewest number of words that can be memorized in a day.
  2. maxi -- the largest number of words that can be memorized in a day.
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 mini and maxi. 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: [min1-1, max1] and [min2-1, max2], then it's possible. Otherwise, it is not. So, your strategy is: 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 right.

Similarly, 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 binary search.

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