OAK - June Long 17 - Approach

general
, ,
1

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

Thanks!

2 Likes
2
  1. HLD decomposition of the branches of the tree
    1. 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.
    2. 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)
    3. Make tree[0] = root where 0 - is initial state.
    4. 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]
    5. Used one central node allocator for fast allocation of nodes
    6. 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.
9 Likes
3

Quick Explanation

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.

My Solution

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.

Min Tree

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.

Oak Tree

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

Building the Tree

  1. Perform HLD.
  2. 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.
  3. For each chain, create a mintree of initial value W'[u] := W[u].
  4. Insert that mintree to the oaktree at L_{chain[u]}.
  5. Set the root of the oaktree as state[0].

Query 1: Add x acorns to branch u.

  1. 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.
  2. 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.
  3. Otherwise, perform range decrease to all ancestors a (including u), W'[a] := W'[a] - x.

Query 2: Bird sits on branch u.

  1. 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].
  2. Reset nodes under u within the same chain by copying same range from state[0] to the current mintree of chain[u].
  3. 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]}].
  4. Update ancestor capacities. Increase all ancestors a (excluding u), W'[a] := W'[a] + acorns.

Complexity

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