CF: Mortal Combat Tower

1418C - Mortal Kombat Tower Problem — 1418C — Codeforces

Simple problem.... but solution 1 took me a long time to debug, mainly because there was a sneaky hidden bug

Solution 1: DP

Simple brute force memoization search of all cases:

State: $$$dp[i][j]$$$ means at position $$$j$$$ when switched to player $$$i\in[0,1]$$$ (0=my friend, 1=me), the minimum skip points used. So the answer is $$$min(dp[0][n],dp[1][n])$$$, checking at the end which player's side has the minimum skip points.

Initial state: $$$dp[1][0]=0$$$ means if switched to me at position 0 (although impossible since friend starts first), then 0 skip points were used.

Code:

#include <bits/stdc++.h>
using namespace std;

int main() {
    int test_case_num;
    cin >> test_case_num;

    for (int t = 0; t < test_case_num; t++) {
        int n;
        cin >> n;

        vector<int> bosses(n);
        for (int j = 0; j < n; j++) {
            cin >> bosses[j];
        }

        /*
         * dp[i][j] = the min amount of skip points
         * on turn i (your turn is 0), on the jth boss.
         * (1e9 to prevent overflow)
         */
        vector<vector<int>> dp(2, vector<int>(n + 1, 1e9));

        /*
         * base case:
         * your friend uses zero skip points before fighting any bosses.
         */
        dp[1][0] = 0;

        for (int j = 0; j < n; j++) {
            // the opposite player switches on the previous move.
            dp[0][j + 1] = min(dp[0][j + 1], dp[1][j] + bosses[j]);
            dp[1][j + 1] = min(dp[1][j + 1], dp[0][j]);

            // the opposite player switches from the previous two moves.
            if (j + 2 <= n) {
                dp[0][j + 2] =
                    min(dp[0][j + 2], dp[1][j] + bosses[j] + bosses[j + 1]);
                dp[1][j + 2] = min(dp[1][j + 2], dp[0][j]);
            }
        }
        cout << min(dp[0][n], dp[1][n]) << endl;
    }
}

The annoying part is, since we need to find min, the array should be initialized to infinity right? But the bug is that if I set it to INT_MAX, during the DP process it will increase above that, causing integer overflow to INT_MIN, and since we're always taking min, it gets carried to the end outputting INT_MIN. I spent so long debugging without realizing this sneaky issue...

Setting it smaller to 1e9 works fine, as it won't cause integer overflow.

Solution 2: Greedy

Friend must go first, so use skip points on first position if needed. The key is how to choose switches after that.

1 1 1 1 1 1

Consider a consecutive sequence of 1s, the optimal case should be me taking two 1s, switch (must switch) to friend using one skip point, then let me take two more...

We can observe the conclusion (quite difficult, I also saw it from the editorial): For a subsequence of $$$k$$$ consecutive 1s, minimum skip points needed is $$$\lfloor \frac{k}{3} \rfloor$$$. So, just count lengths of consecutive 1 sequences, calculate skip points used, done.

Code (not original, from Educational Codeforces Round 95 Editorial — Codeforces):

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
    freopen("input.txt", "r", stdin);
//  freopen("output.txt", "w", stdout);
#endif
    
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> a(n);
        for (auto &it : a) cin >> it;
        int ans = 0;
        ans += a[0] == 1;
        for (int i = 1; i < n; ++i) {
            if (a[i] == 0) {
                continue;
            }
            int j = i;
            while (j < n && a[j] == 1) {
                ++j;
            }
            ans += (j - i) / 3;
            i = j - 1;
        }
        cout << ans << endl;
    }
    
    return 0;
}