How to solve 'F2. Lightsabers (medium)' from Codeforces?

binary-search
codeforces
medium
sliding-window
two-pointers

#1

Link to the problem: http://codeforces.com/problemset/problem/958/F2
I thought of doing it, this way: We need to find the smallest length subarray which has each light-saber either greater or equal to the requirement, then minimum deletion will be equal to the sum of extra light-saber of each type.

To implement this I thought of maintaining a prefix-sum array for each of the m light-saber, then using the prefix sum array and binary search we can find the "the smallest length subarray which has which has each light-saber either greater or equal to the requirement. However the time complexity of this solution will be O(M * N * log(N)) which will Time-Out for the given constraint.

What can be an optimal solution?


#2

Your thinking is very clear, but we may wish to think from another perspective, first solve some sub-questions, and consider the final choice of the interval is [1, R1] what is the minimum R1, then consider the final choice of the interval is [2, R2] what is the minimum R2, and so on, This is obvious that Rn >= Rn-1 >= … >= R2 >= R1, so we can use two-pointers to solve these sub-problems, so the overall time complexity is O(n).
sorry for my poor english :slight_smile:


#3

Thanks freeloop :slight_smile: