You are not logged in. Please login at www.codechef.com to post your questions!

×

CHEFSUM - Editorial

0
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{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

asked 31 Aug '17, 17:33

r_64's gravatar image

7★r_64
261923
accept rate: 16%

edited 11 Sep '17, 17:41

admin's gravatar image

0★admin ♦♦
19.6k349497539


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

link

answered 11 Sep '17, 18:16

trashmaster's gravatar image

2★trashmaster
98619
accept rate: 12%

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)

link

answered 11 Sep '17, 21:09

hemant_dhanuka's gravatar image

5★hemant_dhanuka
533112
accept rate: 3%

edited 11 Sep '17, 21:09

some random explanation given here..dissappointment :( :/

link

answered 13 Sep '17, 00:46

ruhul1995's gravatar image

1★ruhul1995
6717
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; }

link

answered 21 Dec '17, 08:53

abhyuday18's gravatar image

1★abhyuday18
1
accept rate: 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)

link

answered 01 Apr, 19:41

aswin_ts's gravatar image

1★aswin_ts
11
accept rate: 0%

edited 01 Apr, 19:42

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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,129
×1,556
×286
×26

question asked: 31 Aug '17, 17:33

question was seen: 2,835 times

last updated: 01 Apr, 19:42