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:


Output:


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:



ANDDDDDDDDDDDDDDDDD


Ultimate troll question.

Codechef July 2013 Galactik

First, to find out where to build the bridges, I had to find out what islands/isolated pockets of planets are there. This can be done by a connected components algorithm, simple enough.

Next step, to choose which islands to build the teleporters on....I had no idea. Dug through the comments on the question page for hints. I found this big one:

qwaker00 @ 5 Jul 2013 07:19 PM

Can GFA create more than one teleport on a planet?

zwolf10003 @ 5 Jul 2013 07:59 PM

Please specify if GFA can construct more than one teleport ending on a planet.

jay_adm @ 5 Jul 2013 10:14 PM

@zwolf10003 ,@qwaker00: yes.

Hence, I could just build one end of all teleporters on the same planet. And of course, that planet would offer the cheapest rate in the galaxy for building one!

The other end would go to each individual island/component. And for each island, the best place to end the teleporter would be the cheapest planet in the island.

With the solution planned out I proceeded to code it out in Python. Code here. Worked perfectly, but when submitted:


Sigh.

Time for port over to C++ again. But before that, I made a search for the fastest I/O operation I can achieve on C++. I landed upon this blog post. Tried the last method, but found that Windows does not have getchar_unlocked(). Replaced it with getchar() instead.

The result:


It's accepted!

Codechef Jun 2013 Collect

Coded first in Python, time limit exceeded.

Then ported over to C++, time limited exceeded again.

Reviewed the editorial, added segment trees to facilitate range querying, but still exceeded time limit!

=_=U