This post was originally written on Codeforces; relevant discussion can be found here.

I’ve been meaning to write a blog about this interesting, but not (as far as I know) documented trick for a while. I’ve decided to call it the Amogus trick after the first problem where I encountered and used it.

Prerequisites

  • DSU
  • Basic knowledge of 2-SAT (definitely not required, but it may make the blog easier to understand)

Focus Problem: CF1594D - The Number of Imposters

First, let’s solve an easier version of this problem, where we just need to find whether there exists a configuration of player roles (i.e. Crewmate or Imposter) such that all the statements made by players so far are true.

Let’s look at the two different types of statements made by players separately.

  • Case 1: Player ii claims Player jj is a crewmate. Now, if Player ii is a crewmate, Player jj will also be a crewmate. Similarly, if Player ii is an imposter, Player jj will also be an imposter. The reversed versions of these statements are also true. Using this, we can create a virtual “edge” between Players ii and jj, as their roles in the game will always be the same. More formally, for those familiar with 2-SAT or otherwise, we create the equivalency vi=vjv_i = v_j.

  • Case 2: Player ii claims Player jj is an imposter. Now, if Player ii is a crewmate, Player jj will be an imposter. Similarly, if Player ii is an imposter, Player jj will be a crewmate. We can create a virtual “anti-edge” between Players ii and jj, as their roles in the game will always be the different. More formally, we create the equivalency vi=!vjv_i = !v_j.

Adding edges is easy, we can just use normal DSU. But how do we deal with anti-edges? This is where the Amogus Trick comes in!

We can deal with these anti-edges by creating a DSU with 2n2n nodes, where nodes 11 to nn represent player ii being a crewmate, and nodes n+1n + 1 to 2n2n represent player ini - n being an imposter. Now, let’s look at those cases again.

  • Case 1 results in both players having the same role in the game. Therefore, when such a statement is said, we can unite nodes ii and jj, and similarly, unite nodes i+ni + n and j+nj + n.

  • Case 2 results in both players having differing roles in the game. Therefore, when such a statement is said, we can unite nodes ii and j+nj + n, and similarly, unite nodes i+ni + n and jj.

Testcases 2 & 3 of the sample input in the problem, respectively, visualised with the Amogus trick:

So, how can we solve our reduced problem with this? Note that a player can be exactly one of {Crewmate, Imposter}\{ \text{Crewmate, Imposter} \}, so a configuration is invalid iff for some 1in1 \le i \le n, nodes ii and i+ni + n are in the same component in our DSU. This is the only condition we need to check, as since the edges we add to our DSU are symmetric, there will always be a valid assignment of roles.

It’s not too difficult to extend this idea to solve our original problem.

Full Solution

Provided that there exists a solution for our configuration. We can give each node from 11 to nn a weight of 00, and each node from n+1n + 1 to 2n2n a weight of 11, as we only care about the number of imposters in our configuration. Now, for each pair of symmetric components, take the one that contains the maximum number of players being imposters.

My AC submission

Using this trick, we can solve a variety of other problems, such as dynamic bipartiteness checking, and it can often be paired with other modifications of DSU such as with support for rollbacks.

Other Problems:

Problems are ordered (roughly) in ascending order of difficulty.

CF1702E - Split Into Two Sets

tourist's AC Code

163478635

CF1290C - Prefix Enlightenment

My AC Code

169912969

CF1713E - Cross Swapping

My AC Code

169902868

CF1444C - Team-Building

My AC Code

169902269

A special thank you to kostia244, BucketPotato, fishy15 and AlperenT for providing feedback and/or sample problems!