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 $Ni+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:
EXPLANATION:subtask 1We enumerate $i$. For a specific $i$, we compute the sum of first $i$ elements($A[1\sim i]$) and the sum of last $Ni+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.
The overall complexity is $O(N^2)$. subtask 2We can compute $PrefixSum$ and $SuffixSum$ in $O(N)$ time: $$\begin{align*} PrefixSum(i)=&\begin{cases}0&i < 1\\PrefixSum(i1)+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:
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, 32bit integers aren't big enough to store such kind of numbers; we need 64bit integers. A simpler solutionWhat 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:
This approach is also $O(N)$ and is easier to implement. Also, it doesn't involve 64bit integers. AUTHOR'S AND TESTER'S SOLUTIONS:Author's solution can be found here(This is not author's, but Praveen's). asked 31 Aug '17, 17:33

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

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

some random explanation given here..dissappointment :( :/ answered 13 Sep '17, 00:46

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<=i;j++)" {="" temp="temp+array[j];" }="" <br=""/> for(long long k=i;k<variables;k++) {="" <br=""/> temp=temp+array[k];
} answered 21 Dec '17, 08:53

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
