what u think about hide and seek problem??was it easy for you??

My solution by using DP: https://mirror.codeforces.com/contest/1162/submission/53754575

Interesting. 4 is also optimal for $$$n$$$ large enough, since 3 is impossible when $$$2^{1.5n} < 3^n/6$$$.

I wrote a brute force for $$$n = 6$$$ and $$$0 \leq a_i \leq 5$$$ and outputted the positions where Bob wins. From those positions the solution is obvious.

Maybe it didn't affect anybody but tests for 1161D - Palindrome XOR seem weak too. Judging from prefixes of tests, all big tests are just random characters ?01. Maybe there is some smart pattern in some, but I don't see any test e.g. with just characters 1 or just ?.

Thanks! arsijo added it to the tests yesterday. It's my bad T-T

Let's suppose that image is rotationally symmetrical and image consist of p identical blocks. Then every block has length of n/p. Then if we rotate image by n/p units, the new image will be the same as the original one. Now we can brute force the value p among the divisors of n and check if the rotation i + n/p is correct.

Let a segment be [a,b] when we rotate it by k it gets [a+k, b+k] to be symmetrical there should be a segment [a+k, b+k] which after rotating will move to [a+2k, b+2k] or we can say that all possible values can be [(a+xk)%n, (b+xk)%n].

r = (a+xk)%n = a+xk-qn

xk — qn = r — a

Use bezout identity euqation has solution if r-a is c*gcd(k,n) or r = a+c*gcd(n,k).

Same bro

Bob will ask Alice k questions (if Alice is in the i-th cell ? ) . On reply.. Alice can answer yes or no. At most one time in this process, before or after answering a question, Alice is allowed to move her token from her current cell to some adjacent cell.

Consider the first example: << Lets say, {x,x,x} is ALice's answer on Bob's 3 question. Here , x = y(yes) or n(no). >> there is a subsequence (5,4) on Bob's question. Since Alice can change the position at most once, here 3 cases can be arrived. 1) if she changed before 5 , her answer will be {n,n,y}; 2) if she changed on between 5 and 4, answer {y,n,y}; 3) if she changed after 4, her answer {y,n,n};

Now consider a subsequence that is not present in Bob's question list. Let it is (3,4) in this case , she can change position after 4, her answer will be {n,n,n};

And the question says, "Alice acted in such a way that she was able to answer "NO" to all of Bob's questions." As you just see .. if there is a subsequence , Alice's answer will must contain at least 1 yes.

And since Alice can move to an adjacent cell only, There are 2*(n-1) + n subsequence on their playing ground. So all u have to do is .. somehow erase all those culprit subsequence from our all possible subsequence set. Thats it ! :3

why so hard? my solution works in O(n*m) time and it is much easier
http://mirror.codeforces.com/contest/1162/submission/53747942

It says you can but not you must .

[Deleted]

Well, I used two facts to prove it.

1. turning by $$$k$$$ will yield the same result as $$$2k$$$, $$$3k$$$ and so on;
2. turning by $$$n$$$ will obviously put the circle in the same position it was initially.

Thus there exists some $$$t$$$ such that $$$tk = n$$$, $$$k$$$ is a divisor of $$$n$$$.

Let the minimum value to do a symmetrical rotation be $$$k$$$.

Then for any $$$t$$$, such that $$$t \% k == 0$$$, $$$t$$$ will produce a symmetrical rotation too, and generally rotating by $$$t$$$ is the same as rotating by $$$t\%k$$$.

It's obvious that turning by $$$n$$$ produces a symmetrical rotation.

Let $$$n \% k != 0$$$, then that means that $$$n \% k$$$ produces a symmetrical rotation. But $$$n\%k < k$$$, hence this statement contradicts the first one.

Start numbering from zero,instead of 1

If a,b moves to (a+k)%n,(b+k)%n.Then (a+k)%n,(b+k)%n will move to (a+2*k)%n,(b+2*k)%n and so on,but there should be a (a+k(q-1))%n,(b+k(q-1))%n,which will move to a,b in next step.

so, (a+kq)%n=a

a+kq=dn+a

kq=dn

if k is not divisible by n,then it should definitely be divisible by nd.

q can be at max n.

SO,d cannot be greater than k.

So if k divides nd,then k/d should divide n.

In short if there is a solution with k not divisible by n,then there will definitely be another solution with k1 less than k and k1 divisible by n.

Try this test case

7 7

0 2

1 3

2 4

3 5

4 6

5 0

6 1

K=2 is a solution,but k=1 is also a solution

If for some k, you rotate all segments by k units and you get the same figure back then it is also possible for 2*k, 3*k ......so on. Now you can get the same figure back when k=n. So k must be a divisor of n. Any number under 10^5 has around 100 divisors at max, so you have to check for them only if such a k exists or not

Since there are no perfectly overlapping segments maybe we can do something like — Transform a segment [x,y] into [x%k, y%k] and check final counts of segments appearing in the first block because [(a+k)%k, (b+k)%k] = [a,b].

By keeping the pair in a unordered_set or hashset. Or you could just use set or treeset with o(logn) complexity. It will still get accepted, I submitted this way

Solution: http://mirror.codeforces.com/contest/1162/submission/55727925

Sorry, I got my mistake after spending a lot of time.