Problem Link
Author: Dmytro Berezin
Tester: Pawel Kacprzak and Misha Chorniy
Editorialist: Bhuvnesh Jain
Difficulty
EASY-MEDIUM
Prerequisites
Segment trees, Deque, Rotation trick
Problem
You are given an array A consisting of 0 and 1. You need to perform 2 type of queries of the array.
- Find the maximum number of 1's in the array covered by frame having size less than or equal to $k$
- Shift the array to the right by 1 element. (circular rotation)
Quick Explanation
Remove the rotation part in problem by duplicating the array. Pre-compute the answer for each window of size less than or equal to k. Use segment trees to answer the maximum in a range.
Explanation
Let 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 sub-arrays 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. (0-based 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 pre-compute the number of 1’s in window of size k for all sub-arrays 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 sub-arrays and each sub-array 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+k-1). 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.
sum[0] = 0
for i in 1 to k:
sum[i] = sum[i-1] + b[i]
for i in k+1 to 2*n:
sum[i] = sum[i-1] + b[i] - b[i-k]
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 (n-k+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