Here is the funny(?!) story behind of
my SRM - 467Last night, after a very bad performance in codeforces beta round#10 I thought I am really in bad form and after having a very short sleep it could be even worse.
250
This problem is a combination of simulation and probability. I just simulate over all of the possible slots of walking ans sum up the region where Professor will encounter a late present by John. Late me call this region L, the late region. If i
th slot of walking starts at t
i then add overlapping region of [bestArrival, worstArrival] and [t
i, t
i + walkTime - lateTime] to the L. The result is L / (worstArrival - bestArrival).
After quickly code this, I found that last two samples giving me wrong output and observed that bestArrival and worstArrival can be same. So I specially handle this case, as I know it will always return 1.0 or 0.0 in this special case.
I found each of the idea of this problem quickly, but still it took 20 minutes. 20 long minutes before I submit.
500
I was stuck here for a while and suddenly became excited, because I thought that I have discern a matrix exponentiation idea. After coding for a few minutes I realized that it is wrong. For thinking from beginning, I draw a table in paper and found that it is nothing but the well known problem, - "how many paths in a grid from (0, 0) to (M, N)", the solution is choose(N + M, M). In this problem you can find easily that N = n - 1, and M = k + 1. Even after finding this it took me a while to understand that it will take only a loop of at most 50 iterations as k <= 50 here. All I need is mod inverse, and as the number given to mod by is a prime, it is easy. Thus I managed to submit just 2/3 minutes before coding phase ending.
1000
I didn't open this problem. Most of the times I do not have time to open 1000. So no wonder at all.
Challenge Phase
I can't realize why I was so excited to challenge a correct solution. I can't even explain whats wrong I saw in that code. All I saw biginteger in that code and thought it will fail. Stupid me, just wasted 25 points, nothing else.
I don't find any reason to get this story of an ordinary coder interesting. BTW, this was my 45th consecutive SRM. :)
congratulations to
rng_58 for win
this match.