How to solve Hermes from IOI 2004?

Revision en1, by AndrijaMlad, 2023-09-01 16:33:54

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: //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!

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English AndrijaMlad 2023-09-01 16:36:09 6 Tiny change: 'o: https: //www.yout' -> 'o: https: https://www.yout'
en1 English AndrijaMlad 2023-09-01 16:33:54 704 Initial revision (published)