KRYP2 - Editorial

editorial
, , , , , ,
1

[Contest][1]
[Practice][2]

Author: [Shivam Garg][3]
Tester: [Shiv Dhingra][4]

DIFFICULTY

MEDIUM HARD

PREREQUISITES

Mo’s on Trees

PROBLEM

Given a tree, for each query comprising a path in the tree, it is required to answer the minimum absolute difference between any two distinct nodes on that path.

EXPLANATION

In order to solve this problem, Mo’s algorithm on trees can be implemented.
In order to gain more insight into this algorithm, refer this [excellent source][5].

As explained in the above-mentioned post, we, first of all, need to flatten the tree and compute the inTime[ ] and outTime [ ] via DFS. Mo’s algorithm can be implemented over this contiguous interval.

Now, according to the algorithm, queries can be computed, as we do not count the nodes which appear twice.

Now, in order to compute the minimum absolute difference of squared value between any 2 distinct nodes, there are various ways.

One of them is via the use of 2 multisets. The first multiset stores the squared values of the nodes. The second multiset stores the difference between closest/adjacent values in the first multiset.

In case a new element is inserted into multiset 1, not more than 2 new differences will be generated. These will be inserted in multiset 2. The same case holds when an element has to be deleted from multiset 1.

The answer to each query is the first element of multiset 2.

This question can also be solved by the use of Segment Tree. Whenever an element is to be inserted or removed, carry out the update operation in segment tree. Also, at each node compute the minimum absolute difference of the squared value between its constituent leaf nodes.

The complexity of multiset/segment tree is O(Log (N)), and that of Mo’s on Trees algorithm is O(Q \sqrt{N}). So, the overall complexity turns out to be O(Q \sqrt{N}Log (N)).

SOLUTION

Setter’S Solution -


[6]


  [1]: https://www.codechef.com/CODR2018/problems/KRYP2/
  [2]: https://www.codechef.com/problems/KRYP2/
  [3]: http://codechef.com/users/shivamg_isc
  [4]: http://codechef.com/users/lucifer2709
  [5]: http://codeforces.com/blog/entry/43230
  [6]: https://www.codechef.com/viewsolution/17468445
2 Likes