SRM 706, D2, 500-Pointer (SellingFruits)

James S. Plank

Sun Jan 29 10:47:03 EST 2017
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. When I solve these problems, I don't use any floating point operations.
Give this one some time on your own, but try to leave 20 minutes or so to read what I've written below, because chances are that you won't solve this the way that I'm solving it, and you should take a look at the way I have solved it.

If the constraints weren't so big, you could just enumerate the fruit that you buy.

The first thing that I did was copy the parameters to maxDays into long long variables in the class definition. For example, I added a variable X to the SellingFruits class, and the first thing that I did was copy x to X. I never used x again. I did the same thing for f, d and p.

Next, I wrote a new method inside the class called:

long long days_if_i_buy_b_fruit(long long b);

This calculates the number of days that I live if I buy b fruit. For example, in example 0:

When you write this, take care to handle illegal values of b (those that are negative, and those that are greater than D*P). You may need this feature later.

Once you have written days_if_i_buy_b_fruit(), you can simply try all potential values of b, from 0 up to the maximum that you can afford. Return the maximum number of days that you will live.

Go ahead and write this -- it will solve examples 0 through 3. It won't solve example 4, though, because the constraints are too big, and you are trying every fruit.

This is the point at which you may want to bust out some algebra, but resist that thought. Go ahead and print out each value of b and how many days that lets you live. Do this for example 0 (I'm doing it for you):

Fruit          Days
bought(b)      you live
------         --------
0               5
1               6
2               7
3               8
4               9
5              10
6              11
7              10
8               6
9               3
10              0
You'll note that the days you live increases to a maximum, and then decreases. You can use that fact to limit the values of b that you test.

What I did was the following. I tried every value of b that was a multiple of 10,000. Sure, for examples 0 through 3, the only value of b that fits that description is 0, but for example 4, I'm trying quite a few of them. The maximum number of fruit that I'll try, given the constraints, is 2,000,000,000 / 10,000, which is 200,000. So this part of my program will run fast enough (you get roughly 10,000,000 operations on topcoder).

So, go ahead determine the best value of b that is a multiple of 10,000. Call that b10K. You know that the actual best value of b will be between (B10K-10,000) and (B10K+10,000). You can test all of those with 20,000 calls to days_if_i_buy_b_fruit(long long b). That's also fast enough.

This approach lets you solve the problem quickly enough for topcoder, and you'll note that you don't use any floating point.

If you haven't solved the problem already, go ahead and try to solve it in this manner. I will email the TA's my solution, and they can show that solution (or theirs) to you at the end of the first part of lab.

Is this the best solution?

No -- far from it. That solution is O(D/P). 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).

Another fun way to solve this is to write a method called:

bool can_i_live_y_days(long long y);

Then, you can do a binary search on the number of days that you can live -- start with 0 (which you know you can do), and (F+D/P+1), which you know you can't do. Then use these to do a binary search. Now your running time is O(log(F+D/P)).