Codeforce Round 995 Problem G

problem link: Codeforce 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 \dot 10^5$) — the number of snakes and the number of events.

That means it allows us to use very complex algorithms to solve the problem since $n$ is only $20$.

Since we know the order the snakes will place. Then we only need to know the minimum distance between the snakes. To do this, we just support that two snakes are adjacent at the beginning. We also do not need to know the length of the snakes, so we just use two variables to store the position 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, then we just simply move it to the right, which is $ x += 1$. If the right snake shrinks, we also move it to the right, which is $y += 1$. If $x = y$, that means the two snakes meet; we need to increase the distance between the snakes. 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)$.

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 the problem is to make sure what kind of order 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 think consider following state for dynamic programming:

1. mask is the snake we have placed.
2. last is the last snake we placed.

$dp[mask][last]$ is the minimum distance we need to place the snakes.

The transfer function is as follows:

\[dp[mask][last] = \min_{i \in mask} dp[mask \oplus (1 << last)][i] + min\_dist[i][last]\]

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 = 0; mask < (1 << n); mask++) {
    for (int last = 0; last < n; last++) {
        // dp[mask][last] <-- min dp[mask ^ (1 << last)][i] + min_dist[i][last]
        // if mask has last bit set, then skip (or only last bit set)
        if ((mask & (1 << last)) == 0) continue;
        if (mask == (1 << last)) continue;
        for (int i = 0; i < n; i++) {
            if ((mask & (1 << i)) == 0) continue;
            dp[mask][last] = min(dp[mask][last], dp[mask ^ (1 << last)][i] + min_dist[i][last]);
        }
    }
}

The final answer is $dp[(1 « n) - 1][i] + \text{i enlarged size}$ where $i$ is the last snake we placed.

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