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
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;
}