| ENG RUS | Timus Online Judge |
Discussion of Problem 1699. Turning TurtlesVlad Hint for solution [5] // Problem 1699. Turning Turtles 14 Mar 2009 18:08 This was overall a great problems set! Can anyone give a hint on the solution for "J. Turning Turtles"? What special property (beside that it's a tree) must one use? What is the complexity of the intended solution? Thanks in advance! Samsonov Alex [USU] Re: Hint for solution [2] // Problem 1699. Turning Turtles 14 Mar 2009 20:19 This problem can be solved in O(N + Q*logN), where N is the size of the field. Vedernikoff Sergey (HSE: EconomicsForever!) Re: Hint for solution [1] // Problem 1699. Turning Turtles 14 Mar 2009 21:43 Am I right that we build slightly another tree and then use LCA on that? =) And when the problems will be added to the problemset? Samsonov Alex [USU] Re: Hint for solution // Problem 1699. Turning Turtles 14 Mar 2009 23:27 Actually it is possible to use the given tree. But calculating the answer is not very trivial. svr Re: Hint for solution [1] // Problem 1699. Turning Turtles 14 Nov 2009 11:30 I was glad to use successfully LCA with forgotten implementation. It is enough to know what LCA do. It is mean that LCA very adequate tool for tree and cannot be omitted in learning. Harkonnen Re: Hint for solution // Problem 1699. Turning Turtles 17 Aug 2022 10:36 It is possible to use given tree, but my complexity is O(N*log(N)+Q*log(N)) - 0.25 sec and quite a bunch of RAM. For every node store its 1st, 2nd, 4th, 8th, 16th, ... 2^16th parent. Also store number of turns on that path and final orientation after last move (horizontal/vertical). This information is enough to calculate answers at log(N). cap_prot Have wa #12 [1] // Problem 1699. Turning Turtles 27 Jan 2013 18:46 My program is more advanced than LCA. It uses BFS and could work on arbitrary graphs. Could somebody help with this test? I know that if there is no bug with my program then there is a problem with connectivity of graph from start point to end point. ძამაანთ [Tbilisi SU] Re: Have wa #12 // Problem 1699. Turning Turtles 6 Aug 2013 19:17 Check for cases when start = end. also don't use incorrect comparison. for example: newPoint = point+delta if(0<=newPoint && newPoint<w*h) Baurzhan wa #7 [2] // Problem 1699. Turning Turtles 5 Nov 2010 19:40 Who had problems with test #7, tell me WTF? Please,anybody,post here some tricky tests! bsu.mmf.team Re: wa #7 [1] // Problem 1699. Turning Turtles 9 Nov 2012 20:20 This test helped me to avoid WA#7: 6 6 ###### #.#.#. #.#.## #..... ###### #.#..# 1 3 6 6 6 ans: 6 cap_prot Re: wa #7 // Problem 1699. Turning Turtles 27 Jan 2013 18:40 Right answer is 5, isn't it? Edited by author 27.01.2013 18:40 Vedernikoff Sergey (HSE: EconomicsForever!) For those who has problems with test #4 // Problem 1699. Turning Turtles 16 Mar 2009 01:44 Try this test: INPUT ------- 1 1 # 2 1 1 1 1 1 1 1 1 OUTPUT ------- 0 0 Edited by author 16.03.2009 15:10
|