Not the best analogy though: "this is DP problem" would typically be a hint (and it is never written in problem statement), while "this is an interactive problem" is something that is written in problem statement and isn't secret information.

Not many people from the USA compete in Codeforces because of timezone difference.

No, you are in the USA.

I took greedy approach, for a particular index (i,j) assigned a[i][j]=min(a[i][j],b[i][j]) and b[i][j]=max(a[i][j],b[i][j]). Then checked whether the new matrix a and b are increasing.

I coded a $$$Nlog(N)$$$ solution, for $$$N=100000$$$ I don't think it's too strict.

I coded O(n)

For the people who are commenting, I know that the intended solution is O(N) or O(NlogN). I'm saying that there are an unintended solution which was obvious to me, and it would run just over a second.

It's enough to check rotations that are divisors of $$$N$$$.

I did hashing -> pi function.

You can observe that the k used to rotate the segments must be a divisor of N. This means that there are at most $$$cbrt(N)$$$ candidates for k, therefore we can simulate the process. We can see if some state is equivalent with the initial one in O(N), but I think that O(N*log(N)) is also good

We can represent the circle as a string (the "characters" are vectors of distances to neighbors) and then use Z function to find the period of the "string". The answer is yes if and only if the string is periodic (at least, my solution relies on that :D).

You did the same to me. :P

What were your tests? Should I be worried about my solution?

I believe you can iterate over proper factors of $$$n$$$ and brute force check them all.

That can be inducted to "if count of minimum number is greater than n/2 you lose."

How can a segment have 2 lengths ?

You have N points on the circle. For any rotation to be a correct rotation, it's increment has to be a divisor of N. As N <= 1e5, max divisors of N is 128.

Now, store your initial graph as an array of edges, and for each divisor of N between 1 and N-1, make a new graph by adding the increment (and handling the modulo of points between 1 and N) to the points in the old graph, and check if your new graph is the same as the old one.

Complexity = O((Number of divisors of N)*M*C), where C is a constant like logN, depending on how you store your graph.

I have an alternate solution, check for all clockwise and anticlockwise rotations of magnitude X (where X can be any divisor of N) . That should suffice

I used the prefix function as well. However, I first created an array d, where d[i] is the sorted list of clock-wise segments lengths of which i is an end point. For example, if n = 7 and node 1 is connected to nodes 2, 4, and 6, d[1] would be {1, 3, 5}. I then created an additional array d2, which was two instances of d concatenated together. The Knuth-Morris-Pratt algorithm was used to determine if there were more than two occurrences of d in d2.

Edit: My solution was accepted. https://codeforces.me/contest/1162/submission/53757920

Why weak? Can you leave your test case?

I think something wrong in the contest privacy system.

Probably not. I tried to reload the page and it said, that I am not allowed to view the page. I think it is because of the onsite contest.

Maybe because they want to wait for the onsite results to be announced before anything else? Still stupid though.

Read update 3 of the post

lets iterate over all starting positions(from one to n) call  it pos

if a pos is not in the x list
     answer += 3 if pos >1 and pos < n # e.g. (2,1)(2,2)(2,3)
     answer += 2 else  e.g(1,1)(1,2)

if it is in the list
    if(last[pos-1] < first[pos]) 
    ++answer
    if(last[pos+1] < first<[pos])
    ++answer

i know i am not very clear but could explain this much now

i have the same on my profile page o_o

Moreover, all users' profile page is also blocked.

ETA?

EDIT: "UPD 4: The results will be in around 90 minutes after the end of the competition."

can I find tasks somewhere now?

nah I thought it's because of Thanos

my Div2A didn't compile and checker log showed nothing, then i resubmitted the same code with //1 and it passed pretests.53746942, 53747370

In your opinion how long will this take?

for each i as starting ,you can take j = i,i+1,i-1 as ending only if starting position of i > last position of j..

Solve this problem separately for each cell. There are only three Alice moves for each cell 'i'. Alice moves the token from i to i+1, from i to i-1, or from i to i. The first and second are not valid if there is a Bob move from source to target cell. The last one is valid if there is no Bob move at that cell.

observe that there are total of (n*3)-2 pairs you can form, just iterate over all the queries asked by bob, when you are at a query, if bob asks x+1 in some question next, then the pair (x, x+1) is invalid. the same process goes for (x, x-1) pairs, also for each question, (x, x) pair is invalid. you can easily keep track of invalid pairs in set <int> the answer is total — set.size()

Thanks to all you guys!

For every i, if i is not present in sequence, then the scenario (i, i), (i, i + 1) [if i < n], (i, i — 1) [if i > 1] will always print "No".

If i is present in sequence, then, let pos be the minimum position where x[pos] = i, we need to change i to i + 1 for scenario (i, i + 1) before pos. Now, if i + 1 is not present in sequence after position pos, then scenario (i, i + 1) will answer "No". Same goes for (i, i — 1).

solve k as divisors of n -> after k units of rotation for each segment there should be one segment replacing it....

I passed pretests with KMP.

lol , you are not alone

Ну Майк зато заблокировал то, что хотел!

https://codeforces.me/blog/entry/66821?#comment-509597

https://codeforces.me/blog/entry/66821?#comment-509597

The system testing is started!

Yep

I faced load shedding and submitted A after solving B.

@MikeMirzayanov