×

# CHEFSUM - Editorial

Practice

Contest

Author: Prateek Gupta

Tester: Jingbo Shang

Editorialist: Hanlin Ren

Cakewalk

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:

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

# EXPLANATION:

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[i]\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)$.

We can compute $PrefixSum$ and $SuffixSum$ in $O(N)$ time: \begin{align*} PrefixSum(i)=&\begin{cases}0&i < 1\\PrefixSum(i-1)+A[i]&1\le i\le N\end{cases},\\ SuffixSum(i)=&\begin{cases}0&i > N\\SuffixSum(i+1)+A[i]&1\le i\le N\end{cases}. \end{align*}

Pseudocode:

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

Note that $PrefixSum(i)+SuffixSum(i)$ can be very large: if $N=10^5$ and all $A[i]$'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[i]$, 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[i]$. Let $m$ be the minimum element among $A$, we just find the smallest index $i$ that $A[i]=m$.

Pseudocode:

m = 100000 for i = 1 to N m = min(m, A[i]) for i = 1 to N if A[i] == 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

7★r_64
261924
accept rate: 16%

19.7k350498541

 0 In easy language you just have to find the minimum element and print out its 1 based index . Hope this helps the newbies. answered 11 Sep '17, 18:16 986●1●9 accept rate: 12%
 0 simply we just have to caluculate minimum element in array 1 based index(if more than one elements are minimum just print index of which element come first) answered 11 Sep '17, 21:09 533●1●12 accept rate: 3%
 0 some random explanation given here..dissappointment :( :/ answered 13 Sep '17, 00:46 67●1●7 accept rate: 6%

Please tell me What's wrong with my code.

Here it is-

# include<iostream>

using namespace std; int main() { long long test=0; cin>>test; while(test--) { long long variables,max=600000000000,index=0,temp=0; cin>>variables; long long array[variables]; for(long int i=0;i<variables;i++) {="" cin="">>array[i]; } for(long long i=0;i<variables;i++) {="" temp="0;" for(long="" long="" j="0;j&lt;=i;j++)" {="" temp="temp+array[j];" }="" <br=""/> for(long long k=i;k<variables;k++) {="" <br=""/> temp=temp+array[k]; }
if(max > temp) { index=i+1; max=temp; } } cout<<index<<endl; } return 0; }

1
accept rate: 0%

 0 Aim: find index 'i' where min(prefix[i] + suffix[i]) for elements in given array. SOLUTION: consider the case of 'n' number of elements present in the array, labelled as: a1, a2, a3,......an Consider the approach of iterating linearly over the array to generate a Prefix sum array. The Prefix array containing the sums are in the array: [a1, a1+a2, a1+a2+a3,.......,a1+a2+a3+....an] Prefix(first element)=a1 Prefix(second element)=a1+a2 Prefix(third element)=a1+a2+a3 Prefix(last element)=sum of all elements The Suffix array is found to be the reverse of the Prefix array Suffix array is labelled as follows: [a1+a2+a3+....an,......,an] Suffix(first element)=sum of all elements Suffix(second element)=sum of all elements (from second index onwards) Suffix(last element)=last element SUM array is the sum of prefix and suffix for each element 'i' in the array. let 'S' denote sum of all elements SUM array is described as follows: [a1+S,a2+S,a3+S,....,an+S] so the min value of the array can be found from the min value of the given array itself, thereon the min index can be found. Solution can be found with single traversal itself. complexity O(N) answered 01 Apr '18, 19:41 2★aswin_ts 1●1 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,498
×1,615
×286
×26

question asked: 31 Aug '17, 17:33

question was seen: 2,896 times

last updated: 01 Apr '18, 19:42