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