Codeforces 1195 C. Basketball Exercise

This is a very typical dynamic programming problem. In this write-up, I will show three ways to solve it using dynamic programming.

Problem Analysis

First, we need to analyze the problem carefully. According to the statement, there are four restrictions we must respect when choosing students:

1. We choose players from left to right.
2. The index of each chosen player (except the first one) must be strictly greater than the index of the previous player.
3. Demid chooses students such that no two consecutive chosen students belong to the same row.
4. The total height of all chosen students must be as large as possible.

Given these conditions, we can try to define the states for dynamic programming.

When designing a DP state, we must ensure that it satisfies two important properties:

1. The state clearly reflects the restrictions above.
2. The state is independent of the future.

The second condition is especially important, because the core idea of dynamic programming is to derive the optimal result from the optimal previous state. In other words, we need to make sure that the current state contains enough information to determine the best future choice.

First Solution

Let us make the problem simpler. Since we can only choose people from left to right, one intuitive idea is to define dp[i], meaning the best possible combination when we reach the i-th position.

However, we also need to know which row the last chosen student came from. Therefore, a better state is dp[i][j].

We define dp[i][j] as:

• when we are at index i,
• what is the optimal result if we choose operation j.

Here, j is an integer in [0, 2]:

• j = 0: pick a student from row A
• j = 1: pick a student from row B
• j = 2: skip the current position

The meaning of dp[i][j] is the maximum total height we can obtain when we reach index i and perform operation j.

At the end, the answer is:

max(dp[n][0], dp[n][1], dp[n][2])

State Transition

Once we define the state, the next step is to derive the transition equation.

This part is fairly straightforward once the state is chosen. At least for this problem, the main work is just simulation.

A good approach is to start by writing the base cases.

Base case: i = 0

The answer is obvious: if i = 0, then no one has been chosen yet, so:

dp[0][0] = 0
dp[0][1] = 0
dp[0][2] = 0

Base case: i = 1

This means we are deciding what to do for the first student.

• If we choose a player from row A, we get the first student from row A: cpp dp[1][0] = rowA[0]

• If we choose a player from row B, we get the first student from row B: cpp dp[1][1] = rowB[0]

• If we skip the first student: cpp dp[1][2] = 0

General Case

Now let us consider the general case i.

For dp[i][0]

If we pick a player from row A at index i, then the transition must look like:

a[i] + max(...)

This means: we add the height of the current student and then take the best previous value that does not violate the rule that consecutive chosen students cannot come from the same row.

Since we picked from row A, the previous chosen student must not be from row A. Therefore, the previous state cannot be dp[i-1][0].

The valid previous options are:

• dp[i-1][1]
• dp[i-2][0]
• dp[i-1][2]

Thus, the transition is:

For dp[i][1]

Similarly, if we pick a player from row B, then:

For dp[i][2]

Skipping a player imposes no restriction, so:

The reason I use rowA[i-1] and rowB[i-1] is that I use 1-based indexing for the DP array, while the original arrays are 0-based.

C++ Implementation

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

#define ll long long
#define i128 __int128
#define vl vector<ll>
#define vb vector<bool>
#define vec vector
#define umap unordered_map
#define uset unordered_set
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define init(n) ll n; cin >> n;
#define printVec(v) for (int i = 0; i < v.size(); i++) cout << v[i] << " ";
#define printlnVec(v) for (int i = 0; i < v.size(); i++) cout << v[i] << " "; cout << "\n";

void setIO(string name = "") {
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr);
    if (!name.empty()) {
        freopen((name + ".in").c_str(), "r", stdin);
        freopen((name + ".out").c_str(), "w", stdout);
    }
}

int main() {
    setIO();
    int n;
    cin >> n;

    vector<ll> rowA(n), rowB(n);

    for (ll i = 0; i < n; i++) {
        cin >> rowA[i];
    }
    for (ll i = 0; i < n; i++) {
        cin >> rowB[i];
    }

    vector<vector<ll>> dp(n + 1, vector<ll>(3, 0));

    dp[0][0] = 0; // pick from row A
    dp[0][1] = 0; // pick from row B
    dp[0][2] = 0; // skip

    dp[1][0] = rowA[0];
    dp[1][1] = rowB[0];
    dp[1][2] = 0;

    for (ll i = 2; i <= n; i++) {
        dp[i][0] = max({dp[i - 1][1], dp[i - 2][0], dp[i - 1][2]}) + rowA[i - 1];
        dp[i][1] = max({dp[i - 2][1], dp[i - 1][0], dp[i - 1][2]}) + rowB[i - 1];
        dp[i][2] = max({dp[i - 1][0], dp[i - 1][1], dp[i - 1][2]});
    }

    cout << max(dp[n][0], max(dp[n][1], dp[n][2])) << '\n';
    return 0;
}

This code follows exactly the DP we discussed above.

Complexity

• Time complexity: O(n)
• Space complexity: O(3n)

This is already efficient enough to pass the problem, although it is not the most space-optimized version.

Can We Reduce the Number of States?

The code above uses 3 states, but we can actually reduce it to 2.

Why is dp[i][2] unnecessary?

Because skipping a position can be absorbed into a better state representation.

Why dp[i][2] Can Be Removed

Let us write:

• A_i = dp[i][0]
• B_i = dp[i][1]
• C_i = dp[i][2]

The original transitions are:

We claim that we can rewrite the first two equations without C.

Step 1: Expand C_{i-1}

For any index k ≥ 1:

Applying this to k = i-1 gives:

Step 2: Substitute into A_i

Let:

Substitute the expression for C_{i-1}:

Since max(x, x) = x, we can simplify this to:

The key observation is that C_{i-2} is never useful because it is always dominated by an existing term.

Step 3: A Useful Lemma

For all k ≥ 1:

Why?

From the transition for B_k:

Since heights are positive, we have:

The same argument applies to A_k.

So a skip is never better than choosing a positive-height student in the same prefix.

Step 4: Remove C_{i-2}

Since:

we can safely drop C_{i-2} from the maximum. Therefore:

By symmetry, we also get:

So the skip state is no longer necessary.

Final Answer Without C

The original answer was:

But since C_n is dominated by A_n or B_n, we can simply take:

With n ≥ 1 and A_0 = B_0 = 0, the final answer is just:

or, depending on the exact implementation, you may keep the previous values to avoid edge-case mistakes.

Optimized 2-State DP

Here is the optimized implementation:

vector<vector<ll>> dp(n + 1, vector<ll>(2, 0));

dp[0][0] = 0; // pick from row A
dp[0][1] = 0; // pick from row B

dp[1][0] = rowA[0];
dp[1][1] = rowB[0];

ll ans = max(dp[1][0], dp[1][1]);

for (ll i = 2; i <= n; i++) {
    dp[i][0] = max({dp[i - 2][0], dp[i - 1][1], dp[i - 2][1]}) + rowA[i - 1];
    dp[i][1] = max({dp[i - 1][0], dp[i - 2][1], dp[i - 2][0]}) + rowB[i - 1];
    ans = max({ans, dp[i][1], dp[i][0]});
}

cout << ans << '\n';

This version keeps only the two meaningful states and avoids the unnecessary skip state.

This proves that a 3-state DP is valid, but a 2-state DP is enough to solve the problem elegantly and efficiently.

However, there is still a things we can improve, which let space complexity euqual to O(1) We don't even have to store so much previious computation results. We can use a rolling array to store results.

int main() {
    setIO();
    int n;
    cin >> n;
    vector<ll> rowA(n),rowB(n);
    for(ll i=0;i<n;i++) {
        cin >> rowA[i];
    }
    for(ll i=0;i<n;i++) {
        cin >> rowB[i];
    }


    if (n == 1) {
        cout << max(rowA[0], rowB[0]) << endl;
        return 0;
    }
    
    vector<vector<ll>> dp(2, vector<ll>(2, 0));
    dp[0][0] = 0;          
    dp[0][1] = 0;
    dp[1][0] = rowA[0];
    dp[1][1] = rowB[0];

    for (ll i = 2; i <= n; i++) {
        ll cur_0 = max({dp[i % 2][0], dp[(i - 1) % 2][1], dp[i % 2][1]}) + rowA[i - 1];
        ll cur_1 = max({dp[(i - 1) % 2][0], dp[i % 2][1], dp[i % 2][0]}) + rowB[i - 1];
        dp[i % 2][0] = cur_0;
        dp[i % 2][1] = cur_1;
    }

    cout << max({dp[0][0], dp[0][1], dp[1][0], dp[1][1]}) << endl;
    return 0;
}