CHEFSUBA - Editorial

editorial
, , ,
2

this was a nice question and definitely not a easy one, I wonder how it got so many submissions,Please check for any cases of plagiarism or cheating.

3

i used a heap since i didn’t know segmented trees. and initially before rotation two pointers one at k-1(0 based) and n-1, subtract the pointers whenever rotation occurs and add n-1 whenever the become less than 0. Avoids the use of B.

4

I did exactly as above using segment trees and checked for many cases and it works perfectly

But my solution was getting WA in two tasks of first subtask. When I changed the place of declaration of the segment tree array, I got one AC but for one task it was still giving WA.

Can anyone help in finding what’s wrong. Thanks.

Here’s the solution link:

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

5

I solved this problem without using segment tree, heap, deques, sparse table or any other special data structure. CodeChef: Practical coding for everyone

1 Like
6

My segment tree solution was getting TLE. Here is the solution. Could someone please help in pointing out the error. Thanks in advance.

7

Solution:CodeChef: Practical coding for everyone
Concept:Sliding Window Maximum (Maximum of all subarrays of size K) - GeeksforGeeks
Time complexity: O(n)
Space complexity: O(n)(dynamic programming) + O(k) (for dequeue where k is frame size)
I converted this problem to one where we have to find maximum in window of size k along with principle of dynamic programming. Main task is you have to generate array containing total one’s in a window. You can see my solution. I got full 100 points.

2 Likes
8

@pmj642_coder

I think it is wrong because you have not checked the condition when k will be greater than equal to n.Correct me if i am wrong.

9

This was a great problem. I took the the deque approach after referring to this link. With some minor changes, and a check for k>n, it worked. For some reason though, my sub-task testcases were failing with the deque, so I had to use brute force for n<1000. Here’s my solution.

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