### PROBLEM LINK:

**Author:** Prateek Gupta

**Tester:** Jingbo Shang

**Editorialist:** Hanlin Ren

### DIFFICULTY:

Cakewalk

### PREREQUISITES:

None

### PROBLEM:

You are given an array A of length N. Let PrefixSum(i) denote the sum of first i elements, and SuffixSum(i) denote the sum of last N-i+1 elements. Find an index i that PrefixSum(i)+SuffixSum(i) is the minimum. If there are many such indices, find the smallest one.

### QUICK EXPLANATION:

There are many solutions to this problem:

- We can calculate PrefixSum and SuffixSum in O(N) time, and just do what the problem asks; 64-bit integer types are needed;
- We can find the minimum element in the array, m, and output the smallest index i that A_i=m.

### EXPLANATION:

## subtask 1

We enumerate i. For a specific i, we compute the sum of first i elements(A[1\sim i]) and the sum of last N-i+1 elements(A[i\sim N]), then add the two sums together. We maintain the smallest answer ans and corresponding index. We enumerate i from 1 to N, so we only update the answer if PrefixSum(i)+SuffixSum(i) is strictly smaller than ans.

In this subtask, N\le 100 and A*\le 10^5, so PrefixSum(i)+SuffixSum(i)\le 10^7+10^5. When initializing ans, we need a number that’s big enough.

```
ans = 20000000 //2*10^7
for i = 1 to N
tmp = PrefixSum(i) + SuffixSum(i)
if tmp < ans then
ans = tmp
ans_i = i
print ans_i
```

The overall complexity is O(N^2).

## subtask 2

We can compute PrefixSum and SuffixSum in O(N) time:

Pseudocode:

```
PrefixSum[0] = 0
for i = 1 to N
PrefixSum* = PrefixSum[i - 1] + A*
SuffixSum[N + 1] = 0
for i = N downto 1
SuffixSum* = SuffixSum[i + 1] + A*
```

Note that PrefixSum(i)+SuffixSum(i) can be very large: if N=10^5 and all A*'s are 10^5, then this sum can be as large as 10^{10}+10^5, so we should initialize ans to be a number big enough(e.g. 10^{11}). Also, 32-bit integers aren’t big enough to store such kind of numbers; we need 64-bit integers.

## A simpler solution

What is PrefixSum(i)+SuffixSum(i)? this sums up all elements in 1\sim i, and all elements in i\sim N. Thus, let Sum=A[1]+A[2]+\dots+A[N] be the sum of all numbers, then PrefixSum(i)+SuffixSum(i)=Sum+A*, since only element i is counted twice, and all other elements are counted exactly once.

So, to find the index i that minimizes PrefixSum(i)+SuffixSum(i), we only need to find i that minimizes A*. Let m be the minimum element among A, we just find the smallest index i that A*=m.

Pseudocode:

```
m = 100000
for i = 1 to N
m = min(m, A*)
for i = 1 to N
if A* == m then
print i and break
```

This approach is also O(N) and is easier to implement. Also, it doesn’t involve 64-bit integers.

### AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here(This is not author’s, but Praveen’s).

Tester’s solution can be found here.

Editorialist’s solution can be found here