SRM 706, D2, 500-Pointer (SellingFruits)

James S. Plank

Sun Jan 29 10:47:03 EST 2017

In case Topcoder's servers are down

Here is a summary of the problem:

The examples

Example x f d p Answer
0 3 5 100 10 11
1 2 17 20 1 10
2 1 97 98 1 97
3 16 4 8 2 0
4 17 1 2000000000 4 95238095
5 1 1996245611 1999990159 123 1996275808
6 15000000 100 2000000000 1 133
7 1 1000000000 2000000000 1000000000 1000000000

Testing yourself

Like the Cryptography Problem, I have a shell script tests.sh, that you can use to test your program. When you run tests.sh, your answer should be identical to answers.txt

Hints

This is a typical frustrating Topcoder problem -- it seems so simple, but there are pitfalls out there that will trip you up. I'm going to give you two pieces of advice, before I give you some time to work this out on your own:
  1. Don't use integers for anything -- use long long's. When Topcoder puts constraints at the 2,000,000,000 mark, they're doing it so that you'll hit overflow with integers if you're not super-careful. So don't use integers.
  2. Beware of trying to use math that will end up with floating point, when all of the equations involve integers. I know there is a huge temptation to use algebra to solve this problem. While you might get it right, I'll put money that you'll get it wrong multiple times before you get it right. So try something easier on the brain. BTW, when I solve these problems, I don't use any floating point operations.
Give this one some time on your own. If you find yourself struggling, read the hints below.































Binary Search

There are two different binary searches you can do on this problem. I'll frame them as procedures you can write. In each of these, I assume that you store the method's parameters in the class:
  1. long long days_if_i_buy_b_fruit(long long b); This returns how many days that you will life if you buy b pieces of fruit. This function will increase to a maximum value and then decrease, so a binary search is plausible here. I'd worry about about duplicate values, myself, but it's a thought.

  2. bool can_i_live_y_days(long long y); This returns whether or not you can live y days. Clearly, here there will be a maximum value of y for which this is true. You want to find that maximum. I think that this is the easier of the two binary searches.

Is this the best solution?

Probably not. The proper way to solve this problem, when you're not doing a programming competition, is to (ha ha) use algebra, and get it right. That will be O(1).

However, this solution, which is O(log(f+d)) is plenty fast.