PROBLEM LINK:Authors: Piyush Mehrotra DIFFICULTY:Medium PREREQUISITES:Basic know of Queue DataStructure, Sweg PROBLEM:There is a string of length L consisting of 2 kinds of characters, namely X and O on which we perform update operation of 2 types on substring[l,r]. Either we change all the characters of the substring to X or O. EXPLANATION:First, I will explain the second part of the problem, that is, to output the minimum number of toggles to transform the string(Assuming that all the updates are done). I will explain how to do the updates in the latter part of the explanation. We have to transform the string in such a way such that all the X if they occur, occur in the beginning. Lets take some ‘i’ in [0,L] (L denotes the length of string). Suppose that till ‘i’th index all the characters preceding it are X. So the number of toggles to transform the string will be sum of the number of O appearing at index j in [1,i] and number of X appearing at index j in [i+1,L]. We have to calculate the minimum of the sum for all i in [0,L]. This can be implemented in O(L) as follows
Now coming to the update part of the question, it can be easily be seen that for some ‘i’th element, if it comes in many a, l, r updates, then only the last update operation decides the final value of the element. So if we are able to get the highest index of the update query for every ‘i’th element, then we can easily find the final string. We can do that using segmenttree with lazy propagation or using priorityqueue in O(L*log(k)). We can also do this using queue and apply binarysearch on it. Here, I will explain the solution with priorityqueue so that even those who don’t know segmenttree can understand it.
Then we traverse this array and push the indices of the queries in the priorityqueue for which ‘i’ belongs to [l,r] and pop those indices for which i>r or i<l. I have done that by maintaining a boolean array (initially all true) as to mark all those indices ‘false’ whose ‘r’ is less than the present index i that we are on. The priorityqueue will sort the elements in it as we push the indices in the queue. The top element gives the highest index of the query of that type that covers that element. We will store all the highest index in an array(initially all elements are zero). Thus we can get the maximum index of the update due to change has taken place for all i in [1,L]. The following code is for type1 query.
Similarly we can do that for both the type of updates. Finally we can update our string in linear time O(L) just by traversing the string and changing it to X> highest index of ith element for type1 queries > highest index of ith element for type2 queries O> highest index of ith element for type2 queries > highest index of ith element for type1 queries Remains same> If both of the ith elements for type1 queries and type2 queries are zero
After the updates, we can find the minimum number of toggles as explained initially. Time Complexity:O(L + L*log(k)) AUTHOR'S SOLUTION:
This question is marked "community wiki".
asked 16 Mar '16, 14:12
