Problem A

Given an integer N, output N multiplied by 2.

Problem B

Statement

Given a 4×4 grid, output the grid rotated 180 degrees.

Solution

This section focuses on permutation operations for square matrices.

In the Cartesian coordinate system, three fundamental permutations are commonly used:

Permutation f (vertical flip): h[i][j] = g[N + 1 - i][j]

A B     D C
D C → A B

Permutation g (horizontal flip): h[i][j] = g[i][N + 1 - j]

A B     B A
D C → C D

Permutation h (diagonal flip along y=x): h[i][j] = g[j][i]

A B     C B
D C → D A

By composing these three permutations, various transformations can be achieved:

• h ∘ g ∘ V produces a 90-degree clockwise rotation. Here, h ∘ g gives: h[i][j] = g[N + 1 - j][i].
• h ∘ f ∘ V produces a 180-degree clockwise rotation. Here, h ∘ f gives: h[i][j] = g[N + 1 - i][N + 1 - j].

Implementation

const int SZ = 4;
std::vector<std::vector<char>> grid(SZ + 1, std::vector<char>(SZ + 1));

for (int i = 1; i <= SZ; i++) {
    for (int j = 1; j <= SZ; j++) {
        std::cin >> grid[i][j];
    }
}

for (int i = 1; i <= SZ; i++) {
    for (int j = 1; j <= SZ; j++) {
        std::cout << grid[SZ + 1 - i][SZ + 1 - j] << " \n"[j == SZ];
    }
}

Problem C

Statement

Starting with the sequence 1, 2, 3, 4, 5, 6 (1-indexed), perform N operations where the i-th operation swaps a[i mod 5 + 1] with a[i mod 5 + 2] for i = 0, 1, 2, ..., N-1. Output the sequence after N operations.

Constraints: 0 ≤ N ≤ 10^9

Solution

For circular swaps, each cycle represents a permutation. The cycle length s does not exceed the modulus, so s ≤ mod.

Observe that the swap operation swap(a[i], a[(i+1) mod n]) for i = 0, 1, ..., n-2 forms a cyclic left shift. Let this permutation be f.

Since for any f, there exists x such that f^x ∘ v = v, after n(n-1) operations the sequence returns to its original state. Therefore, we only need to simulate N mod (n(n-1)) times.

Simplle Approach (O(n²))

int arr[] = {0, 1, 2, 3, 4, 5, 6};
int N; std::cin >> N;
N %= 30;  // n * (n - 1) = 6 * 5 = 30

for (int i = 0; i < N; i++) {
    std::swap(arr[i % 5 + 1], arr[i % 5 + 2]);
}

for (int i = 1; i <= 6; i++) {
    std::cout << arr[i];
}
std::cout << "\n";

Optimiezd Approach (O(n))

Since f is a cyclic shift, f^x can be determined in O(1) and applied in O(n).

Let R = N mod (n(n-1)), which satisfies R < n(n-1).

Perform P = floor(R / (n-1)) cyclic left shifts (P < n), then process the remaining Q = R mod (n-1) individual swaps (Q < n = O(n)).

The cyclic shift maps positions as:

a[0] a[1] a[2] ... a[n-1]
a[P] a[P+1] a[P+2] ... a[(P-1) mod n]

1-indexed implementation:

const int n = 6;
int a[n + 1] = {0, 1, 2, 3, 4, 5, 6};
int N; std::cin >> N;
N %= n * (n - 1);

int P = N / (n - 1);
int Q = N % (n - 1);

int b[n + 1];
memcpy(b, a, sizeof b);
P++;
for (int i = 1; i <= n; i++) {
    a[i] = b[(P - 1) % n + 1];
    P++;
}

for (int i = 1; i <= Q; i++) {
    std::swap(a[i], a[i + 1]);
}

for (int i = 1; i <= n; i++) {
    std::cout << a[i];
}
std::cout << "\n";

Problem D

Statement

On an infinite integer number line, each coordinate contains a box. There are R red balls at position -100, G green balls at position 0, and B blue balls at position 100. In each operation, a ball can be moved to an adjacent box, but no box can contain two balls of the same color. Find the minimum number of operations to ensure each box contains at most one ball.

Solution 1: Minimum Cost Maximum Flow

This is a classic network flow problem.

Let N = max(100 + R + G + B). The range [-N, N] is sufficient to hold all balls; moving balls outside this range only wastes operations.

Construction:

• Source connects to positions -100, 0, 100 with capacities (R,0), (G,0), (B,0) respectively.
• Positions in [-N, N] connect to sink with capacity 1 and cost 0.
• Between these two sets, add edges with capacity 1 and cost equal to the distance between positions.

Solving this min-cost max-flow yields the answer. The time complexity is O(max_flow × V²) in the worst case.

Solution 2: Dynamic Programming

The same N bound applies. Since each position has 4 possibilities (empty, red, green, blue), we can use DP.

State: dp[i][r][g][b] = minimum operations considering position i with r red, g green, b blue balls remaining.

Initialize: dp[-N-1][R][G][B] = 0

Transition for k = 0,1,2,3 (empty, red, green, blue):

dp[i][r][g][b] = min(dp[i][r][g][b], dp[i-1][r][g][b])                                          // k=0
dp[i][r][g][b] = min(dp[i][r][g][b], dp[i-1][r+1][g][b] + |pos[1]-i|)    // k=1, red
dp[i][r][g][b] = min(dp[i][r][g][b], dp[i-1][r][g+1][b] + |pos[2]-i|)    // k=2, green
dp[i][r][g][b] = min(dp[i][r][g][b], dp[i-1][r][g][b+1] + |pos[3]-i|)    // k=3, blue

Time complexity: O((R+G+B) × R × G × B)

Space optimization: Since dp[i] only depends on dp[i-1], use rolling arrays to achieve O(R × G × B) space.

Further Optimization

Key observation: The balls must be arranged in three contiguous segments: red, then green, then blue.

Proof: If a red ball is to the right of a green ball, swapping them reduces total distance.

With positions fixed, each location has only two states: occupied or empty. Color no longer matters—only the total remaining balls need tracking.

The coler at position i can be determined directly:

• If consumed ≤ R: red ball
• If consumed ≤ R+G: green ball
• Otherwise: blue ball

Using a half-open interval array t = {-1, R, R+G, R+G+B} with lower_bound gives O(log 3) = O(1) lookup.

State: dp[i][j] = minimum operations considering position i with j balls remaining

Transition:

dp[i][j] = min(dp[i][j], dp[i-1][j])                                              // empty
dp[i][j] = min(dp[i][j], dp[i-1][j+1] + |pos[color]-i|)                           // place ball

Time complexity: O((R+G+B)²)

Space: O(R+G+B) using rolling arrays.

Final Implementation

const int INF = 1 << 30;

void updateMin(int& a, int b) { a = std::min(a, b); }

int main() {
    int R, G, B;
    std::cin >> R >> G >> B;
    
    const int N = 2000;
    const int total = R + G + B;
    std::vector<int> dp(total + 1, INF), prev(total + 1, INF);

    int offset = N + 1;
    int pos[] = {0, offset - 100, offset, offset + 100};
    
    prev[total] = 0;
    
    for (int i = 1; i <= 2 * N + 1; i++) {
        for (int j = 0; j <= total; j++) {
            updateMin(dp[j], prev[j]);
            
            if (j + 1 <= total) {
                int interval[] = {-1, R, R + G, R + G + B};
                int p = std::lower_bound(interval + 1, interval + 4, total - j) - interval;
                updateMin(dp[j], prev[j + 1] + std::abs(pos[p] - i));
            }
        }
        prev = dp;
        dp.assign(total + 1, INF);
    }
    
    std::cout << prev[0] << "\n";
    return 0;
}