EXPRIDE - Editorial



Setter: a0n0k0i0t
Tester: a0n0k0i0t
Editorialist: a0n0k0i0t


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




Prefix Sum , Suffix Sum


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)


using namespace std;
#define ll long long

int main(){
    ll T;
        ll n;
        ll a[n];
        ll b[n];
        for(int i=0;i<n;i++){
        for(int i=0;i<n;i++){
        ll pre1[n],pre2[n]; // preA , preB
        ll suf1[n],suf2[n]; // sufA , sufB
        for(int i=1;i<n;i++){
        for(int i=n-2;i>=0;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
    return 0;

I used this same optimised approach to solve this in C but have taken all the variables in int. Can that be the reason that the test cases given in problem statement passes but not during submission. Can you please share the test cases ?

Yes, that could be a possible reason. Array can be decleared as int because array elements are less than 10^9 but ans variable can reach 10^9 *10^5 which can’t be stored in int. I recommend you to use long long most of the places. Use int when you’re sure it won’t result in overflow.