2022A - Автобус в Пенхамо
2022B - Продавец Карел
2022C - Джерримендеринг
2022D1 - Ассасин (простая версия)
2022D2 - Ассасин (сложная версия)
Hint 3: What is the minimal value anyway? Can we find a lower bound? Can we find the optimal strategy for small $$$n$$$?
Hint 4: We can observe that $$$n = 3$$$ is impossible to solve with less than $$$3$$$ queries and $$$n = 4$$$ are solvable with $$$4$$$ queries. This strategies are ilustrated in the image below:
Hint 5: There's only $$$9$$$ possible unlabeled directed graphs with $$$3$$$ nodes and at most $$$3$$$ edges, you might as well draw them. They are ilustrated in the image below for convinience though. Stare at them and convince yourself $$$4$$$ queries is the optimal for $$$n = 3$$$.
Hint 6: Using our solutions for $$$n = 3$$$ and $$$n = 4$$$, we can extend our solution to D1 for a solution that does $$$n$$$ queries if $$$n$$$ is even and $$$n + 1$$$ queries when $$$n$$$ is odd. The idea is the following:
While $$$n > 4$$$,
- query $$$n -> n - 1$$$, $$$n - 1 -> n$$$.
- If their answers don't match, one of them is the impostor. Query $$$n -> n - 2$$$ and $$$n - 2 -> n$$$.
- If their answers don't match, $$$n$$$ is the impostor.
- Otherwise, $$$n - 1$$$ is the impostor.
- If the answers match, do $$$n -= 2$$$.
- If their answers don't match, one of them is the impostor. Query $$$n -> n - 2$$$ and $$$n - 2 -> n$$$.
- query $$$n -> n - 1$$$, $$$n - 1 -> n$$$.
If $$$n > 4$$$ doesn't hold and we haven't found the impostor, we either have the $$$n = 3$$$ case or the $$$n = 4$$$ case, and we can solve either of them in $$$4$$$ queries.
Hint 7: Is this optimal? Can we find a proof? What would a proof look like?
Hint 8: We would like to have a control of the structure of the possible graph, and we have to prove that $$$n - 1$$$ is a lower bound for $$$n$$$ even and $$$n$$$ is a lower bound for $$$n$$$ odd. We would have to show that regardless of how we ask the questions, the grader has a strategy of answering the questions in such a way that there is at least two ways of assigning the roles that are consistent with the answers, and that this two assignments have a different node as the impostor.
Hint 9: For $$$n - 1$$$ we have some control over the graph. We can show by pigeonhole principle that at least one of them has in-degree $$$0$$$, and at least one of them has out-degree $$$0$$$.
If those two nodes are different, call $$$A$$$ the node with indegree $$$0$$$ and $$$B$$$ the node with outdegree $$$0$$$. Let the grader always reply yes to your queries.
- $$$A$$$ can be the impostor and everyone else Knaves.
- $$$B$$$ can be the impostor and everyone else Knights.
If those two nodes are the same, then the graph looks like a collection of cycles and one isolated node. The grader will always reply yes except for the last query where it replies no. Let the last query be to player $$$A$$$ about player $$$B$$$. The two assignments of roles are:
- $$$A$$$ is the impostor and everyone else in the cycle is a Knight.
- $$$B$$$ is the impostor and everyone else in the cycle is a Knave.
Hint 10: Observe that the structure of this proof is very general, can we generalize it to do the same for $$$n$$$ odd and $$$n$$$ queries?
Hint 11: Use a computer.
Hint 12: Note that the structure of our first proof is very easy to simulate for small values of $$$n$$$ and small number of queries. Write an exhaustive checker.
Hint 13: Run it on $$$n = 5$$$ and $$$5$$$ queries. According to our conjecture, we should found a counter case.
Hint 14: There is no countercase! Which means $$$n = 5$$$ is solvable with $$$5$$$ queries. How? Also, observe that if we find a solution to $$$n = 5$$$ we can apply the same idea and recursively solve the problem in $$$n$$$ queries for all $$$n > 3$$$.
Solution:
We will use a lemma, that generalizes the idea for hint 2.
Lemma:
Consider the natural directed graph representation, adding a directed edge with weight $$$0$$$ between node $$$i$$$ and $$$j$$$ if the answer to the query \t{``? i j''} was yes, and a $$$1$$$ otherwise.
We will prove that the sum of weights of a cycle is odd if and only if the impostor is among us (among the cycle, I mean).
Suppose the impostor is not in the cycle. Then observe that the only time you get an edge with weight $$$1$$$ is whenever there are two consecutive nodes with different roles.
- Consider consecutive segments of nodes with the same role in this cycle, and compress each of this segments into one node. The image bellow illustrates how, grey edges are queries with answer no.
- The new graph is bipartite, and thus has an even number of edges. But all the edges in this new graph, are all the grey edges in the original graph, which implies what we want.
If the impostor is in the cycle, there are three ways of inserting it (assume the cycle has more than $$$2$$$ nodes that case is exactly what we proved in hint 2).
- We can insert the impostor into one of this ``segments'' of consecutive nodes with the same role. This would increase the number of grey edges by $$$1$$$, changing the parity,
- We can insert it between two segments. -If we have Knight -> Impostor -> Knave, the number of grey edges decreases by $$$1$$$. -If thee is Knave -> Impostor -> Knight, the number of grey edges increases by $$$1$$$. Either way, we changed the parity of the cycle.
So for $$$n = 5$$$ we will form a cycle of size $$$3$$$, asking for $$$1 -> 2$$$, $$$2 -> 3$$$ and $$$3 -> 2$$$ (blue edges in the image below). — If the cycle has an even number of no's, we know the impostor is among $$$4$$$ or $$$5$$$. So we ask $$$3 -> 4$$$ and $$$4 -> 3$$$ (green edges). — If both queries match, $$$5$$$ is the impostor. — Else, $$$4$$$ is the impostor. — Else, The impostor is among us (among the cycle, I mean). Ask $$$1 -> 3$$$ and $$$2 -> 1$$$ (purple edges). — If $$$1 -> 2$$$ doesn't match with $$$2 -> 1$$$ and $$$1 -> 3$$$ doesn't match with $$$3 -> 1$$$, $$$1$$$ is the impostor. — If $$$1 -> 2$$$ doesn't match with $$$2 -> 1$$$ and $$$1 -> 3$$$ matches with $$$3 -> 1$$$, $$$2$$$ is the impostor. — If $$$1 -> 2$$$ matches with $$$2 -> 1$$$ and $$$1 -> 3$$$ doesn't match with $$$3 -> 1$$$, $$$3$$$ is the impostor. — It is impossible for $$$1 -> 2$$$ to match with $$$2 -> 1$$$ and $$$1 -> 3$$$ to match with $$$3 -> 1$$$, because we know at least one of this cycles will contain the impostor.
2022E1 - Billetes MX (простая версия)
Code: 285962028
2022E2 - Billetes MX (сложная версия)
Please read the solution to E1 beforehand, as well as all the hints.