Whoa, that was a tough problem. Ironically it’s called Qualification Round:
You’ve just advanced from the Qualification Round of Google Code Jam Africa 2010, and you want to know how many of your fellow contestants advanced with you. To give yourself a challenge, you’ve decided only to look at how many people solved each problem.
The Qualification Round consisted of P problems; the ith problem was fully solved by Si contestants. Contestants had to solve C problems in order to advance to the next round. Your job is to figure out, using only that information, the maximum number of contestants who could have advanced.
Well, at first it seems pretty simple, but there is quite some math involved. The first case of the example input is easy to solve, but the second will most likely get you scratching your head thinking “where the #$%* that number came from” (at least I did). 🙂 Well the secret is that you should not look at the inputs as they are, but instead, find the maximum amount of solved problem combinations there are.
I studied a bit but still could not solve it, and surrendered by checking the contest analysis. It was quite complicated to understand, until they wrote about a clever solution from the winning candidate: it consisted in lowering the possible scores to max at the division of the scores by the amount of needed problems. Just do it (don’t ask why) until there are no scores over the result of that division. That same result will be the answer. Creepy! Python code time:
for case in range(1,int(raw_input())+1): # For all test cases info = map(int, raw_input().split(" ")) # Get test case information problems = info # Fetch number of problems needed = info # Fetch number of needed problems to pass results = info[2:] # Fetch results for each problem qualified = 0 # Initialize our results if (problems == needed): # For this case, we can expect results.sort() # as many contestants as the qualified = results[len(results)-needed] # least solved problem else: # For this case, we use a solution out = False # similar to the winning one while not out: out = True qualified = sum(results)/needed # Reduce the number of possible qualifiers for i in range(len(results)): # And for all results if results[i] > qualified: # Limit their values to the current qualifiers results[i] = qualified out = False # Until they all "match" the qualifiers number print "Case #%d: %s" % (case, str(qualified)) # Report results
Interestingly enough, this code is smaller than the last, and solves a more complicated problem (at least in my opinion). I don’t think I could have done a better job on this one. 🙂 That’s the beauty in learning!