PREFSUMMNMAX - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: harsh_h
Tester: mexomerf
Editorialist: iceknight1093

DIFFICULTY:

simple

PREREQUISITES:

None

PROBLEM:

You’re given an array B of length N.
Find any array A such that B_i = \sum_{j=1}^i A_j - (\max_{j=1}^i A_j) for every index i.

EXPLANATION:

Let’s try to find some relations between the elements of B.

For convenience, let’s define M_i = \max_{j\leq i} A_j and S_i = \sum_{j\leq i} A_j to be the maximum and sum till index i, respectively.
This means B_i = S_i - M_i.

Clearly, S_1 = M_1 = A_1 always, so B_1 = 0 must hold.
For i \gt 1,

  1. If M_i = M_{i-1} (so index i doesn’t contain a new maximum), we have
    B_i = S_i - M_i = (S_{i-1} + A_i) - M_{i-1} = B_{i-1} + A_i
  2. If M_i \neq M_{i-1}, we don’t get any such nice relation, since B_i changes not just by A_i, but also by the difference between M_i and M_{i-1}.

The first relation, B_i = B_{i-1} + A_i (when M_i = M_{i-1}) is particularly nice.
Since we only want to construct any array, as long as we can ensure that the maximum element never changes we’re good.

If we’re able to do this, we’ll obtain A_i = B_i - B_{i-1} for all i \gt 1.
That means, as long as A_1 is not smaller than any of these adjacent differences, the maximum won’t change - and the construction is valid!

A simple construction is thus to define A_i = B_i - B_{i-1} for i \gt 1, and then set A_1 to be the maximum of the other N-1 elements.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n = int(input())
    b = list(map(int, input().split()))
    a = [0]
    for i in range(1, n): a.append(b[i] - b[i-1])
    if n > 1: a[0] = max(a[1:])
    print(*a)
1 Like
2

I overcomplicated https://www.codechef.com/viewsolution/1097209136

1 Like
6

Failing for N = 1, because you are using INT_MIN < 2e6

1 Like
7

When I set a[0] = 2_000_000, I got Wa. But when I set a[0] = 2_000_000 - 1 I got WA. Why?

AC

private fun prefixMinMax(nums: IntArray): List<Int> {
    val n = nums.size
    val result = mutableListOf(2_000_000 - 1)
    for (i in 1 until n) {
        result.add(nums[i] - nums[i - 1])
    }
    return result
}

WA

private fun prefixMinMax(nums: IntArray): List<Int> {
    val n = nums.size
    val result = mutableListOf(2_000_000)
    for (i in 1 until n) {
        result.add(nums[i] - nums[i - 1])
    }
    return result
}
8

You have only one WA submission to the problem, which fails on the sample because it outputs

[2000000, -2, 3]
[2000000, -1, -1, 3]
[2000000, 2, 0, -6, -9]

rather than

2000000 -2 3
2000000 -1 -1 3
2000000 2 0 -6 -9

I took a look at the judge and it checks bounds correctly.

1 Like
9

Got it. I output the answer with wrong format. After fix it, the a[0] = 2_000_000 solution got AC.
Thanks! :wave: