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.