 # PLPROCESS - Editorial

Setter: Kanhaiya Mohan
Tester: Harris Leung
Editorialist: Aman Dwivedi

Simple

Prefix Sum

# PROBLEM:

There are N tasks waiting in line to be executed. The execution time for the i^{th} task is A_i seconds.

Chef has two processors to execute these N tasks. Both these processors work simultaneously. Each processor executes the assigned tasks one by one.

Chef assigns a prefix of these tasks to the first processor and the remaining tasks to the second processor.

# EXPLANATION:

Suppose there is only one processor so it makes sense that the total amount of time taken to execute N tasks will be a summation of all the times required by every task. Let’s say this value is S, i.e

S = \sum_{i=1}^{N}A

Now, suppose we introduced another processor, and now let’s do as the problem says i.e. assign some prefix to the processor 1 and the remaining task to the processor 2.

Let’s say the time required to complete the task that was given to processor 1 is T_1. Hence the processor 2 will be able to complete the task in S-T_1.

Now since the processors are running in parallel, hence the total time required to complete all tasks will be a maximum of T_1 and S-T_1.

Now the question arises, Which prefix do I need to assign to processor 1?

• It’s quite simple, just assign every possible prefix to the processor 1 and check which prefix assignment is giving us the minimum time to complete all the remaining tasks. You can maintain a prefix sum array to efficiently perform the calculations.

Finally, output the minimum time that you can achieve.

# TIME COMPLEXITY:

O(N) per test case

# SOLUTIONS:

Author
#include <bits/stdc++.h>
using namespace std;

int main() {
int t;
cin>>t;
while(t--){
int n;
cin>>n;
int a[n];
long long int sum = 0;
for(int i = 0; i<n; i++){
cin>>a[i];
sum += a[i];
}

long long int ans = sum;
long long int curr = 0;
for(int i = 0; i<n-1; i++){
curr += a[i];
ans = min(ans, max(curr, sum-curr));
}
cout<<ans<<endl;
}
return 0;
}


Tester
Editorialist
#include<bits/stdc++.h>
using namespace std;

#define int long long

void solve()
{
int n;
cin>>n;

int a[n];
int pref[n];

for(int i=0;i<n;i++)
{
cin>>a[i];
pref[i] = (i>0)?pref[i-1]+a[i]:a[i];
}

int ans = pref[n-1];

for(int i=0;i<n;i++)
{
int rem_sum = pref[n-1]-pref[i];
rem_sum = max(0ll,rem_sum-pref[i]);
ans = min(ans,pref[i]+rem_sum);
}

cout<<ans<<"\n";
}

int32_t main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);

int t;
cin>>t;

while(t--)
solve();

return 0;
}


1 Like

It is mentioned that processor 1 can only take prefixes, and since [8, 2, 1] is not a prefix, it is not a valid solution.

1 Like

Why this solution is giving the wrong answer
Solution: 59265032 | CodeChef

1 Like

Integer overflow. Use long long instead.

1 Like

Consier the test case:

3
3 1 1

1 Like

4 Likes

why my solution is wrong?
https://www.codechef.com/viewsolution/59345393

can anyone tell me my mistake please??

#include<bits/stdc++.h>
using namespace std;
using ll = int long long;
int main(){
ll T;
cin>>T;
while(T–){
ll n;
cin>>n;
ll a[n+2];
ll sum = 0;
for(int i=0;i<n;i++){
cin>>a[i];
sum += a[i];
}
if(n==1)
cout<<a<<"\n";

else{
map<int,int>m;
int sum1 = 0;

for(int i=0;i<n-1;i++){
sum = sum -a[i];
sum1 =sum1 + a[i];

m[abs(sum-sum1)] = max(sum,sum1);

}
for(auto it:m){
cout<<it.second<<"\n";
break;
}
}
}
return 0;
}

it is showing wrong on test case 3

May be integer overflow while using map

1 Like

can anyone tell me why my submission is wrong
https://www.codechef.com/viewsolution/59349491

1 Like

how can i correct that??

i think u have the same problem like me…i also got WA on third test case

initialize d=sum not INT_MAX i too had same problem

replace all int by long long

#include<bits/stdc++.h>
using namespace std;
using ll =  long long;
int main(){
ll T;
cin>>T;
while(T--){
ll n;
cin>>n;
ll a[n+2];
ll sum = 0;
for(int i=0;i<n;i++){
cin>>a[i];
sum += a[i];
}
if(n==1)
cout<<a<<"\n";

else{
map<long long,long long>m;
long long sum1 = 0;

for(long long i=0;i<n-1;i++){
sum = sum -a[i];
sum1 =sum1 + a[i];

m[abs(sum-sum1)] = max(sum,sum1);

}
for(auto it:m){
cout<<it.second<<"\n";
break;
}
}
}
return 0;
}

1 Like

it passed all test case…thank u

Use long , i also faced the same issue !
Solution

1 Like

Use long !
Solution

I got the same error ! Use long in sum in place of int , it will solve your problem !

[type or paste code here](https://www.codechef.com/viewsolution/59297791)