https://www.codechef.com/problems/CHN16H

My observations:

f(2s, 2x) = f(s, x) if

f(2s, 2x) = 3f(s - 1, x) if

f(2s + 1, 2x + 1) = 3f(s, x) if

f(2s + 1, 2x + 1) = f(s - 1, x) if

I came across this problem Robolympic Batons yesterday. I actually thought of solving it using string matching. But I am getting a wrong answer. Also that all others solutions are based on FFT but I think it can be easily solvable using string matching.

My exact idea: Make an array of size 2*n of batons where second half is copy of first half of the array (to avoid considering modulos for rotation). Then make an array of size n for storing position of robots (1 — there, 0 — not there) and truncate it (remove all zeroes before first robot and all zeroes after last robot and store the starting position of first robot). And then search the second array in first array. Here we make sure that we only search n substrings.

Please suggest me where I went wrong.

Thanks in advance.

Hi everyone, I am able do problems on dp, graphs, strings. And I even learnt suffix arrays recently. I want to become even more stronger in competitive programming. I want to solve hard problems on sgu specifically. But I am not able to find any problem classifiers anywhere. Can anyone suggest me some hard problems on sgu? Hard in the sense I mean those which can't be solved by a purple or yellow coder. Thanks in advance.