# RUMBLING - Editorial

Tester: Anshu Garg

EASY

# PREREQUISITES:

Prefix/Suffix Sums

# PROBLEM:

Given N titans in a line, each facing either North, South, East or West. It costs X and Y energy to rotate any titan 90\degree clockwise and anticlockwise, respectively. Determine the minimum cost to rotate all titans such that, the first i titans face East and the remaining titans face West, for some optimal i.

# EXPLANATION:

First, calculate the minimum cost to make titan i face East/West, for each i.

How?

A bit of case work is required here. For each of the 4 directions the titan may initially face, determine the minimum cost to make him face East/West.

The table of values is given below (deductions are trivial).

Current direction Min cost to face East Min cost to face West
East 0 \min(2*X,2*Y)
West \min(2*X,2*Y) 0
North \min(X,3*Y) \min(3*X,Y)
South \min(3*X,Y) \min(X,3*Y)

Next, for each i, determine the minimum cost to make the first i titans face East. Also determine the minimum cost to make the last i titans face West.

How?

Let minE_i represent the minimum cost to make titan i face East. Similarly, let minW_i represent the minimum cost to make titan i face West.

Then, calculate the prefix/suffix sums of array minE/minW.

Finally, for each valid i, the minimum cost to place Eren between titans i and i+1 is equal to: minimum cost to make first i titans face East + minimum cost to make last N-i titans face West.

The required answer is then the least cost over all i (don’t forget to calculate the cost when Eren is placed at the East/West end of the line!)

# TIME COMPLEXITY:

Determining the minimum cost to make each titan face East/West takes O(N). Calculating step 2 using prefix/suffix sums takes O(N). Calculating the answer requires iterating once over the N terms, so O(N).

The final complexity is therefore:

O(N+N+N) \approx O(N)

# SOLUTIONS:

Editorialist’s solution can be found here

Experimental: For evaluation purposes, please rate the editorial (1 being poor and 5 excellent)

• 1
• 2
• 3
• 4
• 5

0 voters

Can anybody help me find the error.
This is my code

#include<bits/stdc++.h>
#define lld long long int
#define all(x) x.begin(),x.end()
#define vlld vector
using namespace std;
void solve(){
lld n,x,y;
string s;
cin>>n;
cin>>s;
cin>>x>>y;
vlld e_arr,w_arr;
for(lld i=0;i<n;i++){
if(s[i]==‘W’){ e_arr.push_back(min(2x,2y)); }
else if(s[i]==‘N’){ e_arr.push_back(min(x,3y)); }
else if(s[i]==‘S’){ e_arr.push_back(min(3
x,y)); }
else{ e_arr.push_back(0); }
}

``````for(lld i=0;i<n;i++){
if(s[i]=='E'){ w_arr.push_back(min(2*x,2*y)); }
else if(s[i]=='N'){  w_arr.push_back(min(3*x,y)); }
else if(s[i]=='S'){ w_arr.push_back(min(x,3*y)); }
else{ w_arr.push_back(0); }
}
lld res;
lld es=0,ws=0,q;
ws=accumulate(all(w_arr),0);
res=ws;
for(lld i=0;i<n;i++){
es=es+e_arr[i];
ws=ws-w_arr[i];
lld p=es+ws;
if(p<res){ res=p; }
}
cout<<res<<"\n";
``````

}
int main(){

``````lld t;
cin>>t;
while(t--){
solve();
}
return 0;
``````

}

Edit:

In the meantime, ensure you’re getting the correct answer for Help needed for a problem - #2 by ssjgz.

https://www.codechef.com/viewsolution/50929640

1 Like

Thanks! See my Edit

output is some garbage value

Yes - can you see why? Hint: it’s your call to `std::accumulate`.

Thanks bro!!

1 Like

But, Is there there something wrong with using std::accumulate to calculate the sum of entire vector??

It’s fine, but you have to be careful with the types: it deduces the final type of the computation by template argument deduction on the initial value (`0`) which is an `int`, hence the wrong result.

The following should work:

``````ws=accumulate(all(w_arr),static_cast<lld>(0));
``````

Thanks bro

1 Like

Link to my code: Solution: 50930419 | CodeChef

What’s wrong with my code?

Can anyone please mention to me the faulty testcase!?

It would be of great help to me!