SRM 499, D2, 250-Pointer (SimpleGuess)

James S. Plank

Mon Aug 29 19:49:17 EDT 2016

Problem Statement.
A main() with the examples compiled in.
A skeleton that compiles with main.cpp.
Problem Given in Topcoder: March, 2011
Competitors who opened the problem: 1114
Competitors who submitted a solution: 1021
Number of correct solutions: 778
Accuracy (percentage correct vs those who opened): 69.83%
Average Correct Time: 16 minutes, 15 seconds.

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.

SRM 499, D2, 250-Pointer (SimpleGuess)

James S. Plank

My Solution.