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

×

PTREE - Discussion

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

thesmartguy's gravatar image

4★thesmartguy
786
accept rate: 7%


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;

link

answered 13 Mar, 16:55

samarthtandon's gravatar image

4★samarthtandon
32
accept rate: 0%

edited 13 Mar, 16:56

will you (or) anyone explains what is wrong with this code: https://pastebin.com/CBzkhatT

(13 Mar, 17:45) thesmartguy4★

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) samarthtandon4★

I had 2 TLE / 11 AC with the following:

  1. 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].

  2. 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.

  3. 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:

  1. Start with the interval I=[n, n]
  2. Use the nodes in I and it's descendants preceding N(I) to compute part of the value (could be done in O(1))
  3. I = N(I)
  4. Repeat 2 or return the total value when done
link

answered 13 Mar, 18:54

bob_wonderland's gravatar image

4★bob_wonderland
1
accept rate: 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.

link

answered 13 Mar, 21:29

sdssudhu's gravatar image

6★sdssudhu
1.1k310
accept rate: 15%

toggle preview
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