please explain easy approach(except segment tree aproach)
ok, I have not used segment tree or any other special data structure.
what I have done is, I first calculated and stored(in array b) no. of 1s in windows of size k starting from every index in the given array A.
for that, when taking inputs in array A, for first k elements count no. of 1s. and assign that to b[0] (1s in k window starting from 0). then for remaining inputs do this
b[i-k+1]=b[i-k]+(A[i]-A[i-k]);because the only difference in k-window starting from I-k and I-k+1 is A[I-k] in former is being replaced by a[I] in later. so just add A[I]-A[I-k] in b[I-k] to get b[I-k+1]. now after taking whole array as input I have got array b til b[n-k]. for remaining values run a loop from 0 to k and update b values for last k windows using first k values of A(imagine array as circular so first element occurs after last element) in the same way by b[n-k+i+1]=b[n-k+i]+(a[i]-a[n-k+i]); .
now we have calculated no. of 1s in k size windows starting from every I(if window starts after n-k it takes a circular turn from nth element to 1st element of array, remember array is circular). now take another index array m for which m[I]=I;. sort array b in decreasing order, and while sorting change corresponding elements of m in same way as elements of b(or u can use vector of integer pairs also) so that m[I] always represents starting position of window b[I].
now, array b contains no. of 1s in all the k-windows in decreasing order and m contains there respective starting point. take an end pointer l=n-1. start taking query string as input. if query is ‘!’ decrease the end position , l–(if l becomes negative add n to it so that it comes at n-1 again, because its all circular). If query is ‘?’ , start looping for array b. check for first element(which has most no. of 1s clearly) that, if that window is completed before end position(m[i]+k<=l) then print that. else if l comes in middle of the window that means the window is divided into two parts(one part in the end and other in the start). so check next b[i] until you get a complete window. my solution CodeChef: Practical coding for everyone
The question was quite simple and stated the window of K size out of N - K + 1 possible combinations to have maximum number of ONES.
Firstly for L = 0, R = N - 1, calculate number of Ones of 1st K windows. Keep the maximum and maintain maximum of all values in Kth window using either
1. Max Heap
2. RB Tree Mapping(TreeMap in Java) (The one I used)
3. Priority Queue.
So that the max is always maintained at the top and ‘?’ query can be executed in O(1).
Now coming to the shifting query. There was a common observation that suppose for N = 5, K = 3.
Initially, the Kth window were (0, 2), (1, 3), (2, 4)
Then on 1st Shift it would be (4 , 1), (0, 2), (1, 3)
On Third Shift, it would be (3, 0), (4, 1), (0, 2)
If you closely pay attention in all the iterations, the windows are
1st. (A, B, C)
2nd. (D, A, B)
3rd. (E, D, A)
having a cyclic order of insertion from left and pop() from right and adding the new window which is (L, R)
where L = lastwindow.R, R = (lastwindow.R + K - 1) % N .
So you had to use a Deque for this operation. I hope you understand about Deque and its operations.
Simple optimization tip would be to check
- If popValue != insertValue only then insert in MaxHeap/ ProrityQueue because insert operations are costly.
- Maintain a cumulative array for number of Ones.
Using this algorithm gave me an AC in 0.10 secs in java Code Link
1 Like
I have done this question in an easy way by using set and precalculating.
Look at my submission CodeChef: Practical coding for everyone
Please let me know if you still have any doubt.
1 Like
No need for fancy tree. You can use a map (or multiset) to act as a counter for the window.
The maximum can be retrieved easily by getting the last entry in the map. When you slide the window, add 1 to the count of the value. Remove the value by decreasing the count. If count becomes zero, erase that value.
someone please post an easy solution
1 Like
This was what I did:
- Find initial answer for K-windows.
- Store this in an array. Assume the array to be a circular queue.
- Store initial max and its maxIndex from the array.
- Simultaneously create a set for this array (a c++ container which is a balanced binary tree meaning O(log n) search time).
- Now everytime you perform a rotate operation only recalculate the last element or the rear of circular queue. Move the front to position of rear and new rear to be rear-1.
- Now add and remove respective elements from set.
- If at all the recalculation that was performed was on the maxIndex then use set to find new max else just return whatever maxIndex points to.
1 Like
https://www.codechef.com/viewsolution/13456694
Check my code. If string is abcde after one shift it will be eabcd, after two shift, deabc etc. After 4 switch answer will repeat. So create new string bcdeabcde. In this string say you need window of size 3, find answer for each 3 size segment. bcd, cde, dea etc. Then see you need maximum in string where string size is 5. So compare answer between three segment collection bcd cde dea, cde dea eab etc. Each of these segment will be answer for bcdea, cdeab etc. Keep track of number of shift so far (shift count mod 5) and print answer.
First, a cumulative array can be used to count number of 1’s between a range.
Terms Used -
base = Current starting index in the array. i.e. NewArray[i] = A[(base+i)%N] (Wrapping Horizontally)
We are not generating NewArray, A is the original Array.
windowCnt[i] = Number of 1’s in Window of size K Starting from ith index towards right (Wrapping Horizontally) [Calculated in O(1) ]
ActiveWindows = {windowCnt[i] | For first N-K+1 windows} [Total Insertion time O(N) ]
ActiveWindows contains values of windowCnt of all Possible windows of size K at any moment (All Good Windows at a time)
Now for each query
- If ‘!’ => [ O(lg(N)) + O(1) + O(lg(N)) ]
Remove windowCnt[base+N-K] from ActiveWindows [ After shifting base+N-Kth window is Bad Window]
Shift the base of the Window one step left base=(base+N-1)%N (cyclic manner)
Add windowCnt[base] into ActiveWindows [base is updated baseth window is New Good Window]
Good Window depends on if we simply shifted elements as given in problems then at any moments the windows which can be generated of size K are Good windows.
- otherwise => Get maximum Value from ActiveWindows [ O(lg(N)) ]
Implementation : Source
1 Like
initially accumulate the number of 1’s captured by a frame for eaach starting position (assume the entire queue to be cyclic due to cyclic insertions)
now prepare n array of answers by comapring n-k+1 elements in consecutive to calculate for each shift. (there is a O(n) method to do this )
now to solve the queries,you increment the pointer i to rotate and print the output of s[i] on question
Since we had to give the maximum number of 1’s that could contigously appear, can we not do it like:
Calculate the maximum number of contigous 1’s in the whole array. Then if that number > k, then return k as answer otherwise the actual number obtained?
please explain your code…
See @manjrekarom29’s comment, I believe our approaches are the same, except I used a map while he used a set.
@theprk Can you tell me what is the time complexity of your solution?. According to me it is O(q*n + nlogn). This shouldn’t pass.
please explain logic behind steps.
You have to find max number of 1s captured by a window of size K. Find the sum of K windows for initial array (by calculating cumulative sum). Store this in an array we will use as a Circular queue with front at 0 and rear at last element.
Also at times you shift everything right by 1. When this happens only last element of your Cqueue changes and rest just shift forward. Try this on paper and you can see it.
Now you need to minimise time to find maxSum. This can be done by storing Cqueue elements in a set. So you can fetch max in log(N-K+1) time.