SRM 499, D2, 250-Pointer (SimpleGuess)

James S. Plank

Mon Aug 29 19:49:17 EDT 2016
Sometimes, being effective more important than being smart. My guess is that many topcoders resorted to algebra and wrote buggy programs that involved doubles. There's a very simple solution that requires no algebra. Please read on:

When I first saw the problem, I thought -- seems like algebra. For each pair of hints, A and B, you can set up two equations to find X and Y. Then you'll have to make sure that X and Y are integers.

And then I thought -- look at the constraints. Since each hint is between 1 and 100, X has to be between 1 and 100, and Y has to be between 1 and X. So, let's just enumerate X and Y, and see if X+Y and X-Y are both in the hints. Keep track of the maximum value of X*Y that fits.

My main data structure was a set. I put each hint into the set. Then, I enumerated all X and Y, and looked up X+Y and X-Y in the set. If they were both there, I compared them to the best answer found so far, and then returned the best answer.

My Solution.