How to solve Hermes from IOI 2004?
Difference between en1 and en2, changed 6 character(s)
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!

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)