CHEFSUBA - Editorial

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

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

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.

Code here

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 :slight_smile:

Now its done. Still gives TLE in 3-4 cases.
Code: CodeChef: Practical coding for everyone

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.

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

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

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

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

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

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

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

recursive gave me 100

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

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.

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.

Please check this solution @chaitya_62

How to compute the answer using this sum array…