HMAPPY1 - EDITORIAL

general
, , , , ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2

Setter: Himanshu Mishra
Tester: Zhong Ziqian
Editorialist: Taranpreet Singh

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.

  • ! Shift all elements to the right and make the last element as the first element.
  • ? print the maximum number of consecutive 1s in the array. In case the answer is more than K, print K.

SUPER QUICK EXPLANATION

  • The value of K is irrelevant. We just need to calculate the longest contiguous sequence of 1s after any number of shifts.
  • If we append an array to itself, the problem reduces to, Given a sequence of length 2*N, we need to answer the maximum length of the contiguous sequence of 1s in the range [pos, pos+n-1].
  • We can use Segment Tree to calculate this, storing information for every node in segment tree [l,r] (Max length of consecutive ones in range l to r, Number of 1s at prefix of [l, r], Number of 1s at suffix of [l, r] and whether the segment contains a zero at all.)
  • We can maintain a shift pointer which, on every shift query, moves one step to the left, and in case it is already at position 0, it moves to position N-1. This way, answer to every query is same as the answer to query [shuft, shift+N-1] to above segment tree.

EXPLANATION

First 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.

  • If both left and right child do not contain 0, we see, that the range consists of all 1s, hence, prefix, suffix as well as range max are equal to the length of the segment.
  • If only left child contains 0, we can see, that by merging, prefix of left child become prefix of parent, suffix of parent is the length of right child plus suffix of left child, and range max is maximum of range max of both segments, and the segment length formed by merging suffix of left child with whole right segment.
  • If only right child contains 0, we can see, that prefix of the parent is formed by merging whole left child with the prefix of right child, and suffix of the parent is just the suffix of right child. The range max is the maximum of range max of both segments, as well as the maximum of segment length formed by merging whole left child with the prefix of the right child.
  • Now, Both child contains 0, Then we see, that prefix of left child become prefix of parent, suffix of right child become suffix of parent, and range max of segment is maximum of range max of both segments, and the segment formed by merging suffix of left child and prefix of right child.

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, N-1]. Now, Consider one by one, the segments [0, N-1], [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+N-1] 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 Complexity

Time 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
Testerā€™s solution
Editorialistā€™s solution

Feel free to Share your approach, If it differs. Suggestions are always welcomed. :slight_smile:

2

It can be done in O(N+Q) as well. My Soln.

2 Likes
3

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.

1 Like
4

Also can be done using brute force https://www.youtube.com/watch?v=T47EFVOJbgc&t=

1 Like
5

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

4 Likes
6

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.

7

Segment tree is louv XD

8

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.

9

any reviews for this approach
I consider connected components and then update them as per query and return max of sizes of connected component.

=> https://www.codechef.com/viewsolution/21573122

1 Like
10

@savaliya_vivek I tested your code locally and found that your method to find 1st Max ans 2nd Max is having bugs. Check out this Solution to find your error. rest is fine.

11

why does my code get timed out please help me optimize my code without using segment trees please . my sad


[1]


  [1]: https://www.codechef.com/viewsolution/21620274
12

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).

1 Like
13

Rotation was just there to explain it carefully.

14

Well, thatā€™s the alternate Implementation.

15

https://www.codechef.com/viewsolution/21550313
did Without segment tree.
Much easier to understand and short program.

16

@taran_1407 Yes, and I mentioned it here in case anyone reviewing my code wonders where it happens.

17

I used the same approach as @abhi2402 but it wasnā€™t able to pass the 15th sub-task. What could be the reason? Hereā€™s my code : https://www.codechef.com/viewsolution/21457380

18

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;
someone guided me to return a node rather than the answer for each query, i tried it but canā€™t get the idea how to return the node.
Hereā€™s my code : https://ideone.com/vG4Xo3

can anyone help me with this, and if possible can update the query function.

19

please someone help me find error in my codeā€¦thanks in advance

code link

20

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