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 pre-calculated 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
https://www.codechef.com/viewsolution/21479865
1 Like
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
https://www.codechef.com/viewsolution/21524883
Idea Behind: I made a new vector in a way that it contains number of consecutive 1’s and 0’s
1 1 1 0 0 0 0 1 1
the vector would be: 3 -3 2 (1’s by positive value and 0’s by negative sum)
i kept the maximum abs(maximum sum) till now and used Deque and BANG! Solved
I hope my solution will help you understand
1 Like
I think there’s a slight mistake. the vector should be 3 -4 2 as I guess. Nice solution.
Can I get a C++ answer using this concept? Please. Thanks in advance.