Thanks, fixed.

On the contrary, I was able to deterministically find out the language mapping in atmost $$$11$$$ queries but could not figure out how to perform the search in less than $$$4\log{10^6}$$$ queries.

Your claim for 40 queries in two separate binary searches is quite optimistic because it's not easy to do a binary search (though I believe it's possible in theory to approach this limit).

As a side note, there was a similar problem on IOI2010 that focuses on the 1D version, where the words "hotter" and "colder" are known. It's quite tricky, you can try it in the IOI archive on Codeforces: https://ioi.contest.codeforces.com/group/32KGsXgiKA/contest/103756/problem/B.

Determining the language is easy, so focus on the search part.

I solve for both coordinates independently (I always set the other one to zero), so let's think of it in 1D. The problem is that we are not able to do binsearch easily as for that to work we would need to be able to ask questions for out of bounds points. In my solution I keep an interval $$$[L, R]$$$, where the answer is within that and my last question was either in $$$L$$$ or $$$R$$$. I want to shrink this interval 3 times using 2 questions and maintain my invariant about last question being in one of the ends of my interval. For simplicity assume that last question was in L. Then I ask about $$$c = \frac{L + 2R}{3}$$$. If I get "further" then I know that my answer is within $$$[L, \frac{2L+R}{3}]$$$ and I already shrunk my interval 3 times and I can ask my next question in L to maintain the invariant. If I get "closer" then I ask about $$$c+1$$$. Depending on the answer I restrict to either $$$[\frac{2L+R}{3}, c+1]$$$ or $$$[c+1, R]$$$. That uses $$$4 \cdot log_3(10^6)$$$ questions for the search part, so in addition with constant number of queries determining the language, it barely fits into the limit

OK, it's here: https://nerc.itmo.ru/archive/2022/nef-2022-tutorial.pdf

1. You can brute force it locally.
2. Consider finding a place with the highest entropy (or similar).

Just always ask the question that minimizes the size of the biggest class that you restrict to after getting an answer. Though it will be a bit slow, but if you hardcode first move (that does not depend on anything) as 1475 (that you compute with your a bit too slow code) then it is fast enough

Could not write an AC solution yet, but these should be the cases of the two cells that make the tiling impossible.

• The two cells are on a different connected component.
• The two cells are on the same connected component, and are on the same color (The color being $$$x+y \bmod 2$$$)
• The two cells are on the same connected component, are on the different color, and the two cells divide the component to more than one so that at least one of the divided components are invalid (i.e. odd area or invalid color matching),

Covering with dominoes is of course matching between white and black cells. Let $$$w, b$$$ denote number of white and black cells that remained. Of course we have $$$w=b$$$ and if we remove cells of the same color then we win, so the true answer is at least $$$2 \cdot {w \choose 2}$$$, so if $$$w > 1005$$$ then we are done, because we simply output $$$10^6$$$ and we are allowed to solve the rest of the problem in quadratic complexity in terms of number of free cells. We compute the matching. The answer will be $$${2w \choose 2}$$$ minus the number of pairs so that after their removal there is still a full matching, so we focus on counting these. Then, for each white cell, we unmatch it and remove it and want to count how many black cells we can remove so that there is still a full matching. These are simply reachable vertices from the black cell that was matched with the removed white cell, so we count these using one DFS.

I don't know how to optimise the time complexity, but space complexity isn't hard to cut to $$$O(2^n)$$$.

Let's compute DP[i] = chance of it reaching a state of mask i as in set bits represent people that haven't gotten any answer wrong. From state i, whenever it takes a question that "i AND question_mask != i" (all such questions aren't yet taken because otherwise the AND of all taken questions wouldn't be i) it goes to a state with less bits.

The problem is optimizing the transition and I guess you did that by iterating through submasks in some way. We can solve the problem from here in O(2^M * M^2).

Let's have an array A[i] = number of questions with mask of answers i.

At first we know the answer for DP[(1 << M) — 1]. If we use AND convolution of that DP array with the array A we almost have the contribution of transitions from state "(1 << M) — 1" to submasks of it. What's missing is dividing it by the number of masks that change result when we take the AND. A mask of questions "j" won't change the AND with "i" iff j is a supermask of i. So if we take B[i] = sum of A[j] for j supermask of i, then N — B[i] is the number of masks that will change state.

Now, to apply that transition in general we can simply apply it to states with M active bits, then M-1 active bits and so on.

The solution is: For each BITS from M to 1, take D[i] = 0 if pop_count(i) != BITS otherwise DP[i] / (N — B[i]). Then take the AND convolution of D and A, that'll give us the contribution of states with BITS active bits to states of less than BITS active bits. Add the result of that convolution to the corresponding positions for every position with less than BITS set bits.

can you explain your solution as well?

You can treat it as a bipartite matching problem. A greedy approach will find a matching of size at least N-2. We want a perfect matching, so starting from a matching of size N-2 we can find O(1) augmenting paths in O(N).

the ideas other people proposed are a bit simpler than my way but I started off by thinking about cyclic shifts — for a cycle of length $$$>2$$$ mapping each element $$$a_i := a_{a_i}$$$ results in a valid $$$q$$$ which allows you to derive $$$p$$$ for the elements in that cycle. So then you just have to figure out how to cover the cycles of length $$$ \leq 2$$$

Ok, so let's suppose that there is a set of integers that doesn't occur in $$$q$$$ at given moment. If this set has at least 3 elements, for every $$$i$$$, we can set $$$q[i]$$$ as one of these elements (as every $$$q[i]$$$ has at most two integers that cannot be put there). Problem starts when there are only 2 elements left in this set. So we only want to make sure that remaining 2 elements will suit in remaining positions.

maybe you can submit here(https://mirror.codeforces.com/contest/1773/submit)

Try reducing problem for (n, k) to problem for (n-2, k-2). For that to work you will also need solutions for base cases k=1 and k=2.

random

If you can determine $$$q$$$, then you can determine $$$p$$$ (because it is essentially $$$a^{-1} \circ q^{-1}$$$). The probability that a random permutation will have fixed points is pretty low (probably $$$\frac{1}{n}$$$, without proof). Knowing this, you can shuffle $$$q$$$ multiple times, until you can trust yourself that the answer will be found if it exists.

With randomisation: https://mirror.codeforces.com/blog/entry/109856?#comment-978371

Without randomisation: https://mirror.codeforces.com/blog/entry/109856?#comment-1007263

Suppose you have two towers: 1 3 and 2 4