Editorial Codeforces Round 978 (Div 2)

Правка en15, от jampm, 2024-10-15 10:12:15

2022A - Bus to Pénjamo

Step 1
Step 2
Step 3
Key Takeaway

2022B - Kar Salesman

Step 1
Step 2
Step 3
Alternative Solution
Intuitive proof
Formal Proof by Errorgorn
Key Takeaway

2022C - Gerrymandering

Step 1
Step 2:
Step 3:
Step 4:
Key Takeaways

2022D1 - Asesino (Easy Version)

Hint 1
Hint 2
Solution to D1

2022D2 - Asesino (Hard Version)

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 $$$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 (Easy Version)

Hint 1
Hint 2
Hint 3
Hint 4
Hint 5
Proof of hint 5
Hint 6
Hint 7
Hint 8
Answer to hint 8
Hint 9
Answer to hint 9
Solution

Code: 285962028

Key takeaway

2022E2 - Billetes MX (Hard Version)

Please read the solution to E1 beforehand, as well as all the hints.

Solution 1
Solution 2
Bonus

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en44 Английский JuanPabloAmezcua 2024-10-16 22:21:11 25 Tiny change: ' summary="Formal Proof 2 (b' -> ' summary="Proof 2 (b'
en43 Английский JuanPabloAmezcua 2024-10-15 22:32:24 2 Tiny change: 'number of unhappy peop' -> 'number of happy peop'
en42 Английский JuanPabloAmezcua 2024-10-15 18:32:34 0 (published)
en41 Английский JuanPabloAmezcua 2024-10-15 18:31:54 93 Tiny change: 'olve();\n}```\n</spo' -> 'olve();\n}\n\n```\n</spo'
en40 Английский JuanPabloAmezcua 2024-10-15 18:29:31 128
en39 Английский JuanPabloAmezcua 2024-10-15 18:24:54 147 (saved to drafts)
en38 Английский JuanPabloAmezcua 2024-10-15 18:21:32 2 (published)
en37 Английский JuanPabloAmezcua 2024-10-15 18:21:03 61 Tiny change: 'spoiler>\n\nCode: [submission:285961673]\n\n<spoiler' -> 'spoiler>\n<spoiler'
en36 Английский JuanPabloAmezcua 2024-10-15 18:13:42 8765 Tiny change: '\n}\n```\n\n<spoiler' -> '\n}\n```\n</spoiler>\n<spoiler'
en35 Английский JuanPabloAmezcua 2024-10-15 18:04:14 933 (saved to drafts)
en34 Английский JuanPabloAmezcua 2024-10-15 16:22:02 0 (published)
en33 Английский jampm 2024-10-15 16:17:23 58
en32 Английский jampm 2024-10-15 16:07:23 151
en31 Английский JuanPabloAmezcua 2024-10-15 15:58:57 15
en30 Английский JuanPabloAmezcua 2024-10-15 15:58:06 1 Tiny change: ' \n** * ' -> ' \n ** * '
en29 Английский jampm 2024-10-15 15:13:32 1 Tiny change: 'mma:\n\n\nThe sum of' -> 'mma:\n\n\n>The sum of'
en28 Английский jampm 2024-10-15 15:00:58 919
en27 Английский jampm 2024-10-15 15:00:01 1042
en26 Английский jampm 2024-10-15 14:48:04 216
en25 Английский jampm 2024-10-15 14:37:37 544
en24 Английский jampm 2024-10-15 14:22:54 1287 Tiny change: 'dots a_n\}\right\}$$\n\ncl' -> 'dots a_n\}$$\n\ncl'
en23 Английский jampm 2024-10-15 13:47:37 326
en22 Английский jampm 2024-10-15 13:42:12 434
en21 Английский jampm 2024-10-15 13:32:17 784
en20 Английский jampm 2024-10-15 13:08:03 3290
en19 Английский jampm 2024-10-15 12:35:52 276 Tiny change: 'g" style="width: 300.0px;flo' -> 'g" style="height: 100.0px;flo'
en18 Английский jampm 2024-10-15 12:22:05 1060
en17 Английский jampm 2024-10-15 12:04:22 1744 Tiny change: 'ries match $3$ is th' -> 'ries match, $3$ is th'
en16 Английский jampm 2024-10-15 11:10:52 3916 Tiny change: '2.png)\n\n - The new ' -> '2.png)\n\n- The new '
en15 Английский jampm 2024-10-15 10:12:15 7426
en14 Английский jampm 2024-10-15 00:48:57 8217
en13 Английский JuanPabloAmezcua 2024-10-14 23:38:46 243
en12 Английский JuanPabloAmezcua 2024-10-14 17:54:06 344
en11 Английский JuanPabloAmezcua 2024-10-14 16:51:20 624
en10 Английский JuanPabloAmezcua 2024-10-14 04:59:15 451 Tiny change: ' ** *\n ** * ' -> ' ** *`\n`** * '
en9 Английский JuanPabloAmezcua 2024-10-14 04:32:52 866
en8 Английский JuanPabloAmezcua 2024-10-14 02:41:29 41
en7 Английский JuanPabloAmezcua 2024-10-14 02:39:00 98
en6 Английский JuanPabloAmezcua 2024-10-14 02:33:24 2721
en5 Английский JuanPabloAmezcua 2024-10-14 02:19:56 37
en4 Английский JuanPabloAmezcua 2024-10-14 02:17:19 375
en3 Английский JuanPabloAmezcua 2024-10-14 02:00:42 9
en2 Английский JuanPabloAmezcua 2024-10-14 01:59:36 2779
en1 Английский JuanPabloAmezcua 2024-10-14 01:42:55 1499 Initial revision (saved to drafts)