CHEFSUBA - Editorial

editorial
, , ,
10

@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 CodeChef: Practical coding for everyone

11

https://www.codechef.com/viewsolution/13559652

solve this using priority queue and simple obserations

12

Thanks

13

@pkacprzak

Please check this solution, it doesn’t give the required answer on running!
Used the recursive Segment trees!

14

I solved this problem by precalculating all the possible answer as there cannot be more than N different answers.

here is my solution.

15

Any solution using deque??Please post!!!

16

https://www.codechef.com/viewsolution/13531464
I think it is better Approach ! :stuck_out_tongue:

17

I did this Question using sliding windows by precompute values and deque to get the maximum value

18

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.

Solution:
https://www.codechef.com/viewsolution/13519755

2 Likes
19

Here is my solution: CodeChef: Practical coding for everyone as same as author solution but I don’t know why my solution got wrong. Please tell me why I got wrong. Thank you.

20

One question guys!
Is the complexity O(n) for the entire subtask or O(n) for each querie?

21

Can someone tell me whats wrong with my code. I would be very greatful.
Submission : CodeChef: Practical coding for everyone

22

This Solution is giving TLE. I have used Segment Tree/ Range Maximum Query. Please share your insight.

23

A deque approach with window sliding and taking care of k>n condition and array sizes declaration gives an AC.
here is my easy to understand solution easy solution

24

I used trie CodeChef: Practical coding for everyone

25

i am using segment trees as said above . i am getting WA. please help me

https://www.codechef.com/viewsolution/13739007

26

can anyone explain this part
else the answer is the maximum sum we can obtain by starting the window from 1 to (n−k+1).

27

Someone please tell me why my code is giving SIGABRT
https://www.codechef.com/viewsolution/13742388

28

using namespace std;

include

define _ iosbase::syncwith_stdio(false);cin.tie(NULL);

define D(x) cout<< #x " = "<<(x)<<endl

int main() { _

int n;cin>>n;
int acum = 0;
int ans = 0;
int t;
for (int i = 0; i < n; ++i) {
cin>>t;
if (t == 0) {
ans = max(ans, acum);
acum = 0;
} else {
acum++;
}
}

ans = max(ans, acum);
cout<<ans<<endl;

return 0;
}

29

I have solved the same problem without using dequeue, segment tree or any sparse table.
I have done it just by checking the contribution of the shifted 1 during the shift if last digit is 1 into the new forward window formed using that new 1 and removing its contribution from the last window formed earlier using that 1 digit. Similar is in case of a 0. To maintain the counts of 1’s in the array used a multiset to store the counts of continuous 1’s in the array after the shift. Answer will be the largest value in multiset whenever query occurs.
Do check once!

https://www.codechef.com/viewsolution/13527132

Thanks