please explain easy approach(except segment tree aproach) asked 19 May '17, 18:01

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. answered 19 May '17, 19:43

I have done this question in an easy way by using set and precalculating. Look at my submission https://www.codechef.com/viewsolution/13470150 Please let me know if you still have any doubt. answered 19 May '17, 19:48

This was what I did:
answered 19 May '17, 20:50
please explain logic behind steps.
(22 May '17, 00:38)
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(NK+1) time.
(22 May '17, 12:00)
Check my solution for better understanding. https://www.codechef.com/viewsolution/13483873
(22 May '17, 12:03)

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 NK+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
Remove windowCnt[base+NK] from ActiveWindows [ After shifting base+NKth window is Bad Window] Shift the base of the Window one step left base=(base+N1)%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.
Implementation : Source answered 19 May '17, 22:01

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[ik+1]=b[ik]+(A[i]A[ik]);because the only difference in kwindow starting from Ik and Ik+1 is A[Ik] in former is being replaced by a[I] in later. so just add A[I]A[Ik] in b[Ik] to get b[Ik+1]. now after taking whole array as input I have got array b til b[nk]. 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[nk+i+1]=b[nk+i]+(a[i]a[nk+i]); . now we have calculated no. of 1s in k size windows starting from every I(if window starts after nk 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 kwindows in decreasing order and m contains there respective starting point. take an end pointer l=n1. 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 n1 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 https://www.codechef.com/viewsolution/13623167 answered 19 May '17, 19:16
@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.
(22 May '17, 00:29)

No need for fancy tree. You can use a 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. answered 19 May '17, 20:16
please explain your code..
(20 May '17, 07:46)
See @manjrekarom29's comment, I believe our approaches are the same, except I used a map while he used a set.
(20 May '17, 08:42)

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. answered 19 May '17, 21:46

answered 19 May '17, 21:49

I used trie https://www.codechef.com/viewsolution/13584501 answered 20 May '17, 01:54
@jesaistout Can you explain how you used trie in this question?
(22 May '17, 00:30)

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 nk+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 answered 22 May '17, 14:44

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? answered 22 May '17, 15:10
