I did this Question using sliding windows by precompute values and deque to get the maximum value
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.
2 Likes
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.
One question guys!
Is the complexity O(n) for the entire subtask or O(n) for each querie?
Can someone tell me whats wrong with my code. I would be very greatful.
Submission : CodeChef: Practical coding for everyone
This Solution is giving TLE. I have used Segment Tree/ Range Maximum Query. Please share your insight.
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
i am using segment trees as said above . i am getting WA. please help me
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).
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;
}
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
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).
what will the size of sum array?
Why do I get a SIGSEV error on exactly one of the testcases? All the others are AC. I used two sliding windows.
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: CodeChef: Practical coding for everyone
The code is simple with no use of special data structures, easy to check.
Thank you in advance 
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();
}
}
My solution is showing TLE for few cases. Please help.