### 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:
• Determine min1, max1, min2 and max2.
• Determine if there is overlap in those intervals, and return "Possible" or "Impossible."
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:
• 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!