@xellos0: Nice solution So, basically, for each batch of O(sqrt(N)) queries, you end up with a tree having O(sqrt(N)) vertices (after “compressing” all the leaves not corresponding to vertices changing colours into their parents). I really enjoy simpler O(sqrt(N))-based alternative solutions to otherwise data structure-intensive problems. “Sadly”, this time my own solution is very much along the lines presented in the editorial.
@shangjingbo: This solution is not brute-force. I thought you (the organizers) were able to fail the brute-force solutions by adding more test cases.
@mugurelionut: There was one unusual brute-force solution pass during contest(Thanks for @pat3ik), so there is a rejudge at the beginning. But as long as I relax my vigilance, there is still a brute-force code with lots of heuristic optimization can pass the test data at the last day CodeChef: Practical coding for everyone
Please clear this doubt:
“update: update each node until highest parent and first node with different color also”
here we have to find “the different color node” , how can we find efficiently that node without travelling the path that contain them?
Going upwards the tree will visit at most logn light paths, and at most logn heavy chains, while in a heavy chain he uses that binary search idea to check if there is a different color node, if there isn’t he skips the whole chain going to the topmost node. A chain can be very big, it is contain lots of nodes, so here you can’t check nodes one by one. (that image in the editorial is quite confusing though :/)
what @brunoja says… note that I used 3 BITs per path. One to see the component the node in the path connects to. just a number which is the same if two nodes are in the same component (same color and connected).
And 1 tree per color. CodeChef: Practical coding for everyone
I also want to remind the Java people that there is a stacklimit, so I had to rewrite my methods which used to many recursion.
num is the node number, which I name with the dfs func; inv is the inverse of the num array; wei is the size of each node; hev tells which heavy chain the node is in (or none); top contains the topmost node of a heavy chain; pai is the parent of the node; seg is the BIT that is used in the described solutions (although I am not sure if its 100% the same approach in the editorial); col is the current color of the node; dep is the highest node number of the tree rooted at a node; fio contains the child of a node in a heavy chain. I hope it is clear :), just tell me if something else is obscure…
if we decide heavy and light edges according to the editorial that the edge to the son with biggest size is heavy , then there are chances of tie , when a node v has some sons and two or more have biggest size for example a node ha sthree childrens and of them has size 5 and one has size 3.then u can consider any of the two edges of size 5 as heavy.
but if u consider a node v having size(v)>1/2xsize(parent(v)) . Then there will be no tie.
Do we move upwardly node by node to find the upmost same color node…plz clarify how we will move if the edge is heavy and when the edge is light.THANKYOU…
The BIT is 1D, and it is for the entire tree. The only thing I store from the tree in the editorial is wether a node belongs to a heavy chain or not, and for each chain I keep the index of the nodes of black color (for the white tree, and vice-versa for the black one).
I have confusion in binary search what type of array we will keep to find the same color node in a heavy chain by binary search please explain.THANKYOU
So, basically, for each batch of O(sqrt(N)) queries, you end up with a tree having O(sqrt(N)) vertices (after “compressing” all the leaves not corresponding to vertices changing colours into their parents). I really enjoy simpler O(sqrt(N))-based alternative solutions to otherwise data structure-intensive problems. “Sadly”, this time my own solution is very much along the lines presented in the editorial.
