Problem LinkAuthor: Dmytro Berezin Tester: Pawel Kacprzak and Misha Chorniy Editorialist: Bhuvnesh Jain DifficultyEASYMEDIUM PrerequisitesSegment trees, Deque, Rotation trick ProblemYou are given an array $A$ consisting of 0 and 1. You need to perform 2 type of queries of the array.
Quick ExplanationRemove the rotation part in problem by duplicating the array. Precompute the answer for each window of size less than or equal to $k$. Use segment trees to answer the maximum in a range. ExplanationLet us first remove the query regarding rotation from the problem. This is a known trick where we remove the rotation using duplication of the array. To consider this aspect, see this example below : Let array $A$ be $\{1, 0, 0, 1, 1\}$. Duplicate this array i.e. $\{1, 0, 0, 1, 1, 1, 0, 0, 1, 1\}$ and call it as $B$. Now, you can see that we can obtain all the arrays possible after rotation. They are just contiguous subarrays of length $n$ in the above array $B$. For example, after 2 rotations, we can consider the subarray from position 3 to 7 as the required array. (0based indexing) Now, for the rotation query, we just need to handle the starting position in the above array $B$. So, these queries can be handled in $O(1)$ Once, we have removed the rotations part from the problem, we can precompute the number of 1's in window of size $k$ for all subarrays in $B$. Also, since we want to maximise the number of 1's in the frame, we can always greedily chose frame of size $k$ only. Doing this in a naive way will take complexity $O(n^2)$, as we will loop over subarrays and each subarray will take $O(n)$ in worst case. We can using sliding window concept here to calculate the number of ones in all frames of size $k$. The logic behind this is as follows : First we compute the answer for all positions which are less the $k$. After that, suppose we want to find the answer for a position starting at, say $x$ and ending at $(x+k1)$. We see that only one element moves out of the window and only one element enters the windows as we slide it. Thus, these operations can be done in $O(n)$. Below is a pseudo code for it.
For the sample array $B$ given above and choosing $k = 3$, the sum array will look like $\{1, 1, 1, 1, 2, 3, 2, 1, 1, 2\}$. Now, once we have calculated all the above sums, the question just reduces to finding the windows with maximum sum. Now, if the window is of size greater than or equal to the array size, then the answer is always the number of ones in the array else the answer is the maximum sum we can obtain by starting the window from $1$ to $(nk+1)$. These range maximum queries can be easily with segment trees, sparse tables or in this specific cases using deques. For handling the above minimum queries using segment trees or sparse table, one can refer to this editorial at topcoder . For understanding a better algorithm, which uses deque and works in $O(n)$, one can refer to this problem from Spoj. Time Complexity$O(n \log{n})$, if using segment trees / sparse tables $O(n)$ if using deques Solution Links
This question is marked "community wiki".
asked 18 May, 13:46

Solution:https://www.codechef.com/viewsolution/13617713 Concept:http://www.geeksforgeeks.org/slidingwindowmaximummaximumofallsubarraysofsizek/ Time complexity: O(n) Space complexity: O(n)(dynamic programming) + O(k) (for dequeue where k is frame size) I converted this problem to one where we have to find maximum in window of size k along with principle of dynamic programming. Main task is you have to generate array containing total one's in a window. You can see my solution. I got full 100 points. answered 18 May, 16:22

O(n) solution can be done without deques, using frequency table to get the max. Since values are 0 and 1 only, the max value changes by at most 1. answered 19 May, 10:13

this was a nice question and definitely not a easy one, I wonder how it got so many submissions,Please check for any cases of plagiarism or cheating. answered 18 May, 15:32

i used a heap since i didn't know segmented trees. and initially before rotation two pointers one at k1(0 based) and n1, subtract the pointers whenever rotation occurs and add n1 whenever the become less than 0. Avoids the use of B. answered 18 May, 15:44

I solved this problem without using segment tree, heap, deques, sparse table or any other special data structure. https://www.codechef.com/viewsolution/13623167 answered 18 May, 16:05

My segment tree solution was getting TLE. Here is the solution. Could someone please help in pointing out the error. Thanks in advance. answered 18 May, 16:18

I think it is wrong because you have not checked the condition when k will be greater than equal to n.Correct me if i am wrong. answered 18 May, 16:44

This was a great problem. I took the the deque approach after referring to this link. With some minor changes, and a check for k>n, it worked. For some reason though, my subtask testcases were failing with the deque, so I had to use brute force for n<1000. Here's my solution. answered 18 May, 17:05

@devilhector use iterative segment trees recursive calls on such high constraints is not gonna work. I've used the same approach you can view my solution https://www.codechef.com/viewsolution/13613563 answered 18 May, 17:12
recursive gave me 100
(18 May, 17:27)
I don't know how u got but mine was giving sigsegv and tle error on the recursive one
(18 May, 17:39)

I took a different analytical approach that was O(n). I will post it in sometime when I have completed drafting it.