Editorial Codeforces Round 978 (Div 2)

Revision en15, by 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

History

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