I got TLE on test 14 with a solution that was completely correct. Then I changed one loop, the order in which I check indices, and it passed comfortably.
Nothing else changed. Same recursion, same math, same checks. Just the order. That trick is worth knowing, because it shows up in far more problems than this one.
The problem
Vlad has a permutation of length . For every he counts the subarrays whose minimum is , and writes that count into . You get and have to count how many permutations produce it, modulo . Here and .
The idea
Take any segment and let be the position of its minimum. Every subarray inside the segment has exactly one minimum, so the -values of a valid segment always add up to
The minimum splits the segment in two. Everything to its left is a smaller, independent copy of the same problem, and so is everything to its right. That’s a Cartesian tree, built from the top.
So how do you find when all you have is ? You look for the index where the left part sums to exactly and the right part sums to exactly . Prefix sums make that an check per index.
Once you have the split, counting is easy. The left side has values and the right side has . The values themselves don’t care about positions, only about relative order, so you pick which of the remaining values go to the right subtree:
If no index passes the check, the answer is 0.
Say the real minimum is at and you’re testing some . The right part already accounts for its internal subarrays. But the subarray crosses the boundary and its minimum sits at , on the right. That’s at least one extra subarray, so the right sum comes out strictly too big. The case is the mirror image, with the left sum too big. So for a valid array the first index that passes is the minimum, and you can stop searching there. I also brute-forced every permutation up to to be sure. The number of distinct valid arrays comes out to the Catalan numbers (1, 2, 5, 14, 42, …), exactly the number of Cartesian tree shapes. Cute.Why only one index can pass the check
Where it went wrong
My first version found the split with the obvious loop:
for (int i = l; i <= r; i++) {
if (leftSum(l, i) == tri(i - l) && rightSum(i, r) == tri(r - i)) {
// recurse on [l, i-1] and [i+1, r]
}
}Correct. Also quadratic.
Look at the second sample: a = 1 2 3 4, which comes from . The minimum of every segment is at its right end. The loop walks the entire segment to find it, peels off one element, then walks the entire rest again.
With that’s around steps. Test 14 was almost certainly one of these.
The fix
Check the candidates from both ends, alternating:
Both ends (AC)
for (int step = 0; step < len; step++) {
int i = (step % 2 == 0) ? l + step / 2 : r - step / 2;
// same check as before
}Left to right (TLE)
for (int i = l; i <= r; i++) {
// same check as before
}That’s it. The whole change.
Here’s why it works. If the split lands at distance from the nearer end, the alternating loop finds it in about steps. And is exactly the size of the smaller piece. So a split costs time proportional to the smaller side, never the bigger one:
That recurrence is , and the proof is a one-liner I really like. Charge the cost of each split to the elements of the smaller piece, one unit each. An element only gets charged when it lands in the smaller half, and each time that happens the segment it lives in at least halves in size. You can’t halve more than times. So each element pays at most , and the total is .
The skewed case that killed the first version now costs per level, since the split is at the right end and the loop checks second. A perfectly balanced split costs per level across levels. And everything in between is covered by the charging argument.
If this feels familiar, it should. It’s the same reasoning as small-to-large merging (DSU on tree), just applied to searching instead of merging.
Numbers
Same code, compiled with -O2, input a = 1 2 ... 500000:
| Scan order | Time |
|---|---|
| Left to right | over 20 s (I killed it) |
| Both ends, alternating | 0.1 s |
Not a constant factor. A different complexity class.
The full solution
This is a cleaned-up version of what I submitted, with my template and the segment-tree pruning stripped out since the complexity doesn’t need either. Run it on the samples below.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 1e9 + 7;
vector<ll> pre, fact, inv;
ll power(ll b, ll e) {
ll r = 1; b %= MOD;
for (; e; e >>= 1, b = b * b % MOD) if (e & 1) r = r * b % MOD;
return r;
}
ll C(int n, int k) { return fact[n] * inv[k] % MOD * inv[n - k] % MOD; }
ll tri(ll k) { return k * (k + 1) / 2; }
ll sum(int l, int r) { return pre[r + 1] - pre[l]; }
// Number of valid permutations for segment [l, r], 0 if none.
ll solve(int l, int r) {
if (l > r) return 1;
int len = r - l + 1;
for (int step = 0; step < len; step++) {
int i = (step % 2 == 0) ? l + step / 2 : r - step / 2;
if (sum(l, i - 1) == tri(i - l) && sum(i + 1, r) == tri(r - i)) {
ll L = solve(l, i - 1);
if (!L) return 0;
ll R = solve(i + 1, r);
return C(r - l, r - i) * L % MOD * R % MOD;
}
}
return 0;
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
const int MX = 500001;
fact.assign(MX, 1); inv.assign(MX, 1);
for (int i = 1; i < MX; i++) fact[i] = fact[i - 1] * i % MOD;
inv[MX - 1] = power(fact[MX - 1], MOD - 2);
for (int i = MX - 1; i > 0; i--) inv[i - 1] = inv[i] * i % MOD;
int t; cin >> t;
while (t--) {
int n; cin >> n;
pre.assign(n + 1, 0);
for (int i = 0; i < n; i++) { ll x; cin >> x; pre[i + 1] = pre[i] + x; }
if (pre[n] != tri(n)) { cout << 0 << "\n"; continue; }
cout << solve(0, n - 1) << "\n";
}
}sample Input: Expected: single element Input: Expected: balanced tree Input: Expected: skewed, n = 100000Test cases
4
3
1 4 1
4
1 2 3 4
4
1 6 1 2
3
3 3 32
1
3
01
1
111
3
1 4 12
The last test case is the skewed worst case at . It’s too big to show inline, so expand it for a preview, or grab everything with Download all.
Where else this shows up
Any time you recurse by splitting a range at a point you have to search for, ask one question: does finding the split cost the size of the whole range, or only the smaller side? If it’s the whole range, a skewed input will get you. Searching from both ends is the cheapest way to make it the smaller side.
It’s the same pattern behind “find the unique element, split around it” problems, where people usually reach for a sparse table or a stack. Sometimes you don’t need either. You just need to stop scanning from the left.
Next time you get a TLE on a divide and conquer you know is right, before you rewrite anything, check which way your loop is walking.
