Help me with Chef and Sub Array problem?

general
1

I am getting TLE in one testcase. I tried very hard to get it into TL but got no results. Please help.

Problem link: https://www.codechef.com/problems/CHEFSUBA

My solution: https://www.codechef.com/viewsolution/14291195

2

for(j=n-1;j>-1;j–){
if(check(myvector[j].second,i,y,n)) break;
}

You can try using binary search here. Also using segment trees is much easier.

3

I will help you with AC solution. Assume you have n elements and k be the length of the frame.

FOR SUBTASK 1 : n,k<1000 → here you can use simple Brute Force technique and do what the question tells you to do,i.e, when you encounter a ‘!’ character,rotate your array in o(n) and when you encounter a ‘?’ calculate the maximum of all the k sized subarrays and print it, it will alse take o(n). Thus the overall complexity will be o(n*p) which would pass for this subtask but not the other one.

FOR SUBTASK 2: for given n-sized array of zeroes and ones, what i did was create an array of size 2*n in which after the last element from the input, we insert again from the first element at the preceeding places,i.e
if the elements are given “0 1 0 0 1 1” then we insert these from position 0 to position 5 of the array and again from the 6th position to 11th position we insert given elements in the given order.
Then we create a new array(say csum[]) whose ith index stores the sum of first i elements of the above created array.Now, we know that after operating ‘!’ l times the start index would be ((n-l)%n)th element .
let this start index be st.

Since we have stored the cumulative sum in our csum array we now have to answer the maximum sum that can be obtained in a k frame from index st to (st+n). By precalculating this for all values of st from 1 to n,we can answer each query in o(1) time and we dont even need to rotate the array,just increase the variable l when ‘!’ is encountered. For precalculation, rather than explaining that process myself I would recommend you to read this on Sliding window maximum.

I hope it helped a little, if not, forgive me, its only my first answer to someone’s question in here.

Any doubts, ask me freely in the comment section.

My solution

2 Likes