Can anyone explain the approach to solve problem PERSISTENT OAK(OAK) from the June Long Challenge 17 ?

Thanks!

Can anyone explain the approach to solve problem PERSISTENT OAK(OAK) from the June Long Challenge 17 ?

Thanks!

2 Likes

- HLD decomposition of the branches of the tree
- the bst tree for the whole tree (not for subbranch) when building bst swap children to make sure heavy branch continues first, that creates ability to set/zero/add correct subbranch range!

3. tin/tout index contains nodes once, heavy first. [tin-tout] embraces whole sub-tree. - Build persistent segment tree on the index above (nodes include current sum, add value that need to be added, minimum capacity in the range and index of this element)
- Make tree[0] = root where 0 - is initial state.
- Use several special flags:

a. zero means this node zeroed. but children yet to be zeroed

b. add - already added to this node but need to be added to children

c. rcap - need to reevaluate minimum capacity and index

d. zero , rcap and add never set on a leaf.

e. pn0 - pointer on initial version of the node (it has right capacity and children)

f. when zeroing node - just create new node instead cloning pn0 as source.

7. The operations on tree: get_min_cap [l,r] , get_sum [idx] , add_val [l,r] , set_zero [l,r] - Used one central node allocator for fast allocation of nodes
- Run through queries. Copy source state pointer into tree[new_state] before doing commands

while doing command use tree[new_state] and reassign to it if new root pointer returned

10.Carefully check that trough 3 out of 4 commands (zero, add, getcap; getsum) new nodes may be constructed and returned including getcap - as lazy propagation may require construction of the new node.

11.When adding values - first check if the capacity is sufficient, check on every HLD segment from the node to the root of the whole tree. If not sufficient on particular segment, and index x returned - then recheck [x+1, n], as another minimum below x can be hiding in the shadow of global minimum.

- the bst tree for the whole tree (not for subbranch) when building bst swap children to make sure heavy branch continues first, that creates ability to set/zero/add correct subbranch range!

9 Likes

I did persistent segment tree with Heavy-Light Decomposition, with a range copy functionality. We do range min to look for branch to cut, and range copy form state[0] to perform the cut.

I used two trees for this: a range-min tree of acorn capacity (per HLD chain) and a tree based on the DFS-order of the chains. Let’s call the former the mintree and the latter the oaktree.

The mintree contains the capacity of a branch. Initially, the value at a branch u is W[u]. Note: a negative value of the mintree means that a branch can’t hold capacity, so it is cut.

The oaktree is a **meta segment tree** of the mintree. This is built in DFS-order (aka Euler Tour) of the chains. For example, if node u lives in chain[u], we can store the whole subtree of chain[u] located in some range [L_{chain[u]}, R_{chain[u]}] in the tree. Here, L_{chain[u]} refers to the current chain, and the value there is the root of the persistent mintree at chain[u]. Chains below will be at the range [L_{chain[u]} + 1, R_{chain[u]}].

- Perform HLD.
- While building the HLD chains, take note of the order during DFS. Set L_{chain[u]} as the enter time, R_{chain[u]} for exit.
- For each chain, create a mintree of initial value W'[u] := W[u].
- Insert that mintree to the oaktree at L_{chain[u]}.
- Set the root of the oaktree as state[0].

**Query 1**: Add x acorns to branch u.

- First, we need to know which branch will fall. Upwards, we search for the deepest ancestor a such that W'[a] < x. We can perform binary search to get this value.
- If index exists, do query 2 on node a to “cut” the branch. Observe that cutting a branch is the same as making a bird sit.
- Otherwise, perform range decrease to all ancestors a (including u), W'[a] := W'[a] - x.

**Query 2**: Bird sits on branch u.

- Get number of acorns that will fall. This is simply the change in capacity so we can get this using a point update on the mintree. Let acorns := W[u] - W'[u].
- Reset nodes under u within the same chain by copying same range from state[0] to the current mintree of chain[u].
- Reset nodes under u that are on different chains by copying the oak tree from state[0] at [L_{chain[u]} + 1, R_{chain[u]}].
- Update ancestor capacities. Increase all ancestors a (excluding u), W'[a] := W'[a] + acorns.

For query 1, accessing a mintree is O(log N). There is one mintree per chain and there are O(log N) chains so doing both becomes O(log^2 N). For query 2, we only replace O(log N) nodes during range copy and we only access a single mintree. Total runtime is O(Q log^2 N).

Remember to do everything persistently, so make sure every update needs to return a new tree. Hope that was helpful. Here’s link to solution.

5 Likes