CF 105819K - Not Japanese Triangle
We only know the last row of a triangular array. Every value above it is defined recursively as the minimum of the two values directly below it. If the last row is $$b1,b2,dots,bn$$ then the row above it contains $$min(b1,b2),min(b2,b3),dots$$ and the process continues upward.
CF 105819K - Not Japanese Triangle
Rating: -
Tags: -
Solve time: 50s
Verified: yes
Solution
Problem Understanding
We only know the last row of a triangular array. Every value above it is defined recursively as the minimum of the two values directly below it.
If the last row is
$$b_1,b_2,\dots,b_n$$
then the row above it contains
$$\min(b_1,b_2),\min(b_2,b_3),\dots$$
and the process continues upward.
The task is not to reconstruct the entire triangle explicitly. We only need the sum of every row.
A useful observation appears immediately if we expand the recurrence a few levels.
For a row that is $k$ levels above the bottom, each entry becomes the minimum of a contiguous segment of the bottom row. More precisely,
$$a_{i,j}=\min(b_j,b_{j+1},\dots,b_{j+n-i})$$
So the sum of row $i$ is exactly the sum of minimum values over all subarrays of the bottom row having length
$$n-i+1.$$
The problem is equivalent to computing, for every subarray length $L$, the sum of minima of all subarrays of length $L$.
The constraint $n \le 10^5$ immediately rules out any approach that explicitly generates rows of the triangle. The triangle contains $O(n^2)$ values, which would be around $5 \cdot 10^9$ cells in the worst case.
We need something close to $O(n \log n)$ or $O(n)$.
A common source of mistakes is handling equal values incorrectly when determining which element is considered the minimum of a subarray.
Consider:
3
5 5 5
Every subarray minimum is 5. If both directions use a strict comparison, some subarrays get counted multiple times. If both directions use a non-strict comparison, some subarrays are missed. The standard fix is to use one strict side and one non-strict side.
Another easy mistake is forgetting that the top row corresponds to the longest subarray length.
Example:
3
1 2 3
The row sums are:
1
2
6
The top row is the minimum of the entire array, not the minimum of a single element.
Approaches
A direct simulation is easy to describe.
Starting from the last row, repeatedly build the row above by taking adjacent minima. Each row takes linear time in its length. The total work becomes
$$n+(n-1)+\cdots+1 = O(n^2).$$
This is correct because it exactly follows the definition of the triangle. Unfortunately, with $n=10^5$, it would require roughly $5 \cdot 10^9$ operations.
The key observation is that every row corresponds to minima of fixed-length subarrays in the bottom row.
Let
$$S_L$$
be the sum of minima of all subarrays of length $L$.
Then the required answers are simply
$$S_n,S_{n-1},\dots,S_1.$$
Now the problem becomes: compute the sum of subarray minima simultaneously for every possible length.
For a fixed position $i$, suppose $b_i$ is chosen as the representative minimum of a subarray.
Using a monotonic stack, we find:
$$A=i-\text{previous strictly smaller}$$
and
$$B=\text{next smaller-or-equal}-i.$$
Then $b_i$ is the minimum of exactly $A \cdot B$ subarrays.
More importantly, for every subarray length, the number of such subarrays forms a very simple shape:
$$1,2,3,\dots,x,x,\dots,x,\dots,3,2,1$$
where
$$x=\min(A,B).$$
This piecewise-linear structure lets us add contributions with range updates instead of touching every length individually.
Using two difference arrays, we can add linear functions over intervals in $O(1)$ per element. After processing all elements, a prefix sweep reconstructs every $S_L$.
The entire solution runs in linear time.
| Approach | Time Complexity | Space Complexity | Verdict |
|---|---|---|---|
| Brute Force triangle construction | $O(n^2)$ | $O(n)$ | Too slow |
| Monotonic stack + range linear updates | $O(n)$ | $O(n)$ | Accepted |
Algorithm Walkthrough
- Read the bottom row $b$.
- Compute the previous strictly smaller element for every position using an increasing monotonic stack.
- Compute the next smaller-or-equal element for every position using another monotonic stack.
- For each position $i$, let
$$A=i-\text{prevLess}[i]$$
and
$$B=\text{nextLessEq}[i]-i.$$
These are the numbers of valid left and right extensions while keeping $b_i$ as the chosen minimum. 5. Let
$$x=\min(A,B), \quad y=\max(A,B).$$
For every subarray length, the count contributed by this element is:
$$1,2,\dots,x,$$
then a plateau of value $x$,
then
$$x-1,x-2,\dots,1.$$ 6. Add the contribution $b_i \cdot \text{count}$ to all affected lengths using three range updates:
$$b_i \cdot L$$
on $[1,x]$,
$$b_i \cdot x$$
on $[x+1,y]$,
and
$$b_i \cdot (A+B-L)$$
on $[y+1,A+B-1]$. 7. Store range updates in difference arrays representing functions of the form
$$p \cdot L + q.$$ 8. Perform a prefix sweep to recover every $S_L$. 9. Output
$$S_n,S_{n-1},\dots,S_1,$$
because row $i$ corresponds to window length $n-i+1$.
Why it works
Each subarray has exactly one representative minimum because of the strict/non-strict tie-breaking rule used in the monotonic stacks.
For a fixed element $b_i$, every valid left extension and right extension combination generates exactly one subarray where $b_i$ is the chosen minimum. The number of combinations producing a given length depends only on $A$ and $B$, yielding the triangular-plateau-triangular pattern above.
The algorithm adds the contribution of every representative minimum to every length it belongs to. Since every subarray is counted once and only once, the resulting value $S_L$ is exactly the sum of minima of all length-$L$ subarrays.
Python Solution
import sys
input = sys.stdin.readline
def add_linear(diff_a, diff_b, l, r, a, b):
if l > r:
return
diff_a[l] += a
diff_a[r + 1] -= a
diff_b[l] += b
diff_b[r + 1] -= b
n = int(input())
arr = list(map(int, input().split()))
prev_less = [-1] * n
stack = []
for i in range(n):
while stack and arr[stack[-1]] >= arr[i]:
stack.pop()
prev_less[i] = stack[-1] if stack else -1
stack.append(i)
next_less_eq = [n] * n
stack = []
for i in range(n - 1, -1, -1):
while stack and arr[stack[-1]] > arr[i]:
stack.pop()
next_less_eq[i] = stack[-1] if stack else n
stack.append(i)
diff_a = [0] * (n + 3)
diff_b = [0] * (n + 3)
for i, v in enumerate(arr):
A = i - prev_less[i]
B = next_less_eq[i] - i
x = min(A, B)
y = max(A, B)
add_linear(diff_a, diff_b, 1, x, v, 0)
add_linear(diff_a, diff_b, x + 1, y, 0, v * x)
add_linear(
diff_a,
diff_b,
y + 1,
A + B - 1,
-v,
v * (A + B)
)
sums = [0] * (n + 1)
cur_a = 0
cur_b = 0
for length in range(1, n + 1):
cur_a += diff_a[length]
cur_b += diff_b[length]
sums[length] = cur_a * length + cur_b
ans = [str(sums[length]) for length in range(n, 0, -1)]
print(" ".join(ans))
The first stack computes previous strictly smaller elements. Equal values are removed, which guarantees a unique ownership rule for subarrays.
The second stack computes next smaller-or-equal elements. Using the opposite inequality is what prevents double counting when equal values appear.
The helper add_linear performs range updates of functions of the form
$$a \cdot L + b.$$
After all updates are recorded, a single prefix pass reconstructs the actual contribution for each length.
The final reversal is important. Length $n$ corresponds to the top row, length $1$ corresponds to the bottom row.
Worked Examples
Example 1
Input:
6
1 2 1 2 2 6
The sums of subarray minima by length are:
| Length | Sum of minima |
|---|---|
| 1 | 14 |
| 2 | 7 |
| 3 | 5 |
| 4 | 3 |
| 5 | 2 |
| 6 | 1 |
Output is printed from length 6 down to length 1:
| Row | Corresponding length | Sum |
|---|---|---|
| 1 | 6 | 1 |
| 2 | 5 | 2 |
| 3 | 4 | 3 |
| 4 | 3 | 5 |
| 5 | 2 | 7 |
| 6 | 1 | 14 |
This confirms the mapping between rows and window lengths.
Example 2
Input:
3
5 5 5
Subarrays:
| Length | Subarrays | Minima sum |
|---|---|---|
| 1 | [5] [5] [5] | 15 |
| 2 | [5,5] [5,5] | 10 |
| 3 | [5,5,5] | 5 |
Output:
5 10 15
This example demonstrates why careful tie handling is required. Every subarray minimum is equal, yet each subarray must still be counted exactly once.
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | $O(n)$ | Two stack passes, one contribution pass, one prefix sweep |
| Space | $O(n)$ | Stacks, boundary arrays, and difference arrays |
The solution scales comfortably to $10^5$ elements. Every index is pushed and popped from each stack at most once, and every contribution is processed in constant time.
Test Cases
# helper: run solution on input string, return output string
import sys
import io
def solve(inp: str) -> str:
sys.stdin = io.StringIO(inp)
input = sys.stdin.readline
n = int(input())
arr = list(map(int, input().split()))
prev_less = [-1] * n
stack = []
for i in range(n):
while stack and arr[stack[-1]] >= arr[i]:
stack.pop()
prev_less[i] = stack[-1] if stack else -1
stack.append(i)
next_less_eq = [n] * n
stack = []
for i in range(n - 1, -1, -1):
while stack and arr[stack[-1]] > arr[i]:
stack.pop()
next_less_eq[i] = stack[-1] if stack else n
stack.append(i)
da = [0] * (n + 3)
db = [0] * (n + 3)
def add(l, r, a, b):
if l > r:
return
da[l] += a
da[r + 1] -= a
db[l] += b
db[r + 1] -= b
for i, v in enumerate(arr):
A = i - prev_less[i]
B = next_less_eq[i] - i
x = min(A, B)
y = max(A, B)
add(1, x, v, 0)
add(x + 1, y, 0, v * x)
add(y + 1, A + B - 1, -v, v * (A + B))
cur_a = cur_b = 0
res = [0] * (n + 1)
for L in range(1, n + 1):
cur_a += da[L]
cur_b += db[L]
res[L] = cur_a * L + cur_b
return " ".join(str(res[L]) for L in range(n, 0, -1))
# provided samples
assert solve("6\n1 2 1 2 2 6\n") == "1 2 3 5 7 14"
assert solve("11\n14 15 20 10 1 16 1 14 5 19 5\n") == "1 2 3 4 5 6 7 21 39 58 120"
# custom cases
assert solve("2\n1 2\n") == "1 3"
assert solve("3\n5 5 5\n") == "5 10 15"
assert solve("3\n1 2 3\n") == "1 2 6"
assert solve("4\n4 3 2 1\n") == "1 3 6 10"
| Test input | Expected output | What it validates |
|---|---|---|
2 / 1 2 |
1 3 |
Minimum valid size |
3 / 5 5 5 |
5 10 15 |
Equal values and tie handling |
3 / 1 2 3 |
1 2 6 |
Strictly increasing sequence |
4 / 4 3 2 1 |
1 3 6 10 |
Strictly decreasing sequence |
Edge Cases
Consider:
3
5 5 5
The previous-less stack uses a strict boundary and the next boundary is non-strict. The middle subarray [5,5] is assigned to exactly one position instead of both. The algorithm produces:
5 10 15
which matches the true row sums.
Consider:
3
1 2 3
The top row corresponds to the minimum of the entire array:
[1]
not to a single bottom element. The computed length sums are:
L=1 -> 6
L=2 -> 2
L=3 -> 1
and the output becomes:
1 2 6
which is exactly the sequence of row sums from top to bottom.
Consider:
4
4 3 2 1
Every longer subarray has its minimum at the far right. The monotonic stack still gives correct spans:
length 1 -> 10
length 2 -> 6
length 3 -> 3
length 4 -> 1
The output is:
1 3 6 10
showing that highly unbalanced spans are handled correctly by the piecewise-linear contribution formula.