emo's blog

By emo, 5 years ago, In English,

Today in topcoder single round match 649, I did a small mistake on 550.


One of my test was failing for this mistake and couldn't figure out what was wrong during the contest.

        long res = 0;
        FenwickTree tree = new FenwickTree(sz);
        for (int i = 0; i < sz; ++i) {
            res += tree.read((int)a[i] - 1);
            tree.update((int)a[i], 1);
        return res;

Here I used a instead of b. I normalized int[] a into int[] b to use that with FenwickTree but at the end I ended up using the original array a. Replacing a with b makes the code pass all test.

If anyone has suggestion about how to overcome this kind of mistake and how to concentrate more, please let me know.

Read more »

Tags srm
  • Vote: I like it
  • -21
  • Vote: I do not like it

By emo, 8 years ago, In English,

I would like to share my problem solving blog with you - I solved a problem.
I hope your comments and suggestions will help me.

Read more »

  • Vote: I like it
  • 0
  • Vote: I do not like it

By emo, 10 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.


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.


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.


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.

Read more »

  • Vote: I like it
  • +16
  • Vote: I do not like it

By emo, 10 years ago, In English,
In the context of programming contest -

Problem setter has to think - is there any solution?
Problem solver only thinks - it must has a solution, let's try.

So, I think the latter is the easier most of the time.

Read more »

  • Vote: I like it
  • +4
  • Vote: I do not like it

By emo, 10 years ago, In English,
I just registered for "Codeforces Beta Round #6", as soon as I got the mail. Last round I forgot to register. I forgot that codeforces contests also require registration. I opened first problem and solved within 8 minutes, then rushed to submit and found that I was not registered. :(

From now on, as soon as I get mail, I shall register. :)

Read more »

  • Vote: I like it
  • +1
  • Vote: I do not like it