PROBLEM LINK:Practice Setter: Himanshu Mishra DIFFICULTY:Easy PREREQUISITES:Segment Tree, Deque. PROBLEM:Given a cyclic array $A$ of length $N$, with current position being the first element, Perform following operations.
SUPER QUICK EXPLANATION
EXPLANATIONFirst of all, let's see the brute force solution. We can actually shift the array in $O(N)$ time and for answering queries, we can iterate over the whole array again in $O(N)$ time, Giving Overall Time complexity $O(Q*N)$ which shall time out. Now, Let us focus on a faster solution. There are two (or even more) solutions, out of which, I am going to share a more general one, which has wider applications than the other, the Segment Tree solution. In Segment Tree, we usually store some information for a node, and we should be able to combine information of two child nodes to get the same information for the parent node. Segment Tree is simple, so, I'll be focusing more on finding the answer using segment tree. Segment tree resources are listed at the end. Let us call maximum length of contiguous 1s in a range $[l,r]$ as range max of $[l,r]$. Now, For this problem, to answer the query, we need the range max for a segment. Suppose we have it calculated the range max of two segments $[l, mid]$ and $[mid+1,r]$ and we need to combine this to calculate range max for segment $[l,r]$. But, the catch here is, that we cannot directly assume that maximum length of contiguous 1s in the range $[l,r]$ is just the maximum of range max of both children. Consider example: The array is 1 1 0 1 1 1 0 0 Assume l = 1, r = 8 and mid = 4. We see, that range max for $[l,mid]$ is 2 and $[mid+1,r]$ is 2, but range max of segment $[l,r]$ is 3. This happened because the left segment's suffix merged with the right segment's prefix to form a larger segment. The left child had a suffix length 1, and the right child had prefix length 2, which merged to form a segment of length 3. Hence, we also need to store the length of contiguous 1s at the start of the segment as well as at the end of the segment. Also, we need another variable telling whether a segment contains at least one 0 or not. The reason is, that if a segment does not contain 0 at all, this means that prefix and suffix are same as the length of a segment. This case needs to be handled specially. Now, we are ready to merge the information of two children to calculate the same information for the parent node. We need to consider all four cases, whether the left child contains 0, and whether the right child contains 0 or not. So, Here we go.
Proving the above is not hard, and this gives us a very neat and simple solution to solve the problem. Let us append the array to itself, so we get a new array $B$ of length $2*N$ with property that $B[i] = B[i+N] \forall i \in [0, N1]$. Now, Consider one by one, the segments $[0, N1]$, $[1, N]$, $[2, N+1]$ and so on. You can see, that it is basically the different shifts of the array. So, we can change the rotation to shifts in the array $B$. We can reformulate the problem as. Given an array $B$ of length $2*N$, we need to find maximum length of contiguous sequence between range $[P, P+N1]$ for a given $P$ This can be easily answered using the above segment tree. But as the problem says, we should report a segment only of length $\leq K$, we print $K$ if the length of the sequence we find is greater than $K$. This completes another Segment Tree problem. But we still need to practice segment trees, so here we go. An excellent blog on Segment tree here. A nice set of problems to practice we may find here. Alternative Implementations An alternate solution could be based on observation, that after handling the case in which array consists of 1 only, there will be at least two disjoint segments consisting of 1s only, considering First and Last elements to be neighbors. At any moment, due to shifting, only one of these segments can be split (divided due to the border). We can see, that we can find the maximum length of contiguous sequence containing 1 by considering the position of the shift, and making cases on basis of the position of largest two segments consisting of 1s only, which we can find beforehand. Time ComplexityTime complexity is $O((N+Q)*logN)$. $O(N*logN)$ for building Segment Tree while $(Q*logN)$ for processing answer queries. AUTHOR'S AND TESTER'S SOLUTIONS:Setter's solution Feel free to Share your approach, If it differs. Suggestions are always welcomed. :)
This question is marked "community wiki".
asked 09 Nov '18, 23:12

Question can be done in O(N+Q) by simply precomputing the first and second largest subsequence of 1's. Store the starting index and length of largest and second largest subsequence initailly itself. Then while processing the queries, simply check the conditions that whether the largest subsequence is in "rotation process", if it is, only then you have check the second largest subsequence and parts of the the largest subsequence(since it has been divided into 2 parts due to rotation). Thus each query takes O(1) as we already have the indices of the largest and second largest subsequence and lengths of both parts (if largest subsequence is under "process") can be obtained directly using them. My solution click here answered 15 Nov '18, 01:14

My solution in Python(link) basically uses the alternative implementation describe in the trailing paragraph above, finding the "main" and "spare" runs of $1$s on a circular view of the data array. Since the query limit is significantly bigger than the data array, I derive answers for all positions of the array, which gives a simple profile that dips down in the main run of $1$s. Then I can report out from a simple mark that is updated to keep track of where the break in the circle is. No rotation of the array is needed to derive this. answered 15 Nov '18, 00:38
Note that my competition answer didn't implement the answer array, but it makes the code a bit tidier and there is a small timing advantage.
(15 Nov '18, 01:17)
Rotation was just there to explain it carefully.
(17 Nov '18, 07:34)
@taran_1407 Yes, and I mentioned it here in case anyone reviewing my code wonders where it happens.
(17 Nov '18, 22:03)

Also can be done using brute force https://www.youtube.com/watch?v=T47EFVOJbgc&t= answered 15 Nov '18, 01:10

any reviews for this approach answered 15 Nov '18, 10:05

It's a little late but I think the solution to this problem is relatively simpler than described in the editorial. Ofcourse other approaches mentioned are also great. I simply precalculated and hashed the sequences of 1's and their sizes and beginning indexes. Sorted them so I get the largest sequences on one side. Then I pre calculated the result for each N, by simply checking if the pointer is outside, inside or at the edge of the largest sequence, the second largest and so on... The code is a little messy but the approach is very simple answered 19 Nov '18, 15:36

https://www.codechef.com/viewsolution/21524883 answered 26 Nov '18, 22:56
I think there's a slight mistake. the vector should be 3 4 2 as I guess. Nice solution.
(27 Nov '18, 00:04)

My approach same as @abhi2402 ,but still i am getting WA in 4 test case. Anybody help me ,what's wrong in my code??. This is my code: https://www.codechef.com/viewsolution/21471443 Thanks advance. answered 15 Nov '18, 08:56
@savaliya_vivek I tested your code locally and found that your method to find 1^{st} Max ans 2^{nd} Max is having bugs. Check out this Solution to find your error. rest is fine.
(15 Nov '18, 14:25)

why does my code get timed out please help me optimize my code without using segment trees please . my sad code answered 15 Nov '18, 21:49
1
Even though you are using deque, whenever there is a query of '?' type, your code takes O(N) time for getting the largest subsequence. For query of type '!', your code does shifting in O(1) time as you are using deque, but if there are lots of query of type '?' your code can take O(N*Q) time which easily exceeds the time limit. You can check my answer above for doing the problem in O(N+Q).
(15 Nov '18, 23:27)

https://www.codechef.com/viewsolution/21550313 did Without segment tree. Much easier to understand and short program. answered 17 Nov '18, 20:55

I used the same approach as @abhi2402 but it wasn't able to pass the 15th subtask. What could be the reason? Here's my code : https://www.codechef.com/viewsolution/21457380 answered 18 Nov '18, 17:09

i have tried this with Segment Tree as per the editorial,
i have build the segment tree for 2*N , but i am stuck at query part, can't figure out how to find the answer when the answer is the sum of suffix of left child and prefix of right child and not the max of both child; can anyone help me with this, and if possible can update the query function. answered 18 Nov '18, 19:54

without segment tree / set ... ( like a few others in the posts above) my solution (simple to understand as well) https://www.codechef.com/viewsolution/21655487 answered 19 Nov '18, 00:45

loved the editorial , was struggling a bit to fit segment tree in there .I know of the other approaches now but this is what I neeeded answered 21 Nov '18, 01:49

Can I get a C++ answer using this concept? Please. Thanks in advance. answered 12 Dec '18, 18:06

It can be done in $O(N+Q)$ as well. My Soln.
Segment tree is louv XD