Tuesday, June 18, 2013

Change of plans

If you remember the post: Topcoder SRM 560-562: You people have stood in my way long enough. I'm going to clown college!. You would know that's the moment in which I decided to start using a new contest strategy: To open the "Easy" problem only when there are 10 minutes left for the match.

As it was expected, that strategy is too risky. I had very bad matches afterwards. A good example is the last one: SRM 582.

In SRM 582, I opened the division 1 hard, it seemed a bit complicated. Then I opened the div1 medium. I spent the remaining tens of minutes trying to code an easy (but super slow) dynamic programming approach. In the hopes that maybe, once that approach is coded and understood, I can optimize it to O(N^2). (This is an approach that has worked for me in the past). But I kept having issues with the example cases, so something was probably wrong, either in the code or in my understanding of the problem.

I opened 250 points problem. I only had 10 minutes. I realized that it could be solved by a binary search. The matching afterwards could be done with some greedy strategy. But I had the *brilliant* idea to use min-cost-flow to solve this. Unfortunately, it seems I spent more time than I planned pasting and tweaking my min-cost-flow solver (It didn't help that KawigiEdit has the habit of turning slow when there is a lot of code).

At the end, this one last SRM has taught me. The strategy is too risky. I need a change.

This is the reason that , from now on, I will change my strategy: I will no longer open the easy problem during the coding phase. I will only open the medium and hard problems and dedicate all the coding time to attempt to solve at least one of them.


I bet this new strategy will be much less risky!
(Wikimedia Commons)

6 comments :

Gareve said...

You are a crazy man xD Good luck on your savage strategy (y)

Jhonatan Castro said...

He he..., all we have to pay a price to get something ...
Happy Coding!

Shuaib said...

Vexorian, what is the intention behind this strategy? To me it seems like your intention is the satisfaction of solving harder problems, and you aren't interested in rating that much. Correct? Because if rating was your concern, I think going with easy, medium, harder, order makes more sense. Or do you think this strategy will help your rating in the long run, what with being able to solve harder problems more consistently, there will come a time when you will be able to solve harder ones, plus get time to solve the easy. :)

vexorian said...

I am not even sure if I have to reply now that you typed my reply in your own comment.

Shuaib said...

:)

Oswaldo Ceballos Zavala said...

Using same strategy we solved 0 problems in ICPC Latin America 2013 (last year we solved 3 problems, form easiest to harder ones). It's too risky.