Fady and Stable Arrays#12482

Fady and Stable Arrays (Editorial)

Problem Author:	Fady Rafat (FADY)
Prepared by:	Fady Rafat (FADY)
Edited by:	Hasan Saleh (MathModel)

Solution

General Idea: We need to count distinct stable arrays (no two adjacent elements equal) that can be formed by applying operations on the original array.

Key Observation:

When we apply the operation on two adjacent equal elements $a_{i} = a_{i + 1} = v$ a_i = a_{i+1} = v, we replace them with a single element of value $v + 1$ v + 1. This means we can "merge" adjacent blocks of equal values into higher values.

More formally, a contiguous subarray of identical values $[v, v, \dots, v]$ [v, v, \ldots, v] of length $2^{k}$ 2^k can be merged into a single element of value $v + k$ v + k.

DP Formulation:

Let $L [i] [v]$ = the leftmost starting index such that the subarray $a [L [i] [v] \dots i]$ a[L[i][v] \ldots i] can be merged into value $v$ .

This can be computed as:

$L [i] [a [i]] = i$ L[i][a[i]] = i (a single element merges to itself)
$L [i] [v] = L [L [i] [v - 1] - 1] [v - 1]$ L[i][v] = L[L[i][v-1] - 1][v-1] if the subarray ending at $i$ that merges to $v - 1$ v-1 can be preceded by another subarray that also merges to $v - 1$ v-1

Let $d p [i] [v]$ dp[i][v] = number of stable arrays ending at position $i$ with last element value $v$ .

Let $an s [i]$ = total number of stable arrays ending at position $i$ .

The transition is:

If $L [i] [v] = 0$ L[i][v] = 0: $d p [i] [v] + = 1$ dp[i][v] += 1 (the entire prefix merges to $v$ )
Otherwise: $d p [i] [v] + = an s [L [i] [v] - 1] - d p [L [i] [v] - 1] [v]$ dp[i][v] += ans[L[i][v] - 1] - dp[L[i][v] - 1][v]

We subtract $d p [L [i] [v] - 1] [v]$ dp[L[i][v] - 1][v] to avoid two adjacent blocks with the same value $v$ (stability condition).

Finally:

an s [i] = v \sum d p [i] [v]

ans[i] = \sum_{v} dp[i][v]

The answer is $an s [n - 1]$ ans[n-1].

Complexity Analysis:

$L [i] [v]$ computation: $O (n \cdot V)$ \mathcal{O}(n \cdot V) where $V = 80 + lo g_{2} (n) \approx 102$ V = 80 + \log_2(n) \approx 102.

$d p$ computation: $O (n \cdot V)$ \mathcal{O}(n \cdot V).

Total per test case: $O (n \cdot V)$ \mathcal{O}(n \cdot V).

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

const int MOD = 1e9 + 7;
const int MAX_V = 102;

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++)
        cin >> a[i];
    
    vector<vector<int>> L(n, vector<int>(MAX_V, -1));
    vector<vector<long long>> dp(n, vector<long long>(MAX_V, 0));
    vector<long long> ans(n, 0);
    
    for (int i = 0; i < n; i++) {
        L[i][a[i]] = i;
        for (int v = a[i] + 1; v < MAX_V; v++) {
            int right_start = L[i][v - 1];
            if (right_start > 0) {
                int left_start = L[right_start - 1][v - 1];
                if (left_start != -1)
                    L[i][v] = left_start;
            }
        }
        for (int v = 0; v < MAX_V; v++) {
            int start = L[i][v];
            if (start == -1) continue;
            if (start == 0) {
                dp[i][v] = (dp[i][v] + 1) % MOD;
            } else {
                long long ways = (ans[start - 1] - dp[start - 1][v] + MOD) % MOD;
                dp[i][v] = (dp[i][v] + ways) % MOD;
            }
            ans[i] = (ans[i] + dp[i][v]) % MOD;
        }
    }
    
    cout << ans[n - 1] << "\n";
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}