Kattis dancerecital solution

Dance Recital

This article provides a rigorous walkthrough of the Kattis Dance Recital problem. We'll cover the problem abstraction, prove correctness, analyze complexity, and discuss implementation details that matter for competitive programming.

Problem Overview

Each dancer is represented by a unique uppercase letter (A-Z). Each dance routine is a string of characters describing which dancers perform. When a dancer appears in two consecutive routines, they need a quick costume change. The goal: find an ordering of all routines that minimizes the total number of quick changes.

Constraints: 2 ≤ R ≤ 10 routines, up to 26 dancers, 1-second time limit.

Modeling the Problem

Let's formalize this before coding.

• Let routine i be represented as a set S_i of dancers.
• If routine i is placed immediately before routine j, the number of quick changes contributed is |S_i ∩ S_j| (dancers appearing in both).
• We need to find an ordering π of all routines that minimizes:

Cost(π) = Σ_{k=1 to R-1} |S_π(k-1) ∩ S_π(k)|

This is equivalent to finding a minimum-weight Hamiltonian path on a complete graph where:

• Vertices are routines
• Edge weight w(i,j) = |S_i ∩ S_j|

This framing clarifies why precomputing pairwise overlaps is correct and why permutation search yields the optimal solution.

Key Insight: Bitmask Representation

With at most 26 dancers, we can represent each routine's dancer set as a 26-bit integer:

int mask = 0;
for (char c : routine.toCharArray()) {
    mask |= 1 << (c - 'A');  // Set bit for dancer 'c'
}

Why this matters: Computing |S_i ∩ S_j| becomes a single machine instruction:

int overlap = Integer.bitCount(mask[i] & mask[j]);

The AND gives the intersection; bitCount (popcount) counts the set bits. This is O(1) and extremely fast.

Algorithm Design

Feasibility Check

Given R ≤ 10, let's verify brute-force is acceptable:

With bitmasks making each permutation's cost evaluation O(R), and 36M operations well under the 1s limit in Java, exhaustive enumeration is viable.

Complexity:

• Time: O(R! × R) — enumerating all permutations, O(R) to compute each cost
• Space: O(R²) — storing the overlap matrix

Correctness Argument

1. For any fixed ordering, the total quick changes equal the sum of adjacent overlaps (by definition).
2. Our algorithm evaluates this objective for every possible permutation of R routines.
3. Taking the minimum over all permutations yields the globally optimal schedule.

Since we enumerate the entire search space and compute the exact cost for each candidate, the result is provably optimal.

Implementation Walkthrough

Step 1: Read Input and Build Masks

int R = Integer.parseInt(in.readLine());
int[] masks = new int[R];
for (int i = 0; i < R; i++) {
    for (char c : in.readLine().toCharArray()) {
        masks[i] |= 1 << (c - 'A');
    }
}

Step 2: Precompute Overlap Matrix

We fill the matrix symmetrically to avoid min/max lookups later:

int[][] overlap = new int[R][R];
for (int i = 0; i < R; i++) {
    for (int j = i + 1; j < R; j++) {
        int common = Integer.bitCount(masks[i] & masks[j]);
        overlap[i][j] = common;
        overlap[j][i] = common;  // Symmetric
    }
}

Step 3: Enumerate Permutations

Using next_permutation pattern (evaluate current, then advance):

int[] order = new int[R];
for (int i = 0; i < R; i++) order[i] = i;

int best = Integer.MAX_VALUE;

do {
    int cost = 0;
    for (int i = 1; i < R; i++) {
        cost += overlap[order[i-1]][order[i]];
        // Early termination: stop if already worse than best
        if (cost >= best) break;
    }
    if (cost < best) best = cost;
} while (nextPermutation(order));

Implementation notes:

• The do-while pattern ensures we evaluate the initial sorted permutation
• Early termination (pruning) when cost >= best provides a significant speedup in practice
• nextPermutation generates lexicographic successors; implementation is standard

Step 4: Output

out.println(best);

Worked Example

Consider 3 routines:

• Routine 0: dancers A, B → mask = 0b00000011 = 3
• Routine 1: dancers B, C → mask = 0b00000110 = 6
• Routine 2: dancer C → mask = 0b00000100 = 4

Overlap computation:

• overlap[0][1] = bitCount(3 & 6) = bitCount(2) = 1 (dancer B)
• overlap[0][2] = bitCount(3 & 4) = bitCount(0) = 0
• overlap[1][2] = bitCount(6 & 4) = bitCount(4) = 1 (dancer C)

Evaluating ordering [0, 1, 2]: Cost = overlap[0][1] + overlap[1][2] = 1 + 1 = 2

The optimal ordering is [0, 2, 1] with cost = 0 + 1 = 1.

Edge Cases

Alternative Approaches

While brute-force is sufficient here, it's worth noting the broader solution space:

Held-Karp DP (O(R² × 2^R)): For R=10, this is ~100K operations—much faster than 3.6M. The state is dp[mask][last] = minimum cost to visit routines in mask ending at last. This becomes preferable as R grows (though R ≤ 10 here).

Branch-and-bound DFS: Build the ordering incrementally, pruning when partial cost exceeds current best. This can be faster in practice for structured inputs.

We stick with permutation enumeration for clarity and because the constraint R ≤ 10 makes it more than fast enough.

Complete Solution

Full Java implementation on GitHub

Summary

• Model: Minimum Hamiltonian path on a complete graph with edge weights = dancer overlap
• Key optimization: Bitmask representation makes overlap computation O(1)
• Complexity: O(R! × R) time, O(R²) space—acceptable for R ≤ 10
• Correctness: Exhaustive enumeration guarantees optimality
• Implementation details: Symmetric overlap matrix, early termination, do-while permutation loop