Saturday, March 14, 2009

A couple recent FAILs

I've recently lost my 1st TopCoder rating to ACRush and have already fell quite a bit behind. This is mostly due to his superb performance (great job Lou!), but it also highlighted several of the weaknesses of the choices I've made for my competing style: namely, using C# and expecting the time limit to have some margin, and not having any pre-written code to use in the competition.

All 3 last matches made me think again about those questions. In TCO09 Round 1 the hard problem turned out to have a rather strict time limit, and thus my asymptotically correct solution timed out slightly (I believe it ran within 3 seconds) and I had to resubmit, placing only 10th. SRM 436's hard was about fast multiplication of polynomials, and as I don't understand Fast Fourier Transformation good enough to code it and don't have it prewritten, I've resorted to the Karatsuba algorithm and again, my solution was very little over the time limit, so I've spent a lot of time until finally getting it under the time limit (and again, it turned out that this solution was expected to be correct by the problem authors), scored very low and placed only 15th. Today, me failing the medium problem was totally my fault (I couldn't invent the correct solution) - but even if it didn't fail, I would place below Lou because he had a pre-written implementation of the Dinic maximum flow algorithm for the hard problem, and it turned out that one could run that 2500 times under the time limit. This was not possible with the stupid maximum flow algorithm I've used, and thus I had to spent a bit more time implementing a slightly more complex approach.

I still believe that all this happening in a row is just a bad coincidence, and in the long term my strategy has more pros than cons. Next couple of months will show :)

19 comments:

  1. "(...)using C# and expecting the time limit to have some margin, and not having any pre-written code to use in the competition."

    Why did you choose C#?
    I thought you had some pre-written code. Why don't you have?
    I don't know if I understood what you meant with the post but, are you going to built some pre-written code?

    ReplyDelete
  2. I'm antonov in TC. Although I am just a newbie in Algorithm, I can understand how you feel right now. I have admired you in this field and Roger Federer in Tennis, who both had just lost the first ranks.
    Through some of your screencasts, I especially love your way of competing, which is fair, gifted and tactful.
    I am not sure if ACRush still wins the matches without pre-written codes, but your not using them makes me more admire you. Best of luck for the future!

    ReplyDelete
  3. 2Paulinho: C# - because it's much harder to make a bug there than in C++, and because it has a little more convenient syntax and is faster than Java.

    I don't have prewritten code since
    1) I'm too lazy to assemble it.
    2) I believe that learning how to code algorithms by oneself is more interesting than just having them ready.

    No, I'm not going to change anything in my approach (yet?). I wrote the post to let the idea out, and to find out what do others think about this.

    2antonov: thanks! As I said in the post, Lou's recent performance is outstanding and I'm pretty sure prewritten codes are only a small part of that.

    ReplyDelete
  4. I think using prewritten code might be bad only for the beginners, in your case it would only save some time.

    ReplyDelete
  5. I agree Antonov, and (I don't know if I read it correctly but) I think one can't take pre-written code at onsite phases and this will be a great advantage to Petr since he is familiarized with that (maybe this is what you meant with "a couple of months will show").

    ReplyDelete
  6. I'm a newbie in Algorithms. When I have a problem I cannot solve, I'll take a lot of time on it, but finally still can't get an answer.
    What will you do when you have a problem you can't solve ?
    Can you give me some suggestions ?
    Thank you!

    ReplyDelete
  7. hey Petr! I was wondering if the solutions to the questions of Petr Contests were available.

    I have learnt much more from looking at your solutions than some books .There is a lot of clarity in your coding style. Hope u don't change it . [:)]

    ReplyDelete
  8. 2Karthik: I'll post them when I get to them (my server, 77.41.63.3, is currently down).

    2seeker: I move on to other problems. What else can one do :)

    ReplyDelete
  9. С днём рождения, Программер!

    ReplyDelete
  10. 2Karthik:

    http://77.41.63.3/blog/pm1/
    http://77.41.63.3/blog/pm2/
    http://77.41.63.3/blog/pm3/
    http://77.41.63.3/blog/pm4/

    Some of those are not by me - suffixes "pmi", "pm" and "petr" mean me, "as", "ml" and "vg" - my collaborators.

    ReplyDelete
  11. HI,

    I am FameofLight from topcoder , i clearly admire your way of competing , also not having pre-written code is best part , because you lose the fun solving problem at instant and pressure to work within .

    Also much clearer code are nice to see.although my rating don't goes up but i always adhire to clearness of my code whatever problem I solve.
    Hemant Verma

    ReplyDelete
  12. @ Petr : Thanks for the reply :)

    ReplyDelete
  13. Hi,

    Just eager to know what about the person , who is learning algorithm , you advice to have pre-written code or code at the time of contest

    ReplyDelete
  14. Hi Petr!

    I think that your style may lose sometimes against pre-written codes. However, i believe that during the on-site events you have the advantage since you don't need the algorithm library that others use (including me) during the online contests.

    Just another thing... are you sure that you don't use "fast forward" in your screencasts? :)
    Just kidding of course, your thinking speed is amazing!

    Good luck for the TCO,
    Miguel Oliveira < mogers >

    ReplyDelete
  15. 2FameofLight: I'm not sure, but I think not using prewritten code is better for learning faster.

    2Miguel Oliveira: In fact, there might be fast forward-like effects there: the recorder runs at the lowest priority, thus, when I execute some code that eats all CPU (like a stress-test), the recorder may get no cycles at all :)

    ReplyDelete
  16. If a TopCoder problem can be easily solved with a standard pre-written algorithm (like max flow, simplex, FFT, Hungarian, etc), and is much harder otherwise, then it is not a good problem, IMO...

    ReplyDelete
  17. you are the number one again.

    ReplyDelete