2222CUnreviewedunratedGPT-5.4 (high)

Median Partition

Progressive hints first, then the full explanation and implementation when you're ready to cash out.

dp math

Original problem

Review status

AI-generated and still unreviewed. Double-check the details before internalizing them.

Hints

Progressive nudges

Open only as much as you need to keep the solve alive.

Don’t start by trying every possible median. That road leads straight into the swamp. Ask yourself: if all parts have the same median $x$ , what must be true about the whole array?

For any odd-length segment with median $x$ , you know both $\#(\ge x) > \#(< x)$ and $\#(\le x) > \#(> x).$ Now sum these inequalities over all chosen segments. What does that force $x$ to be?

Once the target median is fixed to the median $M$ of the whole array, reduce every element in two different ways: $u_i = \begin{cases}1 & a_i \ge M\\-1 & a_i < M\end{cases}, \qquad v_i = \begin{cases}1 & a_i > M\\-1 & a_i \le M\end{cases}.$ For an odd segment $[l,r]$ , what conditions on $\sum u_i$ and $\sum v_i$ mean its median is exactly $M$ ?

With prefix sums $U$ and $V$ , you can test any odd segment $[l,r]$ in $O(1)$ : $U_r-U_{l-1} > 0 \quad\text{and}\quad V_r-V_{l-1} < 0.$ So now the problem is just: partition the array into the maximum number of odd-length segments satisfying that check.

Use DP on prefixes. Let $dp[i]$ be the maximum number of valid parts covering $a_1\dots a_i$ . Then $dp[i] = \max\limits_{0\le j<i,\; i-j\text{ odd},\; [j+1,i]\text{ valid}} (dp[j]+1).$ Initialize $dp[0]=0$ . Since validity is $O(1)$ and you try all $j$ , the whole thing is $O(n^2)$ .

Observation 1: the common median is forced

This is the first big punchline: the median of every piece cannot be some mysterious value you need to guess. It is already determined.

Suppose the partition exists and every odd-length segment has median $x$ . Then for every segment:

more than half of its elements are at least $x$ , so $\#(\ge x) > \#(<x),$
more than half of its elements are at most $x$ , so $\#(\le x) > \#(>x).$

Now sum these inequalities over all segments. The segments are disjoint and cover the whole array, so for the full array we get $\#(\ge x) > \#(<x), \qquad \#(\le x) > \#(>x).$ That means the median of the whole array is also $x$ .

So there is only one possible target median: $M = \text{median of the entire array}.$

That kills the annoying “try all values” idea stone dead. Good riddance.

Observation 2: checking whether a segment has median exactly $M$

For a fixed value $M$ , an odd-length segment has median exactly $M$ iff:

its median is at least $M$ ;
its median is not at least $M+1$ .

That suggests two standard transforms.

Define

1,& a_i \ge M,\\ -1,& a_i < M, \end{cases}$$ and $$v_i = \begin{cases} 1,& a_i > M,\\ -1,& a_i \le M. \end{cases}$$ Now take any **odd-length** segment $[l,r]$. ### Median at least $M$ The segment median is at least $M$ iff strictly more than half the elements are $\ge M$. Since the length is odd, that is equivalent to $$\sum_{i=l}^r u_i > 0.$$ ### Median at least $M+1$ Similarly, the segment median is at least $M+1$ iff strictly more than half the elements are $> M$, i.e. $$\sum_{i=l}^r v_i > 0.$$ Therefore, the segment has median **exactly** $M$ iff $$\sum_{i=l}^r u_i > 0 \quad\text{and}\quad \sum_{i=l}^r v_i < 0.$$ That second inequality is written as $<0$ because the segment length is odd, so the sum of $\pm1$ values can never be $0$. No weird tie case. Nice and clean. Build prefix sums $$U_i = \sum_{k=1}^i u_k, \qquad V_i = \sum_{k=1}^i v_k.$$ Then for any segment $[l,r]$ we can check validity in $O(1)$: $$U_r-U_{l-1} > 0 \quad\text{and}\quad V_r-V_{l-1} < 0.$$ --- ## Observation 3: now it’s just DP on prefixes Let $$dp[i] = \text{maximum number of valid segments covering } a_1\dots a_i.$$ Initialize $$dp[0]=0,$$ and all other states to something very negative. Transition: try the last segment as $[j+1, i]$. Its length must be odd, so $i-j$ must be odd. If that segment is valid, then $$dp[i] = \max(dp[i], dp[j] + 1).$$ So formally: $$dp[i] = \max_{\substack{0\le j<i \\ i-j\text{ odd} \\ [j+1,i]\text{ valid}}} (dp[j]+1).$$ The answer is $dp[n]$. --- ## Why this is fast enough For each test case: - computing the global median: $O(n \log n)$, - building prefix sums: $O(n)$, - DP with all transitions: $O(n^2)$. So total complexity is $$O(n^2)$$ per test case, with $$O(n)$$ memory. Given that the statement guarantees $$\sum n^2 \le 5000^2,$$ this is absolutely fine. Not even close to sweating. --- ## Tiny sanity check If the whole array median is $M$, then the whole array itself is always a valid segment, so $dp[n]$ is never impossible. That’s why the DP can safely start from the full truth and build up. The entire problem is basically: 1. realize the median is forced to be the global median, 2. convert “median exactly $M$” into two prefix-sum inequalities, 3. run a straightforward partition DP. That’s it. The trick is the first observation; without it, you’d waste time trying candidates and feel bad about your life choices.

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

using ll = long long;

void setIO() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
}

int main() {
    setIO();

    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> a(n + 1);
        vector<int> b;
        b.reserve(n);
        for (int i = 1; i <= n; ++i) {
            cin >> a[i];
            b.push_back(a[i]);
        }

        sort(b.begin(), b.end());
        int M = b[n / 2];

        vector<int> prefGe(n + 1, 0), prefGt(n + 1, 0);
        for (int i = 1; i <= n; ++i) {
            prefGe[i] = prefGe[i - 1] + (a[i] >= M ? 1 : -1);
            prefGt[i] = prefGt[i - 1] + (a[i] > M ? 1 : -1);
        }

        const int NEG = -1e9;
        vector<int> dp(n + 1, NEG);
        dp[0] = 0;

        for (int i = 1; i <= n; ++i) {
            for (int j = i - 1; j >= 0; j -= 2) { // odd length => i-j is odd
                if (dp[j] == NEG) continue;
                int s1 = prefGe[i] - prefGe[j];
                int s2 = prefGt[i] - prefGt[j];
                if (s1 > 0 && s2 < 0) {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
        }

        cout << dp[n] << '\n';
    }
}

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

using ll = long long;

void setIO() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
}

int main() {
    setIO();

    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> a(n + 1);
        vector<int> b;
        b.reserve(n);
        for (int i = 1; i <= n; ++i) {
            cin >> a[i];
            b.push_back(a[i]);
        }

        sort(b.begin(), b.end());
        int M = b[n / 2];

        vector<int> prefGe(n + 1, 0), prefGt(n + 1, 0);
        for (int i = 1; i <= n; ++i) {
            prefGe[i] = prefGe[i - 1] + (a[i] >= M ? 1 : -1);
            prefGt[i] = prefGt[i - 1] + (a[i] > M ? 1 : -1);
        }

        const int NEG = -1e9;
        vector<int> dp(n + 1, NEG);
        dp[0] = 0;

        for (int i = 1; i <= n; ++i) {
            for (int j = i - 1; j >= 0; j -= 2) { // odd length => i-j is odd
                if (dp[j] == NEG) continue;
                int s1 = prefGe[i] - prefGe[j];
                int s2 = prefGt[i] - prefGt[j];
                if (s1 > 0 && s2 < 0) {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
        }

        cout << dp[n] << '\n';
    }
}

View on Codeforces Back to the list

Median Partition

Progressive nudges

Full explanation

Observation 1: the common median is forced

Observation 2: checking whether a segment has median exactly $M$

Generated C++

Median Partition

Progressive nudges

Full explanation

Observation 1: the common median is forced

Observation 2: checking whether a segment has median exactly MMM

Generated C++

Observation 2: checking whether a segment has median exactly $M$