CFTREE - Editorial

In Rebuild function,for every node you iterate over node_update list.Then how can be rebuild() done in O(N)??

No link to submit the solutions on practice page. Please fix it.

tried using hld and matrix exponentiation, but unable to implement in given time.

Same here Naveen I too tried forming segment trees with chains but messed it up in between. A great problem btw and a really nice editorial as well.

@rednivrug15 I found your solution elegant. But i couldn’t get the idea behind ‘offset’ and the tree recurrence. Can you please explain it ?

Hello Guys !
Can someone tell me what is wrong with my code… I am getting WA But running time is under constraint.
Thanks!!

https://www.codechef.com/viewsolution/9230143

@sgoel01 how did you manage to submit? the submission is still closed to me.

Can anyone tell similar problems?

This approach is quite Nice, I feel…

And I haven’t ever heard of it!!

why some people have taken offset in fabonacci ?

as

int offset = 100005 or 100020;
fib[offset]=0;
     fib[offset+1]=1;
 
     for( int i=offset-1; i>=0; i-- ) {
        fib[i]=(fib[i+2]-fib[i+1]);
        if( fib[i]<0)
            fib[i] += mod;
     }
 
     for( int i=offset+2; i<3*N; ++i ) {
        fib[i]=( fib[i-1]+fib[i-2]);
        if( fib[i]>=mod )
            fib[i]-=mod;
     }

I think this problem can also be solved using segment tree with lazy propagation.

1 Like

Can somebody explain to me Meteora’s solution. It is elegant but i didn’t get the part with range update…and the reason for keeping 2 BITs.
here is the solution link . Also can anyone explain the way she has queried the tree. It appears that start and end value of a subtree is being updated in the bits. BUt the way it has been done is still cryptic to me.

Thanks in advance.

passing long long ints as argument gets you SIGSEV?

the only difference between these is the arguments of rebuild function … any explanation?

@admin No submission button in the problem page, please add

Author, Tester solution not visible like previous contest editorials :frowning:

2 Likes

Can you please add a little explanation about your solution? Thanks! :slight_smile:

1 Like

It is not. Either try relogin or delete cache. If none of it works, use this link to submit: CodeChef: Practical coding for everyone or open from codechef ide directly.

Instead of downvoting my comment, somebody can help me out.

Hi @kamta0425,

The submit option is coming on the link : Practice
or you can directly go to this link and submit : CodeChef: Practical coding for everyone

@admin @pushkarmishra Fix the link of all solutions given in Editorial otherwise it’s of no use.

2 Likes

I see a few people shared the code for nlogn solution, but people have some unanswered questions. I had to spent a day to finally solve this beautiful problem. So I will share my approach.

PREREQUISITES :

dfs in-out time , any range update point query data structure (Segment tree with lazy propagation)

OBSERVATION:
Let’s assume we wanted to support only the queries of type U x k , and finally print the whole tree. One way to solve this problem is, to store a pair<cur_fib_term, prev_fib_term> for each node, which is initialized as {0,0} for everyone. Now for query U x k, we will update
pair(x).cur_fib + fib[k] , pair(x).prev_fib + fib[k-1].
We can observe that in the end we will just need a bfs, and while transferring the pair from parent to child, we do similar to our update operation i.e.

pair(child).cur_fib += pair(parent).cur_fib , 
pair(child).prev_fib += pair(parent).prev_fib.

Now, we want to add another parameter to our update query , depth of the node x, and we want a fresh way to combine the two update queries. If depth is same for both the update queries, that means we are updating the same subTree, so we can still continue with our previous approach of adding cur , prev fib terms of the two queries. If the depth are different, we want to make depth same.
How do we shift a
{original_cur_fib, original_prev_fib , original_depth} to {new_cur_fib , new_prev_fib, new_depth}.
Let x = original_cur_fib , y = original_prev_fib , Now let’s see how they look, as their depth start increasing

cur : x , y
After 1 : x+y, x
After 2 : 2x+y, x+y
After 3 : 3x+2y , 2x+y
After 4 : 5x+3y , 3x+2y

So, after going d steps down, the same pair will look like
{ fib[d+1]*x + fib[d]*y, fib[d]*x + fib[d-1]*y }

Just how we went increasing depth, one can draw the other version of decreasing depth and find a similar kind of pattern .
So, now we know, how to make depth of two equal, and hence we know how to combine.
So if we can keep a triplet {x,y,d} for each node of the tree, in the end, we query the current node, and shift the result to the depth we need , and print the result.
Implementation