INSQ16C - Editorial

PROBLEM LINK:

Contest

Practice

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[U][level] becomes >= K . And if number of bit set is level < K till last level , answer -1.

TIME COMPLEXITY:

O((NLOG(N)) + (QLOG(N)))

SOLUTION:

Setter’s Solution

Can we do this using segment trees ??/

@admin is on a huge editing spree XD