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 lightsaber either greater or equal to the requirement, then minimum deletion will be equal to the sum of extra lightsaber of each type. To implement this I thought of maintaining a prefixsum array for each of the m lightsaber, then using the prefix sum array and binary search we can find the "the smallest length subarray which has which has each lightsaber either greater or equal to the requirement. However the time complexity of this solution will be O(M * N * log(N)) which will TimeOut for the given constraint. What can be an optimal solution? asked 28 May '18, 00:33

Your thinking is very clear, but we may wish to think from another perspective, first solve some subquestions, 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 >= Rn1 >= ... >= R2 >= R1, so we can use twopointers to solve these subproblems, so the overall time complexity is O(n). sorry for my poor english :) answered 28 May '18, 13:40
