Hey guys, can anyone give a detailed explanation on how to solve the following questions-
1)Pishty and Tree
- Two coins.
Both are from July Long.
Two Coins is the kind of problem whose solution was made first and then problem was made.
Just one dfs is needed to solve the problem.
Could you explain your solution?
1 Like
I know that one dfs is enough, but what was your logic. I was unable to come up with a flawless algo, and got overwhelmed by huge possibility of cases.
For Pishty and Tree:
I basically implemented the editorial: https://discuss.codechef.com/questions/105181/pshttr-editorial. There were two things to note here(assuming root as 0 and nodes are between 0 and n-1):
-
For each node, every node in its subtree can be labelled by consecutive numbers using its DFS order, hence forming an interval. Read here for details: http://codeforces.com/blog/entry/18369
-
For an edge value between a node x and its parent, this edge will be present in all paths from the root to each node in the subtree of x.
I mapped each edge value with the the intervals of its all possible subtrees. I sorted all the queries by K. Before processing each K, I updated all paths which contained edges<=K using lazy propagation.
Also note that the answer for each query will be (xor of values in root to u) xor (xor of values in root to v). The edges not in path from u to v will appear exactly twice and hence, cancel out.
My code: https://www.codechef.com/viewsolution/14513419
Feel free to ask if something is not clear.
2 Likes
For each node, every node in its subtree will be consecutive numbers forming an interval.
How did you arrive at this? What if tree is random, like node 30 just below node 2, node 3 somewhere far off, meaning a random arrangement where the numbers are not consecutive?
The pre processing part was very clever. I liked that.
I updated the line. Basically I was using DFS to label the nodes. In DFS, you visit all nodes in the subtree of the current node before going anywhere else. Hence, after labelling, all nodes in the subtree will be labelled consecutively, and hence we can apply range updates on them.
Okay, so you custom labelled than and used the interval. Thanks for your answer ^^
2 things here. We don’t need to use a map, we can use an array also because we need to store for each node. Secondly, we can do without lazy propagation. Instead of point updates, range queries, we have range updates, point queries, so we can swap the function.
What was your approach, mathecodician?
I’ll try to explain my implementation of TWOCOINS :-
Prerequisite- DP on Trees
Create a 3-D DP storing minimum possible number of coins in its subtree, where first index represents node number, second index represents whether the parent of node has coin or not, and the third index represents whether the node itself has coin or not.
Observations:-
-
The leaf MUST possess a coin (since every node in a tree has only one parent so you can only pull in one coin at most). Moreover, parent or grandparent of the leaf MUST have a coin due to reason given in bracket
-
See this table of configuration :-
3)Consider a node which have any of its child as leaf. Then all configuration of node except FALSE-FALSE is acceptable, with the leaf compulsorily getting a coin.
With all the above points in mind we just have to create a DFS with DP function and hit an AC 
.
My code is available here, I hope its clear enough
7 Likes
I knew it needs dp but i have 0 experience of dp on trees. I just modified my greedy of filling every grand-parent node but got over 30 wa 
This was my first question with DP on trees too 
. Actually you don’t even need to learn DP on trees differently. The idea starts coming naturally to you slowly once you start doing DP problems on your own. The idea here is very similar to DP on arrays. The only difference is that generally the no of states in array DP is generally fixed and on trees you need to handle multiple sub states when it comes to trees. Happy coding
1 Like
I have awarded some points can you upload the image now?
If not can you please provide a link for it because images give a clear cut explanation
@sonu_628 thanks for the points! I have updated point 2 with a table, so it should be clearer now. What exactly were you not able to follow, can you please describe? I’ll try to help you out for the same
3 Likes
@kr_abhinav thanks for uploading the table it is clearer now . I looking through to your solution and did not understand the part where if(cp) => mean if parent has coin . In this section what is coint and mn doing . If you could bit explain it would be very helpful
2 Likes
mn and cnt were to check if atleast one child configuration had a coin in it and was possible to construct (i.e., the answer was not -1 for subtree of that child)