You are not logged in. Please login at www.codechef.com to post your questions!

×

CHEFSUBA - Editorial

4
10

Problem Link

Practice

Contest

Author: Dmytro Berezin

Tester: Pawel Kacprzak and Misha Chorniy

Editorialist: Bhuvnesh Jain

Difficulty

EASY-MEDIUM

Prerequisites

Segment trees, Deque, Rotation trick

Problem

You are given an array $A$ consisting of 0 and 1. You need to perform 2 type of queries of the array.

  1. Find the maximum number of 1's in the array covered by frame having size less than or equal to $k$
  2. Shift the array to the right by 1 element. (circular rotation)

Quick Explanation

Remove the rotation part in problem by duplicating the array. Pre-compute the answer for each window of size less than or equal to $k$. Use segment trees to answer the maximum in a range.

Explanation

Let us first remove the query regarding rotation from the problem. This is a known trick where we remove the rotation using duplication of the array. To consider this aspect, see this example below :

Let array $A$ be $\{1, 0, 0, 1, 1\}$. Duplicate this array i.e. $\{1, 0, 0, 1, 1, 1, 0, 0, 1, 1\}$ and call it as $B$. Now, you can see that we can obtain all the arrays possible after rotation. They are just contiguous sub-arrays of length $n$ in the above array $B$. For example, after 2 rotations, we can consider the subarray from position 3 to 7 as the required array. (0-based indexing)

Now, for the rotation query, we just need to handle the starting position in the above array $B$. So, these queries can be handled in $O(1)$

Once, we have removed the rotations part from the problem, we can pre-compute the number of 1's in window of size $k$ for all sub-arrays in $B$. Also, since we want to maximise the number of 1's in the frame, we can always greedily chose frame of size $k$ only. Doing this in a naive way will take complexity $O(n^2)$, as we will loop over sub-arrays and each sub-array will take $O(n)$ in worst case. We can using sliding window concept here to calculate the number of ones in all frames of size $k$. The logic behind this is as follows :

First we compute the answer for all positions which are less the $k$. After that, suppose we want to find the answer for a position starting at, say $x$ and ending at $(x+k-1)$. We see that only one element moves out of the window and only one element enters the windows as we slide it. Thus, these operations can be done in $O(n)$. Below is a pseudo code for it.

sum[0] = 0 for i in 1 to k: sum[i] = sum[i-1] + b[i] for i in k+1 to 2*n: sum[i] = sum[i-1] + b[i] - b[i-k]

For the sample array $B$ given above and choosing $k = 3$, the sum array will look like $\{1, 1, 1, 1, 2, 3, 2, 1, 1, 2\}$.

Now, once we have calculated all the above sums, the question just reduces to finding the windows with maximum sum. Now, if the window is of size greater than or equal to the array size, then the answer is always the number of ones in the array else the answer is the maximum sum we can obtain by starting the window from $1$ to $(n-k+1)$. These range maximum queries can be easily with segment trees, sparse tables or in this specific cases using deques.

For handling the above minimum queries using segment trees or sparse table, one can refer to this editorial at topcoder . For understanding a better algorithm, which uses deque and works in $O(n)$, one can refer to this problem from Spoj.

Time Complexity

$O(n \log{n})$, if using segment trees / sparse tables

$O(n)$ if using deques

Solution Links

Setter's solution

Tester's solution

Editorialist solution

This question is marked "community wiki".

asked 18 May, 13:46

likecs's gravatar image

6★likecs
3.1k636
accept rate: 9%

edited 18 May, 22:44

I took a different analytical approach that was O(n). I will post it in sometime when I have completed drafting it.

(18 May, 16:57) c0d3_k1ra3★

Solution:https://www.codechef.com/viewsolution/13617713 Concept:http://www.geeksforgeeks.org/sliding-window-maximum-maximum-of-all-subarrays-of-size-k/ 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.

link

answered 18 May, 16:22

rj25's gravatar image

3★rj25
432
accept rate: 0%

edited 19 May, 12:00

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

link

answered 19 May, 10:13

hikarico's gravatar image

6★hikarico
1.7k414
accept rate: 26%

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.

link

answered 18 May, 15:32

yash_22's gravatar image

4★yash_22
213
accept rate: 0%

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.

link

answered 18 May, 15:44

simha's gravatar image

3★simha
1315
accept rate: 0%

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

link

answered 18 May, 16:01

pmj642_coder's gravatar image

2★pmj642_coder
1
accept rate: 0%

Take k = min(k, n); it will give AC. Since there was no contraint on the value of K. This was necessary.

(18 May, 16:28) ssaxena365★

Bro, Just take the case when k>n. Constraints on k were not mentioned. hence this was the only possibility left. Now, you would be laughing on yourself. Me too, but luckily I figured out this in 2 days.

(18 May, 18:10) swamicoder4★

Woah, you're all right, actually the site went under maintenance when I submitted previously and it didn't show the WA in the task. Now, I made the change and its working (all AC's). Thanks guys. Lol ... hours of debugging and missed this one.

(18 May, 23:24) pmj642_coder2★

I solved this problem without using segment tree, heap, deques, sparse table or any other special data structure. https://www.codechef.com/viewsolution/13623167

link

answered 18 May, 16:05

theprk's gravatar image

4★theprk
1
accept rate: 0%

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

link

answered 18 May, 16:18

devilhector's gravatar image

3★devilhector
384
accept rate: 12%

edited 18 May, 16:44

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

link

answered 18 May, 16:44

deepansh_946's gravatar image

2★deepansh_946
456
accept rate: 0%

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.

link

answered 18 May, 17:05

arvindpunk's gravatar image

3★arvindpunk
311
accept rate: 0%

edited 18 May, 17:06

@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 https://www.codechef.com/viewsolution/13613563

link

answered 18 May, 17:12

yash_22's gravatar image

4★yash_22
213
accept rate: 0%

recursive gave me 100

(18 May, 17:27) sanket4074★

I don't know how u got but mine was giving sigsegv and tle error on the recursive one

(18 May, 17:39) yash_224★

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

solve this using priority queue and simple obserations

link

answered 18 May, 17:41

sidd845's gravatar image

4★sidd845
254
accept rate: 0%

Thanks

link

answered 18 May, 18:31

saurabh0612's gravatar image

3★saurabh0612
101
accept rate: 0%

@pkacprzak http://ideone.com/5xdql7 Please check this solution, it doesn't give the required answer on running! Used the recursive Segment trees!

link

answered 18 May, 19:28

tni_md's gravatar image

4★tni_md
111
accept rate: 0%

edited 18 May, 19:29

Please check this solution @chaitya_62

(22 May, 00:10) tni_md4★

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

here is my solution.

link

answered 18 May, 19:58

chaitya_62's gravatar image

4★chaitya_62
1445
accept rate: 16%

Any solution using deque??Please post!!!

link

answered 18 May, 22:12

anilkumar1998's gravatar image

4★anilkumar1998
111
accept rate: 0%

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

link

answered 18 May, 23:39

hugewarriors's gravatar image

3★hugewarriors
111
accept rate: 0%

edited 18 May, 23:40

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

link

answered 19 May, 09:20

ravidelcj's gravatar image

4★ravidelcj
10139
accept rate: 16%

Here is my solution: https://www.codechef.com/viewsolution/13634699 as same as author solution but I don't know why my solution got wrong. Please tell me why I got wrong. Thank you.

link

answered 19 May, 14:26

vdn1999bxvp's gravatar image

3★vdn1999bxvp
11
accept rate: 0%

edited 19 May, 14:58

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

link

answered 19 May, 19:16

ashishsb95's gravatar image

2★ashishsb95
1
accept rate: 0%

Can someone tell me whats wrong with my code. I would be very greatful. Submission : https://www.codechef.com/viewsolution/13640002

link

answered 20 May, 12:52

rks_mak's gravatar image

2★rks_mak
1
accept rate: 0%

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

link

answered 20 May, 22:52

abhiroj786's gravatar image

2★abhiroj786
8110
accept rate: 22%

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

link

answered 21 May, 10:10

ashishsb95's gravatar image

2★ashishsb95
1
accept rate: 0%

link

answered 21 May, 15:21

jesaistout's gravatar image

2★jesaistout
1
accept rate: 0%

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

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

link

answered 23 May, 13:59

tarun_174's gravatar image

2★tarun_174
1
accept rate: 0%

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

link

answered 23 May, 14:16

tarun_174's gravatar image

2★tarun_174
1
accept rate: 0%

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

link

answered 23 May, 16:29

uddhav_2509's gravatar image

3★uddhav_2509
1
accept rate: 0%

using namespace std;

include<bits stdc++.h="">

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

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

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&lt;<endl;< p="">

return 0; }

link

answered 23 May, 17:25

rida_doudou's gravatar image

0★rida_doudou
1
accept rate: 0%

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

link

answered 23 May, 17:31

jainsameeksha's gravatar image

3★jainsameeksha
51
accept rate: 0%

edited 23 May, 17:37

Can someone help me with my code, I'm getting WA in 2 test cases - one from small and one from large I've checked the condition for k>n using k = min(k,n).

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

link

answered 23 May, 18:27

manasjoshi's gravatar image

2★manasjoshi
1
accept rate: 0%

what will the size of sum array?

link

answered 25 May, 00:47

shashank0j's gravatar image

2★shashank0j
1
accept rate: 0%

Why do I get a SIGSEV error on exactly one of the testcases? All the others are AC. I used two sliding windows.

Code here

link

answered 25 May, 13:39

potatio's gravatar image

3★potatio
111
accept rate: 0%

Can anyone reply with side cases and all the test cases you prepared for this problem. I need to run the code on those as its giving a WA. If anyone is willing to look at the code here is the link: https://www.codechef.com/viewsolution/13789471 The code is simple with no use of special data structures, easy to check. Thank you in advance :)

link

answered 26 May, 15:16

rohitthapliyal's gravatar image

3★rohitthapliyal
132
accept rate: 0%

Now its done. Still gives TLE in 3-4 cases. Code: https://www.codechef.com/viewsolution/13789884

link

answered 26 May, 16:11

rohitthapliyal's gravatar image

3★rohitthapliyal
132
accept rate: 0%

My code is giving NZEC in certain cases. Can anyone please help why is this happening?

class CHEFSUBA { public static void main(String[] args) throws IOException { boolean readFromFile = false; boolean outputToFile = false;

    CustomInputOutputClass cio = new CustomInputOutputClass(readFromFile, outputToFile);

    int[] temp = cio.readIntegerArrayFromSingleLine();
    int n = temp[0];
    int k = temp[1];
    int p = temp[2];
    int[] origArr = cio.readIntegerArrayFromSingleLine();
    String queryString = cio.readString();

    ArrayList<Integer> answerList = new ArrayList<Integer>();
    int length = origArr.length;
    int[] arr = new int[2 * length];
    int arrLength = 2 * length;
    int[] maxArray = new int[arrLength - k + 1];

    for(int i = 0; i < 2 * length; i++)
    {
        arr[i] = origArr[i % length];
    }
    for(int i = 0; i < length; i++)
    {
        int t = arr[i];
        arr[i] = arr[2 * length - 1 - i];
        arr[2 * length - 1 - i] = t;
    }

    int count = 0;
    for(int i = 0; i < k; i++)
    {
        count = count + arr[i];
    }
    maxArray[0] = count;

    for(int i = 1; i < arrLength - k + 1; i++)
    {
        maxArray[i] = maxArray[i - 1] - arr[i - 1] + arr[i + k - 1];
    }

    /*
    for(int x: maxArray)
        System.out.print(x + "\t");
    System.out.println();
    */

    Deque<Integer> deque = new LinkedList<Integer>();

    for(int i = 0; i < length - k + 1; i++)
    {
        if(deque.isEmpty())
            deque.addFirst(i);
        else
        {
            if(maxArray[i] < maxArray[deque.getLast()])
                deque.addLast(i);
            else
            {
                while(!deque.isEmpty() && maxArray[deque.getLast()] <= maxArray[i])
                    deque.removeLast();
                deque.addLast(i);
            }
        }
    }

    //for(int x: deque)
    //  System.out.print(x + "\t");

    answerList.add(maxArray[deque.getFirst()]);

    count = 0;
    for(int i = length - k + 1; i < maxArray.length; i++)
    {
        if(deque.getFirst() == count)
            deque.removeFirst();

        if(deque.isEmpty())
            deque.addFirst(i);
        else
        {
            if(maxArray[i] < maxArray[deque.getLast()])
                deque.addLast(i);
            else
            {
                while(!deque.isEmpty() && maxArray[deque.getLast()] <= maxArray[i])
                    deque.removeLast();
                deque.addLast(i);
            }
        }
        answerList.add(maxArray[deque.getFirst()]);
        count++;
    }

    //for(int x: answerList)
    //  System.out.print(x + "\t");

    count = 0;
    for(int i = 0; i < queryString.length(); i++)
    {
        char query = queryString.charAt(i);
        if(query == '?')
            System.out.println(answerList.get(count));
        else if(query == '!')
            count++;

    }
    cio.cleanup();
}

}

link
This answer is marked "community wiki".

answered 30 May, 02:49

sonvar12's gravatar image

3★sonvar12
11
accept rate: 0%

My solution is showing TLE for few cases. Please help.

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

link

answered 02 Jun, 11:36

anubhaw_iiitu's gravatar image

4★anubhaw_iiitu
1
accept rate: 0%

My code is giving TLE. Please Help. https://www.codechef.com/viewsolution/13978376

link

answered 02 Jun, 11:38

anubhaw_iiitu's gravatar image

4★anubhaw_iiitu
1
accept rate: 0%

can any1 give me d solution which is solved using sparse tables ??

link

answered 07 Jun, 22:22

msd_007's gravatar image

3★msd_007
2897
accept rate: 6%

@rj25 plz explain purpose of these lines : for(int k=n-f;k>=0;k--)frames.push_back(fr[k]); for(int i=n-1;i>0;i--)frames.push_back(fr[i]); in your code.

link

answered 13 Jun, 22:48

sierra101's gravatar image

2★sierra101
1
accept rate: 0%

edited 13 Jun, 22:49

The given pseudo code generates a different sum array..can anyone please explain how the given sum array is generated..@likecs @admin i think sum[0]=b[0] ..instead of sum[0]=0

link

answered 12 Aug, 12:45

amanharitsh's gravatar image

3★amanharitsh
134
accept rate: 0%

edited 12 Aug, 13:07

How to compute the answer using this sum array...

(12 Aug, 20:26) amanharitsh3★

https://www.codechef.com/viewsolution/14939652 My simple and easy to understand solution.. And for all struggling with the "Sum array " part...sum[i] denotes the number of 1 in the range inp[i-k] to inp[i]...

(12 Aug, 23:47) amanharitsh3★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×11,580
×909
×164
×16

question asked: 18 May, 13:46

question was seen: 4,589 times

last updated: 12 Aug, 23:47