CHEFSUM - Editorial

editorial
, , ,
1

PROBLEM LINK:

Practice

Contest

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:

  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:

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[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).

subtask 2

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

\begin{aligned} 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{aligned}

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

2

In easy language you just have to find the minimum element and print out its 1 based index . Hope this helps the newbies.

3

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)

4

some random explanation given here…dissappointment :frowning: :confused:

5

Please tell me What’s wrong with my code.

Here it is-

#include
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<=i;j++)
{
temp=temp+array[j];
}
for(long long k=i;k<variables;k++)
{
temp=temp+array[k];
}
if(max > temp)
{
index=i+1;
max=temp;
}
}
cout<<index<<endl;
}
return 0;
}

6

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)