Codeforces Round 995 Problem G

problem link: Codeforces Round 995 Problem G

First, note that the problem constraints are as follows:

The first line contains two integers $n$ and $q$ ($1≤ n ≤20$; $1 ≤ q ≤ 2 \cdot 10^5$) — the number of snakes and the number of events.

This means we can use algorithms with high complexity with respect to $n$, since $n$ is only 20.

Since we know the order in which the snakes will be placed, we only need to know the minimum distance between any two snakes. To do this, we can assume that two snakes are adjacent at the beginning. We can use two variables to store the positions of the snakes. The left snake is at position $x$ and the right snake is at position $y$. Initially, set $x = 0$ and $y = 1$. Then we scan all movements with time complexity $O(q)$.

If the left snake enlarges, we move it to the right ($x += 1$). If the right snake shrinks, we also move it to the right ($y += 1$). If $x = y$, that means the two snakes meet, and we need to increase the distance between them. After increasing the distance, we can move the left snake to the right ($x += 1$), or move the right snake to the right ($y += 1$).

Using this algorithm, we can calculate the minimum distance between all snakes with time complexity $O(n^2 q)$.

(Note: The logic in the following C++ snippet for calculating min_dist might be flawed, as the movement rules for shrinking snakes could be misinterpreted. It is presented here as it was in the original thought process.)

vector<vector<int>> min_dist(n, vector<int>(n, 1e18));
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        if (i == j) {
            min_dist[i][j] = 0;
            continue;
        }
        int dis = 1;
        int x = 0, y = 1;
        for (auto &ele : v) {
            if (ele.first == i) { x += ele.second == '+' ? 1 : 0; }
            if (ele.first == j) { y += ele.second == '+' ? 0 : 1; }
            if (x == y) {
                dis++;
                x--;
            }
        }
        min_dist[i][j] = dis;
    }
}

The second part of the problem is to determine the order in which we should place the snakes. If we use brute force to solve this problem, the time complexity is $O(n! n^2 q)$, which is not acceptable. We need to find a better algorithm to solve this problem.

If we consider the following state for dynamic programming:

1. mask: a bitmask representing the set of snakes we have placed.
2. last: the last snake we placed in this set.

$dp[mask][last]$ is the minimum total length required to place the snakes represented by mask, with last being the last snake placed.

The transition function is as follows:

vector<vector<int>> dp(1 << n, vector<int>(n, 1e18)); // `mask` are placed and last is `last`
// init state
for (int i = 0; i < n; i++) { dp[1 << i][i] = 1; }
// dp loop
for (int mask = 1; mask < (1 << n); mask++) {
    for (int last = 0; last < n; last++) {
        if (!(mask & (1 << last))) continue; // `last` must be in `mask`
        if (mask == (1 << last)) continue; // Base case is already initialized
        int prev_mask = mask ^ (1 << last);
        for (int i = 0; i < n; i++) {
            if (prev_mask & (1 << i)) { // iterate through previous snakes `i`
                dp[mask][last] = min(dp[mask][last], dp[prev_mask][i] + min_dist[i][last]);
            }
        }
    }
}

The final answer is the minimum of $dp[(1 << n) - 1][i] + \text{enlargement\_of\_i}$ over all possible last snakes $i$.

    long long ans = 1e18;
    // last element increasement
    vector<int> enlargement(n, 0);
    for (auto &ele : v) {
        if (ele.second == '+') {
            enlargement[ele.first]++;
        }
    }
 
    for (int i = 0; i < n; i++) {
        ans = min(ans, dp[(1 << n) - 1][i] + enlargement[i]);
    }