ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1699. Turning Turtles

Hint for solution
Posted by Vlad 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!
Re: Hint for solution
Posted by Samsonov Alex [USU] 14 Mar 2009 20:19
This problem can be solved in O(N + Q*logN), where N is the size of the field.
Re: Hint for solution
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?
Re: Hint for solution
Posted by Samsonov Alex [USU] 14 Mar 2009 23:27
Actually it is possible to use the given tree. But calculating the answer is not very trivial.
Re: Hint for solution
Posted by svr 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.
Re: Hint for solution
Posted by Harkonnen 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).