aram90's blog

Problem solving order during Codeforces Round
By aram90, 13 years ago, In English

I have noticed that during Codeforces standard rounds some people are trying to solve the high-point problems before easier tasks to gain a better score, because points of hard problems decrease faster during time. At first glance it may seem that if in the total you can solve the hard problem, then it may be better to start from it, but it is not always so. For example let's see example on 500 and 1000 point problems. We know that for 500 point problem the decrease speed is 2 points/min, and for 1000 point problem it is 4 points/min. If we consider that they both can be solved in 10 minutes, then we get this total score for them:

Case 1) Solving 500, then 1000: (500 — 10 * 2) + (1000 — 20 * 4) = 480 + 920 = 1400

Case 2) Solving 1000, then 500: (1000 — 10 * 4) + (500 — 20 * 2) = 960 + 460 = 1420

So in that case it is possible to get extra 20 points by choosing right order.

Now let's assume that solving 1000 point problem takes more time than 500, because it is more natural, let's raise that time up to 20 minutes.

Case 1) Solving 500, then 1000: (500 — 10 * 2) + (1000 — 30 * 4) = 480 + 880 = 1360

Case 2) Solving 1000, then 500: (1000 — 20 * 4) + (500 — 30 * 2) = 920 + 440 = 1360

So — in this case there is no difference between choosing one order or another. And if we increase the time for solving 1000 point problem, so that it will become more than two times greater than time necessary for solving 500 point problem, we can figure out that in that case it is better to solve the 500 point at first.

But anyway, this is not a thing to worry about much during contest, it is better to concentrate on solving tasks rather than choosing right order of solving.

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

»
13 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

How about the following strategy: first read all problem statements and try to quickly estimate implementation time for each problem, then solve them in ascending order of your estimates.

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

    At least for me careful reading of all problems takes these minutes when I can submit 500 points.

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

You should sort the problems by in non-decreasing order ;)

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

    sickener mode:

    It's truth when there is no time limit (for example, ), But it's wrong when

    contestLen = 120;
points[] = {500, 1000};
tsolve[] = {10,115};
    → Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Non-decreasing or non-increasing?

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

      Non-decreasing. Actually, there was a problem (editorial) about this fact in TopCoder.

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

        If it is non-decreasing, in that case when we have two problems:

        500 points in 20 minutes (500 / 20 = 25)

        1000 points in 10 minutes (1000 / 10 = 100)

        non-decreasing means solving 500 before 1000, but obviously it should be done in reverse order.

        → Reply