PLPROCESS - Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4

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

DIFFICULTY:

Simple

PREREQUISITES:

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

@admin could you please provide test case 4? Thank you.

1 Like

Integer overflow. Use long long instead.

1 Like

Consier the test case:

3
3 1 1
1 Like

@admin could you please provide test case 2? Thank you.

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[0]<<"\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[0]<<"\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)