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

Code

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.

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 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.

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.

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. :)