[UOJ 486] On my way

Difficulty Ratings

Idea Creativity: 4/5
Techniques Used: 2/5
Implementation : 2/5
OP hard interactive... It is modified from an MO practise problem.

I put this picture here so that spoilers dont appear in preview... Please tell me how to do this properly.

Link

Simplified Chinese by tEMMIE.w.=moorhsum=peehs_moorhsum=Cauchysheep=newbiedmy

Simplified Statement

There is a complete undirected graph of size $n$, where each edge is colored in either red or blue. Lets denote $(u) - (v)$ as the edge between $u$,$v$. It is given that $(i) - (i+1)$ is red for $1 \le i < k$. In each query, you can specify two nodes, and the interactor will return the color between the pair of nodes. You can make only $q$ queries. Find a path with $k$ edges such that the color of all edges on the path is the same, and the path is simple (visits $k+1$ vertices in total).
$q=2k$, $\frac{3k}{2} \le n \le 2k$, $1 \le k \le 2000$.

Solution

Let's assume $n = \lceil \frac{3k}{2} \rceil$. We can simply ignore remaining nodes.
We deonte nodes with id $[2,k-1]$ be red (note that $1$,$k$ are colorless), and nodes $[k+1,n]$ be blue.
Firstly, lets find out the color of $(1) - (k)$. If it is red, we have a red cycle of length $k$. We query the following edges:
-$(i) - (k+i)$ and $(i+1) - (k+i)$ For $1 \le i \le n-k$
Either the whole path is blue or there exist a red edge, where you can form a red path with edges in the cycles, so this case is solved. Modifiy the strategy a bit when $k$ is odd.

So now we can assume $(1) - (k)$ is blue.
Lets define an alternating path to be:
-a simple path consisting of only blue and red nodes, and both of its end are blue nodes.
-no nodes that are adjacent hvae the same color
-all edges in the path is blue
Note that a path that only consists of a blue node is also an alternating path. Also, define a size of a alternating path is the number of blue nodes on it.
Let's build two alternating paths $u,v$ inductively until it includes all blue nodes. That is, repeat until $2(|u|+|v|) \ge k$
For the base case, you just pick a blue node for each of $u$,$v$. So the inductive step is as follows: So as you know that $2(|u|+|v|) < k$ and each alternating path as one more blue node than red node, you can find a pair of nodes $i$ and $i+1$ that are not included in any of $u$,$v$.
Also, pick a blue point $r$ that is not included in $u$,$v$.
Let $x$ be an endpoint of $u$, and $y$ be an endpoint of $v$. Case 1: Both $(x) - (i)$ and $(y) - (i)$ is blue.
- Let $u' = u+i+v$ and $v' = r$. Then $|u'|+|v'| = |u|+|v|+1$
Case 2: Both $(x) - (i)$ and $(y) - (i)$ is red.
- Query $(x) - (i+1)$ and $(y) - (i+1)$. If one of them is red then we can find a red path of length $k$ already
- Otherwise let $u' = u+(i+1)+v$ and $v' = r$. Then $|u'|+|v'| = |u|+|v|+1$
Case 3:Exactly one of $(x) - (i)$ and $(y) - (i)$ is blue.
-WLOG assume $(x) - (i)$ is red and $(y) - (i)$ is blue.
-Case 3a) $(r) - (i+1)$ is blue.
-Query $(x) - (i+1)$. If it is red then we can find a red path of length $k$ already.
-Otherwise we can append $i+1$ and $r$ to $u$.
-Case 3b) $(r) - (i+1)$ is red.
-Query $(r) - (i)$. If it is red then we can find a red path of length $k$ already.
-Otherwise we can append $i$ and $r$ to $v$.

So now we have $2(|u|+|v|) \ge k$.
Consider a blue cycle formed by $(1)+u+(k)+v$. Call it $s$. (you need to check 4 edges, and if one of the 4 is not blue you can find a red path of length $k$.
If $2(|u|+|v|) > k$ we are complete, and have made $2k-2$ queries total.
So now $2(|u|+|v|) = k$.
Pick red points $i$, $i+1$ that is not included in $s$ (it is easy to see that it must exist).
Pick a blue point $x$ in $s$.
If both $(x)-(i)$ and $(x)-(i+1)$ are red then we can find a red path of length $k$.
Otherwise we can combine this edge with $s$ and have a blue path of length $k$.

The total number of queries is also $2k-2$.

Comments

Lol i have completely no idea when trying to solve. If you have played with the problem a bit you might realise that its hard to induct if the blue path you are constructing has two continuous blue nodes or two continuous red nodes, which i guess motivates the idea of alternating path. Also you might realise that if you have 3 alternating blue paths then you can merge 2 of them, which can lead to the idea of making the $n-k$ blue points into 2 paths.