emo's blog

SRM - 467
By emo, 15 years ago, In English
Here is the funny(?!) story behind of my SRM - 467

Last 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 ith slot of walking starts at ti then add overlapping region of [bestArrival, worstArrival] and [ti, ti + 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.
  • Vote: I like it
  • +16
  • Vote: I do not like it

15 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Many contestants, including me, solved 500 by matrix exponentiation. Why do you say it is wrong?
→ Reply
  • 15 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    I wanted to say, my approach was wrong.
    → Reply
  • 15 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    I've also implemented matrix exponentiation, but this solution is not so nice and fast to code, as with binom. coefs. So, this is a problem, where one should probably think more and code less or think less and code more)
    → Reply
15 years ago, # |
  Vote: I like it +1 Vote: I do not like it
wonderful sharing....and more wonderful is consecutive 45th srm...thats awesome..hope the number will increase.
→ Reply