USACO Silver 2021 January - Dance Mooves

Official Analysis (C++)

Video Solution

Note: The video solution might not be the same as other solutions. Code in C++.

Solution (DSU)

Just like the official analysis, the key observation to make here is that all cows will share the same answer if they have been in the same position. In other words, any cow i will share the same positions with P[i], the position of the cow after K swaps. Since we are only keeping track of the unique items, it suffices to use a set or in this case an unordered_set to keep track of the distinct position a cow covers. After linking all our components together, it suffices to insert them all into a singular set - the set takes care of counting distinct numbers. The trick here is that we perform insert() on components[dsu.get(i)] in order to count this cumulative distinctness in a single position.

Time Complexity: $\mathcal{O}(N\alpha(N) + K)$

Copy
 Code Snippet: C++ Short Template (Click to expand)

/**
 * Description: Disjoint Set Union with path compression
 * and union by size. Add edges and test connectivity.
 * Use for Kruskal's or Boruvka's minimum spanning tree.
 * Time: O(\alpha(N))
 * Source: CSAcademy, KACTL
 * Verification: *
 */