RUMBLING - Editorial

PROBLEM LINK:

Contest - Division 3
Contest - Division 2
Contest - Division 1

Setter: Shivam Yadav
Tester: Anshu Garg

DIFFICULTY:

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;

}

Please either format your code or (better!) link to your submission - the forum software has mangled it and it won’t compile! :slight_smile:

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
here is the link

1 Like

Thanks! See my Edit :slight_smile:

output is some garbage value :cold_face:

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?? :thinking:

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 :blush:

1 Like

Please help me figure it out! @ssjgz @shivy08 @anshugarg12 @infinitepro

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!

Urgh, my bad!

Really very kind of you @ssjgz , You save me everytime :slight_smile:

2 Likes