Search for a command to run...
Progressive hints first, then the full explanation and implementation when you're ready to cash out.
Review status
AI-generated and still unreviewed. Double-check the details before internalizing them.
Hints
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 , what must be true about the whole array?
For any odd-length segment with median , you know both and Now sum these inequalities over all chosen segments. What does that force to be?
Once the target median is fixed to the median of the whole array, reduce every element in two different ways: For an odd segment , what conditions on and mean its median is exactly ?
With prefix sums and , you can test any odd segment in : 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 be the maximum number of valid parts covering . Then Initialize . Since validity is and you try all , the whole thing is .
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 . Then for every segment:
Now sum these inequalities over all segments. The segments are disjoint and cover the whole array, so for the full array we get That means the median of the whole array is also .
So there is only one possible target median:
That kills the annoying “try all values” idea stone dead. Good riddance.
For a fixed value , an odd-length segment has median exactly iff:
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';
}
}