PROBLEM LINK:
Author and Editorialist: Lalit Kundu
Tester: Kamil Debowski
DIFFICULTY:
medium
PREREQUISITES:
Segment Tree, Two pointer
PROBLEM:
You are given an array A_1, A_2, ..., A_N, where 1 \le A_i \le K, for all i. Also, there are Q updates. In each update, we make the change A_x = y. After each such update, you’ve to output the length of the smallest window in array A which contains elements of all types from 1 to K.
QUICK EXPLANATION:
======================
We build segment tree where each node maintains first and last occurences of each distinct element in that interval. Merge two nodes using two-pointer algorithm to find smallest window which contains all elements.
EXPLANATION:
================
As the constraints suggest, we’ll need something logarithmic in N and linear or log-linear in K. As always, we try to use segment trees! Let’s say we have some information(including answer) about two intervals i_1 and i_2, how can we quickly merge them to recalculate that information for merged interval? Note that answer of merged interval is minimum of (answer of i_1, answer of i_2, length of smallest window which starts in i_1 and ends in i_2 and contains all distinct elements). We need to find this window w which starts in i_1 and ends in i_2 and contains all distinct elements.
Claim: Let’s say j is the value at start of this optimal window. I claim that w starts at last occurence of j in i_1. Similarly, if j is the value at the end of this optimal window, then w ends at first occurence of j in i_2.
Proof: Let’s say the above was not true i.e. window started at a position p in i_1, with value j where j's last occurence wasn’t at this position. Then I could just move this window’s start ahead by one and still it’ll contain all distinct elements(since j has a second occurence after p), which means there is a contradiction. Similar logic can be applied from other end of window too.
So, we need to maintain only the 2K values per interval, position of first and last occurences of all elements from 1 to K. This information can very easily be reconstructed for the merged interal in O(K). Now, there are many ways you can find the smallest window among these positions which has all distinct elements. One way is to assume that window starts at position p and then iterate over all values i from 1 to K to find the closest occurence of i towards right of p. Doing this we’ll know which value was farthest and it’ll tell us smallest window which starts at p. This will take O(K^2). We need something better.
Why not just apply a two-pointer algorithm to find smallest window among these discrete points? We maintain two pointers pt_1 and pt_2, both of which start at the same position. We increment pt_2 until we have a valid window, then increment pt_1 until valid is valid and repeat the process. Whenever we have valid window, we evaluate to see if we’ve a better answer. Complexity of this algorithm is linear in number of points. However, to apply this we need to maintain acutal ordering of values at each interval and not just their positions.
COMPLEXITY:
================
O((N + Q)\text{ log } N * K), since in each update we merge O(\text{log }N) times and each merging step is O(K).