Hi all, I need help with 2021 US Open Gold problem 2. The official analysis reads
" Suppose that portals pv0 and pv1 are not contained within the same cycle as pv2 and pv3 in G. Then if we permute the portals adjacent to vertex v so that the adjacency list is now pv0, pv2, pv1, pv3 this will combine all of pv0, pv1, pv2, pv3 into a single cycle. In other words, every vertex has the potential to unite two cycles."
However, I am not convinced by this. How do we know for sure that switching the adjacency list to be 0,2,1,3 wouldn’t break the existing connection between 0,1 and 2,3? Of course, assuming this logic is correct, the question is solved by a MST algorithm.