I am trying to solve problem 761 B "Dasha and Friends" on codeforces, and I have been stuck on it for a while now. It seems to be an easy problem but I just can't figure it out. Here is the official hint for the problem as given on the codeforces tutorial page:

Let's add distances between pairs of adjacent barriers of both tracks in arrays and check if it possible to get one of them from another using cycling shift of the elements.

I can't understand what the above statement is saying or why it would hold. Also, I found a solution here, but I can't understand what they are doing. Can anyone help me with this? I don't need a complete solution, just an understanding of what is the underlying concept here. Any help is appreciated, thanks !

CodePudding user response：

Runners have distinct start points, so you cannot compare positions relative to start points.

But distances between obstacles are the same, so comparison of sequences of these distances is valid.

The first problem is segment around start position - but we can get it's length by subtracting last_barrier from L first_barrier because of cyclic nature of circle running.

The second problem - we have two lists/arrays of distances, and should check whether cyclic shift of one list give a list similar to second one. Linked solution just generates all cyclic shifts and compares for indentity. It is simple approach and it works nice for given limits (n=50).

If you need to do the same for large n, quadratic complexity becomes unappropriate, and you would need better approach - for example, double the first list (4,1,2=>4,1,2,4,1,2) and search for occurence of second one in doubled (like substring search)