Codechef July 2013 Prob: the ultimate troll question

First, I had no idea how to solve this at all. There is no way to brute force it for such extremely large numbers.

Then, I saw this comment:

sikander_nsit @ 10 Jul 2013 09:58 PM

I was trolled by this question in two phases : First after solving for two hours I was like "oh man, awesome question. So one part of the question remains" then after 5 hours of PnC and probability, when I saw it I was like "mother of all trolls" serious mindfuck question.

I knew there had to be a shortcut somewhere. Hence, I worked out the first sample test case for t4=1. Yielded the result of 0.5. Could it be that the output is the same regardless of how many tickets Chef discards?

Investigating further, I made a program that calculates the probability of every single combination, a.k.a brute forcing the solution. Code here. Of course, I would only load the program with small inputs. The result:

Input:

	9
	2 2 1 0
	2 2 1 1
	2 2 1 2
	2 2 1 3
	2 3 4 0
	2 3 4 1
	2 3 4 2
	2 3 4 3
	2 3 4 4

view raw gistfile1.txt hosted with ❤ by GitHub

Output:

	0.5
	0.5
	0.5
	0.5
	0.4
	0.4
	0.4
	0.4
	0.4

view raw gistfile1.txt hosted with ❤ by GitHub

I found the shortcut! Indeed, the probability is the same regardless of how many tickets Chef discarded. Happily discarded T4 from my program, submitted it, only to get a runtime error. Turns out my stack has run out of space due to too many recursive calls from T3. Hmm, I thought, I could make the calculation non-recursive, but it is still up to 1000000000 calculations for a single test. Another shortcut must exist!

Went back to the question to look for more patterns. Discovered than 0.5 = 2/(2+2) for first sample test case, and 0.4 = 2/(2+3) for second test case. T3 is also not needed!

Submitted a program consisting of just these few lines:

	import sys
	T = int(sys.stdin.readline().strip())
	for t in range(T):
	t1,t2,t3,t4 = sys.stdin.readline().strip().split()
	t1,t2,t3,t4 = int(t1),int(t2),int(t3),int(t4)
	print t1 * 1.0 / (t1+t2)

view raw gistfile1.txt hosted with ❤ by GitHub

ANDDDDDDDDDDDDDDDDD


Ultimate troll question.