If you look at @l_returns code, you will see that he is calculating the values for all nodes.
B_V and S_V are nothing but corresponding values of node v. We already know a method to find these values for a node i. Just use (or recycle) it to find for node v.
Eg - We iterate from smallest to largest node and find B_S and S_S for them. If our node in question is child of node currently assigned a2, then these values become B_V and S_V respectively.
pair<ll,ll> dp[n];
for(int i=0;i<n;i++)
{
dp[i] = make_pair(end_idx[i]-start_idx[i]+1,query(segtree,0,n-1,0,start_idx[i],end_idx[i]));
update(segtree,0,0,n-1,start_idx[i]);
}
This is my code which calculates size of the subarray and number of nodes smaller than the node in its subarray. It’s working perfectly fine, I’ve checked it thoroughly.
Now please tell how do I calculate Bv and Sv from here.
to calculate Bt and St ? or Bs and Ss ?
Talking about functions find_c1, find_c2 and find_c3 ?
You are saying that Bv and Sv for node a2 (where v is one of a2’s children) is the same Bs and Ss for the node v ?
Yes, and thats what the editorial defined them as. If this is not clear to you then you havent understood the problem/editorial and are just mimmicking the implementation. I’d suggest to give it a read, and resolve this Q after a while.
1 Like
They are numbered in the order of increasing size. Please explain the meaning of this line.
Can you quote the exact line?
Every sentence make sense.Good job @vijju123 hope to see more editorials of you on some medium hard problem.
3 Likes
Chef’s restaurant system is a tree with NN vertices, where each vertex is one of his precious restaurants. Just like with Gordon’s restaurants, they are numbered in the order of increasing size.
Thats not in the editorial, but the problem statement. If the question is not clear then you can read the version in the editorial for clarity.