AndrijaMlad's blog

How to solve Hermes from IOI 2004?
By AndrijaMlad, history, 15 months ago, In English

Hello, I am looking for a solution for the problem Hermes. Here is a link to the problem: https://ioinformatics.org/files/ioi2004problem2.pdf ; I have solved this problem for 90% using DP with 3 states, but my solution has a very big memory complexity [20000*2000*2]. My solution is taken from this video: https: https://www.youtube.com/watch?v=bLDy1woBliA ; I have read the official IOI solution, but I don't understand it. BTW for those who want to solve it for the subtask for 50% you can use dp and store your position {N}, your x-axis and y-axis in a 3 dimensional DP. The mem. comp. for this solution is 80*2000*2000; Thanks in advance, hope you have a great day!

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by AndrijaMlad (previous revision, new revision, compare).

→ Reply
»
15 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

When Hermes travel to send a message to a god to another one, he only have to move in one axis, so you can do a DP with a memory complexity [20000 (iGod) * 2000 (the new position on the axis where Hermes move) * 2 (if the last move of Hermes was on the x-axis or the y-axis)] = 80 000 000.

Sorry for my poor English.

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

    Hello attky, I have already implemented this solution and it works for 90% of the problem, If you submit it you will get a MLE messege.

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

      Sorry, I didn't read well your blog.

      → Reply
    • »
      »
      »
      15 months ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      Can you tell me the constraint. They aren't in the task description.

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

        Sorry for not replying to you for a long time, I had some work, The constrains are on the bottom page of the first link

        → Reply
    • »
      »
      »
      15 months ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      You have to optimize de dp in memory, you can apply the %2 tricks because you need only 2 row of the DP table.

      → Reply
»
15 months ago, # |
← Rev. 3   Vote: I like it -9 Vote: I do not like it

Ignore

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

    Hello, I know that you are a master and I am a specialist, so you know more than me, but in the task you need to go in the given order that you are given, so wouldn't that mean that in some cases you would have to go UP, DOWN, UP,... Til you reach the end positions. Can you explane to me haw this solution solves this problem because I dont see it Thanks in advance

    → Reply
    • »
      »
      »
      15 months ago, # ^ |
      ← Rev. 2   Vote: I like it +1 Vote: I do not like it

      It seems that he didn't read that messages must be sent in order.

      As Thyl mentioned you can optimize memory using iterative dp optimizations, but I think that that should still be TLE.

      I think that you can solve it using O(coordinates) memory and O(coordinates + points * log(points)) time by using segment trees or something like that. Keep the dp values in segment trees then you can either use one coordinate or the other to solve the current message. If you use the fixed coordinate, then it's a matter of something like dp_fixed_x[i][coord] -> dp_fixed_x[i+1][coord] + |delta in this coordinate| so range sum (and same for y). If you use the non-fixed coordinate, then it's something like dp_fixed_x[i][coord] -> dp_fixed_y[i+1][point[i].x] + |coord — point[i+1].y|, so it's point update with a query depending on the absolute value. We know that |x — y| is x — y if x > y and y — x if x <= y, so use that to solve the absolute value thing.

      Perhaps doing the process of optimizing memory using iterative dp ideas but still with bad time complexity is still enough because the problem is that old, but even if it's not the case then doing it first might help you understand how you would use segment trees to optimize the transition (only if you manage to optimize it without even using the %2 trick).

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

        Thank you, for the solution Hope you have a great day

        → Reply
    • »
      »
      »
      15 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Ahh my bad, sorry i didn't read that the messages needed to be sent in order

      → Reply