You are not logged in. Please login at www.codechef.com to post your questions!

×

# PTREE - Discussion

 0 Share your approach for getting PA or AC for the PTREE problem, I tried to use simple DFS on it (for PA) but failed...The Editorials will probably take some time, so please share your approaches(for PA or Complete AC). asked 13 Mar, 16:47 78●6 accept rate: 7%

 0 use disjoint sets to store the root of every node.... For example: if n = 6 for tree with edges 1 2, 1 3, 2 4, 2 5, 4 6 then the disjoint set will be like: 1 1 1 2 2 4 from here u can easily calculate the distance like: distance[ u ] = distance[ root[u] ] + 1; answered 13 Mar, 16:55 3●2 accept rate: 0% will you (or) anyone explains what is wrong with this code: https://pastebin.com/CBzkhatT (13 Mar, 17:45) I think you missed something in the "getEdgeDistances" function... you can find my solution to this problem here https://github.com/Samarth9798/Codechef-March-Challenge-2019- (13 Mar, 18:18)
 0 I had 2 TLE / 11 AC with the following: Re-labeling the graph so that nodes a and b of the same depth are |a-b| nodes apart. Given a and b at the same layer this can efficiently give you a' and b' in the next layer such that [a', b'] is the set of children of nodes in [a, b]. For each node u, precomputing its deepest descendant v (and it's depth D(u)) such that every node that is an ancestor of v and not u has exactly one child. Precomputing an RMQ data structure to answer min(D(i)) for a <= i <= b (could be done in O(1)). Given [a, b] at the same layer this could efficiently give you the nearest layer of [a, b]'s descendants N([a, b]) = [c, d] with |c-d| > |a-b|. Now to compute the value of the subtree S rooted at n you can: Start with the interval I=[n, n] Use the nodes in I and it's descendants preceding N(I) to compute part of the value (could be done in O(1)) I = N(I) Repeat 2 or return the total value when done answered 13 Mar, 18:54 1 accept rate: 0%
 0 The solution I did was based on some observations. Initially if there is 1 node at depth 1,x1 nodes at depth 2,x2 nodes at depth 3,... . First observation is that you must assign higher co-efficients to higher depths Now the second observation is as follows : x1<=x2<=x3<=...<=xd . It is because of the perfect tree property. Third observation is if xi=xi+1=...=xj , put them in a group together. The maximum number of such groups <= 633. This is because in worst case all xi are strictly greater than previous by 1 which gives us 1+2+3+...x = 2e5, which gives max value of x as 633. Now if a group starts at depth st and ends at depth ed, with each depth having some ct nodes and there have been total of r nodes before depth st, then the value for the group is as follows : st * xr + st * xr+1 + ... + st * xr+ct-1 + (st+1) * xr+ct + ... + ed * xr+(ed-st+1)*ct-1. Now this can be simplified as : st * xr (1+x+x2+..+xct-1) + (st+1) * xr+ct (1+x+x2+..+xct-1) + ... + ed * xr+(ed-st)*ct (1+x+x2+..+xct-1) Taking the term (1+x+x2+..+xct-1) common you have as follows : (1+x+x2+..+xct-1) * (st * xr + (st+1) * xr+ct + ... ed * xr+(ed-st)*ct). The first term is a GP and the second is an AGP. Now this can be simplified using some math formulas and calculations, like noticing that the term (1+x+x2+..+xct-1) gets cancelled out with one of the denominators of DP and avoiding inverse by taking denominator separately at the end for all terms thus having only a single inverse call and memoizing power function calls for each query I made this solution pass. answered 13 Mar, 21:29 6★sdssudhu 1.1k●3●10 accept rate: 15%
 toggle preview community wiki:
Preview

### Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• link:[text](http://url.com/ "title")
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×733
×75

question asked: 13 Mar, 16:47

question was seen: 578 times

last updated: 13 Mar, 21:29