PROBLEM LINK:
Author: Vivek Bansal
Tester: Kush Khandelwal
Editorialist: Vivek Bansal
DIFFICULTY:
EASY-MEDIUM
PREREQUISITES:
Bitmasking , Dynamic Programming
PROBLEM:
Given a complete binary tree where each node a color associate with it .
For each query U & K, determine what is the minimum level at which number of distinct color nodes is greater than or equal to K under
the subtree rooted at U . If number of distinct color nodes under the subtree (of node U) < K , output -1.
EXPLANATION:
Since it’s a complete binary tree , then the number of levels in tree can be maximum LOG(N) = 17(approx)
where N = 10^5 in worst case.
Consider Node X and Level Y :
For a given node X and Level Y , we should know in O(1) that what is the number of distinct color nodes under the subtree
rooted at node X and upto Level Y .
This can be done simply with the help of dynamic programming and bitmasking.
Let’s say if you have the answer for the childs of a node X and you wish to contruct the DP[][] table for this node X .
Then , this could be computed for a given node while making dfs .
Now for answering an query U & K, Just iterate all the levels sequentially and break when number
of bit set in DP[level] becomes >= K . And if number of bit set is level < K till last level , answer -1.
TIME COMPLEXITY:
O((NLOG(N)) + (QLOG(N)))