najim4689's blog

RouteIntersection Member Single Round Match 474 div2 500 (any idea)
By najim4689, 11 years ago, In English

http://community.topcoder.com/stat?c=problem_statement&pm=10804

This problem is Member SRM 474 div2 500 problem. Since it is a member SRM, there is no editorial. I cant understand the solution code even. But I am very much interested to understand the solution of this problem and then I will try to solve it.

Please help me understanding the idea of the solution of this problem. I am stuck on this problem.

Tags dp, srm
  • Vote: I like it
  • +1
  • Vote: I do not like it

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

Obviously, you can't store all 50 points, because each point is too large. All you need to do is to find an interval of the travel, [a, b], such that the displacement is zero. So you can bruteforce all pairs a, b to check each coordinate independently. If all coordinates are zero, you visit the same point twice. code1 code2 — faster

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

Displacement !!! right !! thanks a lot... excellent idea !!!

→ Reply