PROBLEM LINK:
Setter: a0n0k0i0t
Tester: a0n0k0i0t
Editorialist: a0n0k0i0t
PROBLEM
You are travelling on a road with two lanes A and B. You are initially at position 0. You need to reach your home at position N+1. On each of the lane A and B there are N tollbooths which comes in your way to home. The tollbooths are at positions 1,2,3.., N. Cost of crossing i_{th} tollbooth in lane A and lane B is A_i and B_i respectively. You want to reach your home by spending as less money as possible but there are some rules you should follow for your journey:
- you can start your journey at any of the lane A or B and can also end your journey at any of the lane A or B.
- you can switch the lanes at most one time
- you can switch lanes at any of the positions 1,2,3..N
Determine the minimum cost you must pay to reach your home
DIFFICULTY:
Easy
PREREQUISITES:
Prefix Sum , Suffix Sum
EXPLANATION:
Case I: When you don’t switch lanes
Then the answer is simply the minimum of sum of array A and sum of Array B.
Case II: When you switch the lane from A to B
In this case if you switch at i_{th} position you are paying ((sum(A_1 to A_i)) + sum(B_i to B_N))
We have to find minimum cost of \forall i \in (1,2,..N).
Brute-Force (Gives TLE)
One way to do is iterating over all i and compute sum(A_1 to A_i) + sum(B_i to B_N) over all i and find minimum.
Time complexity: O(N^2)
Optimized Approach
Instead of computing sum(A_1 to A_i) for all i , we can precompute the prefix sum of the array A in preA , where preA_i = sum(A_1 to A_i) .
preA[1]=A[1]; (for i==1)
preA[i]=preA[i-1]+A[i]; (for 2<=i<=N)
In similar way to compute sum(B_i to B_N) , we can precomute the suffix sum of the array B in sufB , where sufB_i = sum(B_i to B_N) .
sufB[N]=B[N]; (for i==1)
sufB[i]=sufB[i+1]+B[i]; (for 2<=i<=N)
Now if you switch lane at i_{th} position cost will be preA[i]+sufB[i] .
Find min( preA[i]+sufB[i]) over all i.
Case III: When you switch the lane from B to A
In this case if you switch at i_{th} position you are paying ((sum(B_1 to B_i)) + sum(A_i to A_N))
This is very similar to Case II ,just you have to find preB and sufA in this case.
preB[1]=B[1]; (for i==1)
preB[i]=preB[i-1]+B[i]; (for 2<=i<=N)
sufA[N]=A[N]; (for i==1)
sufA[i]=sufA[i+1]+A[i]; (for 2<=i<=N)
Now if you switch lane at i_{th} position cost will be preB[i]+sufA[i] .
Find min( preB[i]+sufA[i]) over all i.
The minimum of all three cases will be the answer required.
Time Complexity: O(N)
SOLUTION:
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main(){
ll T;
cin>>T;
while(T--){
ll n;
cin>>n;
ll a[n];
ll b[n];
for(int i=0;i<n;i++){
cin>>a[i];
}
for(int i=0;i<n;i++){
cin>>b[i];
}
ll pre1[n],pre2[n]; // preA , preB
ll suf1[n],suf2[n]; // sufA , sufB
pre1[0]=a[0];
pre2[0]=b[0];
for(int i=1;i<n;i++){
pre1[i]=pre1[i-1]+a[i];
pre2[i]=pre2[i-1]+b[i];
}
suf1[n-1]=a[n-1];
suf2[n-1]=b[n-1];
for(int i=n-2;i>=0;i--){
suf1[i]=suf1[i+1]+a[i];
suf2[i]=suf2[i+1]+b[i];
}
ll ans=min(pre1[n-1],pre2[n-1]); // Case I
for(int i=0;i<n;i++){
ll path1=pre1[i]+suf2[i];
ll path2=pre2[i]+suf1[i];
ans=min(ans,path1); //Case II
ans=min(ans,path2); //Case III
}
cout<<ans<<"\n";
}
return 0;
}