 # FROD - Editorial

Tester: Tejas Deore

medium

# PREREQUISITES:

Implementation , Knapsack

# PROBLEM:

Given a string showing the state of rods standing in a row. States are rod remains standing(N), rod pushed to left (L) and rod pushed to right ( R). Given a rod falling to left pushes adjacent rod on it left and so on after every second and similar is for rod pushed to right. Also given, rod/rods falling on right side balances the rod/rods falling on it from opposite direction. If you are allowed to push at most K more rods either to left or right, find the number of rods that can be made standing. You can push only those rods which are in standing state initially.

# EXPLANATION:

L signifies rod pushed to left.
R signifies rod pushed to right.
N signifies rod is not pushed.

Observation:

1. The rods between L/start and R remains standing as they experience no
force from either sides. So these rods will remain standing with no cost.
Eg. LNNNR, NNNNR
Let count of rods in between be X.
(X-1) rods standing with cost 1.

2. The rods between (start and L) and (L and L) falls to left.
Eg. * given input string is NNNNL - all the standing rods fall to left due to
force of left pushed rod.
* LNNNL.
So, to protect these standing rods form falling, we need to push the rod on
on the left of L(in case of NNNNL) ,on the left of the 2nd L (in case of LNNNL)
to the right. This right pushed will balance the Left pushed rod and hence all
other rods can saved. New states of rods given in above example will be
* NNNRL
* LNNRL

So, the number of extra rod pushed to protect in between rods
from falling in this case will be 1. Let count of rods in between be X.
(X-1) rods standing with cost 1.

3. The rods between (R and end) and R and R falls to right.
Eg. * given input string is RNNNN - all the standing rods fall to right due to
force of right pushed rod.
* RNNNR

The number of extra rod pushed in this case to protect in between rods
from falling will be 1 (explanation is similar to one in observation 2). Let
count of rods in between be X.
(X-1) rods standing with cost 1.

4. The rods between R and L. Let count of rods in between be X.

X is odd-

One rod in between will remain standing due to balance of force from both
sides. So 1 rod standing with cost 0.
(X-2) rods can be balanced with cost 2.
Eg.- RNNNNNL. Push rod at position 2 to left and rod at position 6 to right and
hence new states of rod will be RLNNNRL. 3 rods in between remains
standing(observation 1).
Note-: For X=1, that rod in between will be already standing.
For X=3, need not go with cost 2, because you will save only 1 rod(middle
one) .And that one is already saved with cost 0 (will be standing due to
balance of force).

X is even-

1 rod can be made standing by pushing one rod .
Eg. RNNNNL . Push rod 2 to right and hence new states of rod will be
RRNNNL. Now in between rod count become odd and hence one rod remain
standing due to balance of force.

(X-2) rods can be balanced with cost 2. Explanation is similar to one when X is
odd case above.
Overall, 1 rod with cost 1 and X-2 rods with cost 2
Note -: When X=2, it is not useful to go with cost 2 because rods saved will be
(X-2=0). Rather go with cost 1.

We can do is maintain one vector ‘onerod’ with the count of X-1 for all those rods
which can be saved at cost of 2. Maintain one vector ‘tworod’ with count of X-1 for
all rods which can be saved at cost of 1.
Maintain a count of cases when X is even and X=2.
Maintain the index of smallest number of X-2 value when X is even.
Note- See that vector does not get pushed backed with 0 value.
Sort both vectors in descending order and maintain prefix sum of vector.

Run a loop for ‘i’=0 to ‘i’=k. This ‘i’ value shows the number of 1 cost pushed rods
and remaining (k-i)/2 is count of 2 cost pushed rods. Run for each case and store the maximum value obtained.
Note- If the value of i gets greater than the size of(onerod) then break the loop.
If (k-i)/2 is odd means 1 more rod can be pushed. If (k-i)/2 is greater than size of
vector2, then (k-i- (sizeof(tworod)*2) ) extra count of rod can be pushed still.
We can use this extra count to save 1 rod from cases when X was even and are
not considered .

O(nlogn)

# Setter’s solution

solution
``````#include <bits/stdc++.h>
#define Rajpoot ios_base::sync_with_stdio(0);   cin.tie(0);  cout.tie(0);
#define ll long long
#define loo(i,n) for(i=0;i<n;i++)
#define go(i,sp)  for(auto i=sp.begin();i!=sp.end();i++)
#define pb push_back
#define lb lower_bound
#define mo 1000000007
#define pi 3.14159265358979323846264338327950288419716939937510582
#define exp 2.71828182845904523536028747135266249775724709369995957
#define endl "\n"
using namespace std;

int main()
{
Rajpoot
//    freopen("input.txt","r",stdin);
// freopen("output.txt","w",stdout);

int t; cin>>t;

// int t=1;
while(t--)
{
ll n; cin>>n;
ll k; cin>>k;
string s; cin>>s;
ll sum=0,i;
vector<ll> onerod,tworod;
ll c=0;
ll even_count=0;  // even_count stores the count of when X=2, where x is count of rods in b/w R and L
char ch='N';  ll even2=0;
ll evenval=1000000;
vector<ll> even;    // even vector store all the X-2 count when X is even and X>2
// check the condition of NNNN,LNNR, NNNL,RNNN, RNNNL
// and maintain the count when rods saved at cost 0, at cost 1 and at cost 2.
// sum stores the count of rods which will remain standing even if no extra rod is pushed.
for(i=0;i<n;i++)
{
if(s[i]=='N') c++;

else if(s[i]=='R')
{
if(ch=='L')
sum+=c;
else if(ch=='R')
{
if(c-1>0) onerod.pb(c-1);
}
else
sum+=c;

c=0; ch='R';
}

else if(s[i]='L')
{
if(ch=='R')
{
if(c%2==1)
{
sum+=1; c--;
}
else
{
if(c-2==0)
{
even2++; even_count=-100;
}
if(c-2>0) even.pb(c-2);
}
if(c-2>0) tworod.pb(c-2);

}
else if(ch=='L')
{
if(c-1>0) onerod.pb(c-1);
}
else
{
if(c-1>0) onerod.pb(c-1);
}

c=0; ch='L';
}
}
if(c!=0)
{
if(ch=='R')
{
if(c-1>0) onerod.pb(c-1);
}
else sum+=c;
}
// finding the smallest value of X-2 when X is even
for(i=0;i<even.size();i++)
{
if(even[i]<evenval) evenval=even[i];
}

sort(onerod.begin(),onerod.end(),greater<ll>());
sort(tworod.begin(),tworod.end(),greater<ll>());

for(i=1;i<onerod.size();i++)   // creating prefix sum of rod count saved at cost 1
onerod[i]+=onerod[i-1];

ll leastind=-1;   // this store the highest index when x is even that is least value of x-2

for(i=0;i<tworod.size();i++)   // creating prefix sum of rod count saved at cost 2
{
if(tworod[i]==evenval)leastind=i;
if(i>0)
tworod[i]+=tworod[i-1]; //cout<<tworod[i]<<" ";
}
if(even_count==-100) leastind=1000000; // if X==2 exists

ll maxi=sum; // if no extra rods are pushed  these rods will definitely remain standing

for(i=0;i<=k;i++) // i denotes no. of 1 rods condition to be checked;
{
if(i>onerod.size()) break;

if(i!=0)
answer=onerod[i-1];  // no of rods saved(each rod chunk saved at cost 1) by puhing i rods.
ll d=(k-i)/2;        // no. Of two rods that can be taken
ll o=0;
if((k-i)%2==1) o=1; // one more rod remaining
if(d>tworod.size()) // if number of extra rods that can be pushed is greater than available
{
o+=(d-tworod.size())*2; d=tworod.size();

}
if(d!=0)
{
answer+=tworod[d-1];  // no of rods saved(each rod chunk saved at cost 2) by puhing d pair rods.
}

if(o==1 )
{
}
else
{
}
Huge thanks to Arun Das for helping us on this contest (as it was our first contest ) and especially for his help on this question.
Feel free to Share your approach . Suggestions are welcomed. 