Answers to: PSHTTR - Editorialhttps://discuss.codechef.com/questions/105181/pshttr-editorial<h1>PROBLEM LINK:</h1>
<p><a href="https://www.codechef.com/problems/PSHTTR">Practice</a> <br>
<a href="https://www.codechef.com/JULY17/problems/PSHTTR">Contest</a> </p>
<p><strong>Author:</strong> <a href="https://www.codechef.com/users/fekete">Ivan Fekete</a> <br>
<strong>Primary Tester:</strong> <a href="https://www.codechef.com/users/mgch">Misha Chorniy</a> <br>
<strong>Editorialist:</strong> <a href="https://www.codechef.com/users/deadwing97">Hussain Kara Fallah</a></p>
<h1>DIFFICULTY:</h1>
<p>Medium</p>
<h1>PREREQUISITES:</h1>
<p>Graph Theory,Sorting,Data Structures</p>
<h1>PROBLEM:</h1>
<p>Given a rooted weighted tree with <strong>N</strong> nodes and <strong>M</strong> queries of the form <strong>(u , v , K)</strong>. For each query, you must report to <strong>xor</strong> sum of edges which has weight less than or equal to <strong>K</strong> on the path from <strong>u</strong> to <strong>v</strong>.</p>
<p><strong>N,M ≤ 10^5</strong></p>
<h1>EXPLANATION:</h1>
<p>First of all let's solve the easier version of this problem. Queries which asks for the xor sum of edges on the path between 2 fixed nodes <strong>(without the restriction of K).</strong>
Let's choose an arbitrary root for our tree and call a Depth-First search starting from this node.Let's maintain a table <strong>S[N]</strong>, such that <strong>S<sub>i</sub></strong> denotes the <strong>xor</strong> sum of edges weights starting from the <strong>root</strong> and ending at node <strong>i</strong>. The answer of each query <strong>(u,v)</strong> would be <strong>(S<sub>u</sub> xor S<sub>v</sub>)</strong>. Edges of the chain starting from the root and ending at <strong>LCA(u,v)</strong> (lowest common ancestor) would be excluded because <strong>(V xor V = 0)</strong>.</p>
<p>Now let's solve our problem. First thing we should take advantage of, is that we can answer our queries offline (reading then processing all queries, after that reporting the answer of each one).
Each edge weighted <strong>W</strong> must be included in the answer of all queries with <strong>K ≥ W</strong>. For queries with <strong>K < W</strong> we can assume that this edge's weight is zero (so it won't affect the answers).</p>
<p>Let's sort our queries in ascending order according to their magic numbers <strong>K</strong>, and sort our edges in ascending order according to their weights <strong>W</strong>. Let's process our queries in ascending order, and maintain a pointer iterating on our sorted edges list. So before processing a query with magic number <strong>K</strong>, we add all edges with <strong>W ≤ K</strong> through our pointer.</p>
<p>Now Let's discuss adding edges, and how will we get our table S[].</p>
<p>Let's maintain a timer incremented by one every time we visit a new node in our Depth-First-Search, and keep for the <strong>i<sup>th</sup></strong> node a variable <strong>st<sub>i</sub></strong> (denoting the value of the timer once entering this node),and a variable <strong>en<sub>i</sub></strong> denoting the value of the timer after finishing this node's subtree (before exiting). This is a famous technique called euler tour on tree (dfs order). So we can represent nodes located in the subtree of the <strong>i<sup>th</sup></strong> node by interval <strong>[st<sub>i</sub> , en<sub>i</sub>]</strong></p>
<p>Regarding adding edges, each edge will link between 2 nodes <strong>(u,v)</strong> such that <strong>u = par[v]</strong>, this edge's weight will be added to the <strong>xor sum</strong> (cumulative xor sum from the root) of all nodes located in the subtree of <strong>v</strong>. That means we should apply the operation</p>
<p><strong>S<sub>i</sub> = S<sub>i</sub> xor V</strong> </p>
<p>for each <strong>i</strong> : <strong>(st<sub>v</sub> ≤ i ≤ en<sub>v</sub>)</strong></p>
<p>This can be done using a binary indexed tree, segment tree (with/without) lazy probagation. Since our modification query is done on a segment of array <strong>S</strong> and we are querying the value of only one element we can do the following:</p>
<p>Let's maintain an array <strong>X</strong> which is all zeros at the beginning. When handling an edge of weight <strong>W</strong> added to the results of nodes in node v subtree. </p>
<p><strong>X[st<sub>i</sub>] = X[st<sub>i</sub>] xor V</strong></p>
<p>This means that we are adding V to the <strong>xor</strong> sum of all nodes with enterance <strong>timer ≥ st<sub>v</sub></strong></p>
<p><strong>X[en<sub>i</sub> + 1] = X[en<sub>i</sub> + 1] xor V</strong></p>
<p>This means that we are excluding <strong>V</strong> from the <strong>xor</strong> sum of all elements with entrance <strong>timer > en[v]</strong> (since it was added in the first operation so doing <strong>xor</strong> again is equivalent to exclusion).</p>
<p>You can notice now that the value of <strong>S<sub>i</sub></strong> is:</p>
<p><strong>S<sub>i</sub> = X<sub>1</sub> xor X<sub>2</sub> xor X<sub>3</sub> xor X<sub>4</sub> xor X<sub>5</sub> xor ... X<sub>i</sub></strong></p>
<p>Now we can easily iterate through our queries, and for each one we should make sure that all edges with weight less than or equal to this query magic number are added. After that, each query can be solved in O(log N).</p>
<p>Total complexity <strong>O(N log N + M (log M + log N))</strong></p>
<h1>AUTHOR'S AND TESTER'S SOLUTIONS:</h1>
<p><strong>AUTHOR's solution</strong>: Will be found <a href="https://s3.amazonaws.com/codechef_shared/download/Solutions/JULY17/Setter/PSHTTR.cpp">here</a> <br>
<strong>TESTER's solution</strong>: Will be found <a href="https://s3.amazonaws.com/codechef_shared/download/Solutions/JULY17/Tester/PSHTTR.cpp">here</a> <br>
<strong>EDITORIALIST's solution</strong>: Will be found <a href="https://s3.amazonaws.com/codechef_shared/download/Solutions/JULY17/Editorialist/PSHTTR.cpp">here</a></p>enSun, 30 Jul 2017 17:06:21 +0530Answer by rajat_manglahttps://discuss.codechef.com/questions/105181/pshttr-editorial/107256<p>in the editorial solution they have binary index tree to store the value....
i tried to use the soln given using segment tree but it is giving wrong answer ....
can anyone tell me what is wrong in my code?
<a href="http://ideone.com/5lRSww">here is the code</a></p>rajat_manglaSun, 30 Jul 2017 17:06:21 +0530https://discuss.codechef.com/questions/105181/pshttr-editorial/107256Comment by vishesh_345 on vishesh_345's answerhttps://discuss.codechef.com/questions/105181/pshttr-editorial#106572<p><a href="/users/103648/john_smith_3"><a href="/users/103648/john_smith_3">@john_smith</a></a> so i can say that if u to v has to include root it must be the lca of both those nodes(possibly) and in case of that there is no problem because we can take xor as mentioned above without any problem and if root node is the lca then there will be no edge whose xor is to be taken with <a href="http://themselves.Is">themselves.Is</a> this correct?
Thank you for your reply:)</p>vishesh_345Wed, 26 Jul 2017 11:21:14 +0530https://discuss.codechef.com/questions/105181/pshttr-editorial#106572Comment by john_smith_3 on vishesh_345's answerhttps://discuss.codechef.com/questions/105181/pshttr-editorial#106561<p>In the problem, the <strong>V</strong> values are attached to edges between two adjacent nodes.</p>
<p>In the Editorialist's solution, the values are attached to the node more distant from the root node. There is some logic
<code>
for(int j = 1 ; j < n ; j++){
if(st[E[j].first] < st[E[j].second])
swap(E[j].first , E[j].second);
sorted.push_back({W[j] , -E[j].first});
}
</code>
which swaps the ends of the edge E[j] so that E[j].first is further from the root node than E[j].second.</p>
<p>There is no V associated with the root node,</p>
<p>Hope that makes sense.</p>john_smith_3Wed, 26 Jul 2017 01:52:55 +0530https://discuss.codechef.com/questions/105181/pshttr-editorial#106561Comment by vishesh_345 on vishesh_345's answerhttps://discuss.codechef.com/questions/105181/pshttr-editorial#106549<p><a href="/users/220103/deadwing97"><a href="/users/220103/deadwing97">@deadwing97</a></a> please clear my doubt.</p>vishesh_345Tue, 25 Jul 2017 23:38:24 +0530https://discuss.codechef.com/questions/105181/pshttr-editorial#106549Answer by vishesh_345https://discuss.codechef.com/questions/105181/pshttr-editorial/106548<p><code>The answer of each query (u,v) would be (Su xor Sv). Edges of the chain starting from the root and ending at LCA(u,v) (lowest common ancestor) would be excluded because (V xor V = 0).</code> </p>
<p>Can someone please explain what if root node is in between path of u and v. Now if we take xor S[u] and S[v] then we will take xor of root node twice which will eliminate the contribution of node from the xor since root is taken twice and it vanishes and becomes 0. But that was not intended because root node was a part of the path . Have I got something wrong. Please Help.</p>vishesh_345Tue, 25 Jul 2017 23:00:43 +0530https://discuss.codechef.com/questions/105181/pshttr-editorial/106548Comment by vijju123 on vijju123's answerhttps://discuss.codechef.com/questions/105181/pshttr-editorial#106334<p>Thanks a lot man!! I was REALLY clueless about that complement thing in your fist comment. I thought it just inverted some hidden bit in frontmost position (which determined sign).</p>
<p>Your comment clarified everything, Thanks a LOT man!! Really!!</p>vijju123Mon, 24 Jul 2017 01:00:25 +0530https://discuss.codechef.com/questions/105181/pshttr-editorial#106334Comment by john_smith_3 on vijju123's answerhttps://discuss.codechef.com/questions/105181/pshttr-editorial#106332<p>The nodes are numbered by the depth-first-search process starting at root node, with numbering stored in st[n] (and also, but different, in en[n]).</p>
<p>You are right - edge V is xor-ed in the interval [st,en].</p>
<p>The EDITORIALIST's solution includes the lines
<code>
add(st[node] , Q.first);
add(en[node] + 1 , Q.first);
</code></p>
<p>When the corresponding <strong>get(x)</strong> is evaluated, </p>
<ul>
<li>if x < st[node] then Q.first is not included in the big xor</li>
<li>if st[node] <= x <= en[node], then just the first Q.first is included</li>
<li>if en[node] < x, then both Q.first ^ Q.first = 0 is included</li>
</ul>john_smith_3Mon, 24 Jul 2017 00:57:44 +0530https://discuss.codechef.com/questions/105181/pshttr-editorial#106332Comment by john_smith_3 on vijju123's answerhttps://discuss.codechef.com/questions/105181/pshttr-editorial#106323<p>Most processors use the two's complement representation of negative numbers. (The C99 standard permits other representations of negative numbers)</p>
<p>To calculate the two's complement binary representation of -x, write down the binary representation of x, complement each bit, and add one. </p>
<p>For example, 100=64+32+4 decimal, so the 100 decimal is 1100100 binary.
<code>
100 decimal = ...0001100100 binary
complement each bit ...1110011011
add 1 ...1110011100
-100 decimal = ...1110011100 binary</code></p><code>
</code><p><code>Notice:
100 & -100 decimal = 0000000100 binary
</code></p>john_smith_3Mon, 24 Jul 2017 00:12:03 +0530https://discuss.codechef.com/questions/105181/pshttr-editorial#106323Comment by vijju123 on vijju123's answerhttps://discuss.codechef.com/questions/105181/pshttr-editorial#106299<p>Thanks john!! I really appreciate your explanation. </p>
<p>Can you just further tell on <code>x & (-x) gives the least significant bit of x,</code> ?? </p>
<p>I thought that the edge V should be xored in the interval of [st,en] (where st and en are time of entering and leaving that edge's subtree), i.e. consecutive elements should be xored. Doesnt this depend on numbering of node by some means? I am unable to get it :(</p>vijju123Sun, 23 Jul 2017 20:15:55 +0530https://discuss.codechef.com/questions/105181/pshttr-editorial#106299Comment by john_smith_3 on vijju123's answerhttps://discuss.codechef.com/questions/105181/pshttr-editorial#106288<p>Read and study the <strong>get()</strong> and <strong>add()</strong> functions at the same time:
<code></code></p><code>
</code><p><code>void add(int y , int V){
while(y <= n){
bit[y] ^= V;
y += y & (-y);
}
}
</code>
<strong>get()</strong> returns the xor of the <strong>V</strong> values inserted by <strong>add(y, V)</strong> where <strong>y <= x</strong>.</p>
<p>Note how the expression <strong>x & (-x)</strong> gives the least significant bit of <strong>x</strong>, so that the loop in the <strong>get()</strong> function keeps rounding <strong>x</strong> down to a multiple of larger power of 2, and the loop in <strong>add()</strong> keeps rounding <strong>y</strong> up to a multiple of a larger power of 2. </p>
<p>A similar trick could find the sum of <strong>V</strong> values.</p>john_smith_3Sun, 23 Jul 2017 19:32:43 +0530https://discuss.codechef.com/questions/105181/pshttr-editorial#106288Comment by vijju123 on amit88265's answerhttps://discuss.codechef.com/questions/105181/pshttr-editorial#106254<p>I think if we add 1-2 more tags in pre-requisite (like euler tour, dfs, segment tree/BIT) then perhaps people will read it after getting through the pre-requisites.</p>vijju123Sun, 23 Jul 2017 11:44:32 +0530https://discuss.codechef.com/questions/105181/pshttr-editorial#106254Answer by vijju123https://discuss.codechef.com/questions/105181/pshttr-editorial/106253<p>Can someone explain the get function in Editorial's solution? Its this-</p>
<pre><code>int get(int x){
int ret = 0;
while(x > 0){
ret ^= bit[x];
x -= x & (-x);
}
return ret;
}
</code></pre>
<p>Can someone explain it? Its my first time coming across this type of implementation, so i cannot backtrack the thought process.</p>vijju123Sun, 23 Jul 2017 11:43:25 +0530https://discuss.codechef.com/questions/105181/pshttr-editorial/106253Comment by vaibhavchhabra on vchhabra's answerhttps://discuss.codechef.com/questions/105181/pshttr-editorial#106204<p>yeahaaaaaaa</p>vaibhavchhabraSat, 22 Jul 2017 21:29:21 +0530https://discuss.codechef.com/questions/105181/pshttr-editorial#106204Comment by vaibhavchhabra on vchhabra's answerhttps://discuss.codechef.com/questions/105181/pshttr-editorial#106201<p>I guess they are swapped</p>vaibhavchhabraSat, 22 Jul 2017 21:23:31 +0530https://discuss.codechef.com/questions/105181/pshttr-editorial#106201Answer by h_traphttps://discuss.codechef.com/questions/105181/pshttr-editorial/106079<p>practice and contest links are swapped.</p>h_trapFri, 21 Jul 2017 04:42:45 +0530https://discuss.codechef.com/questions/105181/pshttr-editorial/106079Comment by deadwing97 on amit88265's answerhttps://discuss.codechef.com/questions/105181/pshttr-editorial#106012<p>The editorial is explained in detail. Not understanding a part of it that means that you are missing something you should learn. To solve this problem you should be understanding xor,dfs,dfs order,(Segment tree\BIT)</p>deadwing97Thu, 20 Jul 2017 15:23:31 +0530https://discuss.codechef.com/questions/105181/pshttr-editorial#106012Answer by amit88265https://discuss.codechef.com/questions/105181/pshttr-editorial/106009<p>can anyone explain me briefly what is going on above???</p>amit88265Thu, 20 Jul 2017 14:57:36 +0530https://discuss.codechef.com/questions/105181/pshttr-editorial/106009Answer by ak_mittal006https://discuss.codechef.com/questions/105181/pshttr-editorial/105911<p>Thanks to this problem I learned few new things. For beginners who are facing difficulty solving this (like i did) I recommend following steps -</p>
<ol>
<li>learn dfs </li>
<li>learn segment trees (for Range minimum queries) or sparse table</li>
<li>Learn about euler array , (this <a href="https://www.youtube.com/watch?v=HeeyUZmaZg0">video</a> helped me with implementation )</li>
<li>read this <a href="https://www.topcoder.com/community/data-science/data-science-tutorials/range-minimum-query-and-lowest-common-ancestor/">topcoder article</a></li>
<li>solve <a href="http://www.spoj.com/problems/LCA/">spoj lca</a> or <a href="https://www.codechef.com/problems/TALCA">this lca problem</a></li>
<li>finally try to solve <a href="https://www.codechef.com/problems/TAQTREE">this similiar problem</a></li>
</ol>
<p>I hope above helps :)</p>ak_mittal006Wed, 19 Jul 2017 17:14:55 +0530https://discuss.codechef.com/questions/105181/pshttr-editorial/105911