Equal Sum Subarrays | Code Joint

**Note: The time limit for this problem is 3s, 1.5x the default.**

FJ gave Bessie an array $a$ of length $N$ ( $2 \leq N \leq 500, - 1 0^{15} \leq a_{i} \leq 1 0^{15}$ ) with all $\frac{N ( N + 1 )}{2}$ contiguous subarray sums distinct. For each index $i \in [1, N]$ , help Bessie compute the minimum amount it suffices to change $a_{i}$ by so that there are two different contiguous subarrays of $a$ with equal sum.

Decreasing $a_{1}$ by $2$ would result in $a_{1} + a_{2} = a_{2}$ . Similarly, increasing $a_{2}$ by $3$ would result in $a_{1} + a_{2} = a_{1}$ .

Increasing $a_{1}$ or decreasing $a_{3}$ by $1$ would result in $a_{1} = a_{3}$ . Increasing $a_{2}$ by $6$ would result in $a_{1} = a_{1} + a_{2} + a_{3}$ .

SCORING:

Input 3: $N \leq 40$
Input 4: $N \leq 80$
Inputs 5-7: $N \leq 200$
Inputs 8-16: No additional constraints.

Problem credits: Benjamin Qi

Source: USA Computing Olympiad.

Input Format

The first line contains $N$ .

The next line contains $a_{1}, \dots, a_{N}$ (the elements of $a$ , in order).

Output Format

One line for each index $i \in [1, N]$ .

Sample Input 1

2 2 -3

Sample Output 1

2 3

Sample Input 2

3 3 -10 4

Sample Output 2

1 6 1

Submit

Language