emo's blog

My sad story — SRM 649
By emo, 10 years ago, In English

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.

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

»
10 years ago, # |
  Vote: I like it +18 Vote: I do not like it

Dont use such names for varialbles — for example, instead of 'a' use smth like 'smth that makes sence'. It will take a bit more time, but if such mistakes like u described above are often — will worth.

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Good suggestion. I'll try to follow this.

    → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Also I need to be faster in debugging those kind of situations. Actually I spent more time of verifying my algorithm that this solution actually should work. Because I was skeptical that may be the algorithm has some flaw.

    → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Isn't your code in JAVA, because in sz * log sz * log N passed in JAVA but not in C++ -_-, you can further try to improve it to O(sz * log N)

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    After the fix it still passes system tests in practice room, but yes, should definitely try a better solution.

    → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

a = normalize(a);

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    doesn't work for me, because I cannot modify a, it is reused by caller.

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Actually the reference will be modified, not the array itself

      int[] normalize(int[] a) {
  // put your code with array b, hashmap and sort here
  return b;
}
      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yes, nice technique! Thanks.

        → Reply
»
10 years ago, # |
  Vote: I like it -8 Vote: I do not like it

Use descriptive variables names, indeed. But it is kinda hard and irritating to type thatLongVariable every time if you don't have a very good autocomplete in your text editor or IDE, like Kate or IntelliJ IDEA. But I guess it is worth it for the more difficult problems as it compensates for the debugging time.

And oh, never use the argument — "tourist uses random variable names that come to mind and gets away with it, so I just need to practice more and improve my programming skills, not things like my variable names". To quote my friend, "tourist is constantly making programming genocides" xD

→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 2   Vote: I like it +17 Vote: I do not like it

    After doing some practice — you can actually use random variable names while being pretty sure that you know what these names mean:) Sometimes it is good to write longDescriptiveAndBeautiful variable names when you are writing really complicated code, but in most cases you are using more or less standard blocks of code with more or less standard names — and you are already used to understand it. When you are writing Dijkstra's algorithm for 100th time — I bet you are already comfortable with naming variable for curent vertex as cur/qv/v, variable for distance as dist/d, variable for next vertex as nv/nxt/to (just put your usual names here).

    I've just checked some recent solutions from tourist — and it does not look like random variable names for me; everything is clear. fenw for Fenvick, dir for direction, parity for parity, g for graph, ans for answer and so on; n,m,k etc. — with same meaning as in problem statement. I would not call it random variable names.

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it -8 Vote: I do not like it

      6921847

      a, aa, b, bb, c, cc, d, x, xx, y, yy, ox, oy, xm, ym, mn, km, n, nn, j, jj

      double c = -a * x[i] - b * y[i];
double d = a * bb - b * aa;
xx[ncnt] = (b * cc - c * bb) / d;
yy[ncnt] = (c * aa - a * cc) / d;

      :)

      → Reply