MINCOLREP - Editorial

editorial
, , ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: raysh07
Tester: raysh07
Editorialist: iceknight1093

DIFFICULTY:

Easy

PREREQUISITES:

Dynamic programming

PROBLEM:

You’re given an array A. You can perform the following operation:

  • Choose 1 \leq i \leq j \leq N such that A_i = A_j.
    Then, for each index k \in [i, j], set A_k to A_i.

Some elements of A are zeros, meaning they’re undefined.
Across all possible replacements of the zeros, find the minimum possible number of distinct elements in A after performing this operation several times.

EXPLANATION:

Recall from the solution to the easy version that if there were no zeros, the problem could be solved in \mathcal{O}(N) time with a relatively simple DP, which works as follows:

  • dp_i is the answer for the prefix ending at i.
  • \text{best}[x] is the minimum value of dp_{j-1} across all j with A_j = x so far.
  • Then, at each i, we first minimize \text{best}[A_i] with dp_{i-1}, and then set dp_i to 1 + \text{best}[A_i].

Let’s attempt to adapt this solution to this version when there are zeros.

The definitions of dp_i and \text{best}[x] don’t change.
Let’s look at index i.

If A_i = 0, we can immediately set dp_i = 1, because we can always just fix this 0 to be equal to A_1 and then cover the entire prefix.

If A_i \neq 0, we can, just as in the version without zeros, update \text{best}[A_i] and then set dp_i to \text{best}[A_i] + 1.
This takes care of the case where the segment ending at i starts at some existing occurrence of A_i.

However, now that there are zeros, we have another choice: we can choose any previous zero, set it to A_i, and then color the segment from this zero to A_i.
If the zero chosen is at index j, this gets us a value of dp_{j-1} + 1.

To speed this up, note that we can just do the exact same thing: let \text{best}[0] be the minimum value of dp_{j-1} across all positions with A_j = 0, then the best we can do is \text{best}[0] + 1.

This allows us to augment our solution quite easily, resulting in this as the final algorithm:

  • If A_i = 0, dp_i = 1.
  • Otherwise, dp_i = \min(\text{best}[A_i], \text{best}[0]) + 1.
  • Make sure to keep the \text{best} array updated appropriately.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Author's code (C++) 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (int)1e18

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

void Solve() 
{
    int n; cin >> n;
    
    vector <int> a(n + 1);
    for (int i = 1; i <= n; i++){
        cin >> a[i];
    }
    
    vector <int> dp(n + 1, INF);
    dp[0] = 0;
    
    vector <int> e(n + 1, INF);
    
    int X = INF;
    int mn = INF;
    
    for (int i = 1; i <= n; i++){
        // transport dp[i - 1] to e[a[i]] 
        if (a[i] == 0){
            X = min(X, dp[i - 1]);
            mn = min(mn, X);
        } else {
            e[a[i]] = min(e[a[i]], dp[i - 1]);
            mn = min(mn, e[a[i]]);
        }
        
        // end something here 
        if (a[i] == 0){
            dp[i] = min(dp[i], mn + 1);
        } else {
            dp[i] = min(dp[i], min(X, e[a[i]]) + 1);
        }
    }
    
    cout << dp[n] << "\n";
}

int32_t main() 
{
    auto begin = std::chrono::high_resolution_clock::now();
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    // freopen("in",  "r", stdin);
    // freopen("out", "w", stdout);
    
    cin >> t;
    for(int i = 1; i <= t; i++) 
    {
        //cout << "Case #" << i << ": ";
        Solve();
    }
    auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
    return 0;
}
Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))

    dp = [0]*n
    best = [n+1]*(n+1)
    for i in range(n):
        if i > 0: best[a[i]] = min(best[a[i]], dp[i-1])
        else: best[a[i]] = 0
        
        if a[i] == 0:
            dp[i] = 1
        else:
            dp[i] = min(best[0], best[a[i]]) + 1
    print(dp[n-1])
1 Like