# CHEFSUBA - Editorial

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

#19

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.

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

#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

#25

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;

# 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

#30

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

#31

what will the size of sum array?

#32

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

#33

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.

#34

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

#35

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

``````	CustomInputOutputClass cio = new CustomInputOutputClass(readFromFile, outputToFile);

int n = temp[0];
int k = temp[1];
int p = temp[2];

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* = origArr[i % length];
}
for(int i = 0; i < length; i++)
{
int t = arr*;
arr* = arr[2 * length - 1 - i];
arr[2 * length - 1 - i] = t;
}

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

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

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

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

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

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

if(deque.isEmpty())
else
{
if(maxArray* < maxArray[deque.getLast()])
else
{
while(!deque.isEmpty() && maxArray[deque.getLast()] <= maxArray*)
deque.removeLast();
}
}
count++;
}

//	System.out.print(x + "	");

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

}
cio.cleanup();
}
``````

}

#36