Hi!

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....