FROD - Editorial

Practice
Contest

Author & Editorialist: Adarsh Singh
Tester: Tejas Deore

DIFFICULTY:

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 .

TIME COMPLEXITY:

O(nlogn)

SOLUTIONS:

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;
       {
           ll answer=0;
           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 )  
        {
            if(even2>0 || leastind>d-1) answer++;
        }
        else 
        {
            answer+=min(even2,o);
        }
            maxi=max(maxi,answer+sum);
       }
       cout<<maxi<<endl;
    }    

	return 0;
}

Huge thanks to Arun Das for helping us on this contest (as it was our first contest :grinning:) and especially for his help on this question.
Feel free to Share your approach :stuck_out_tongue: . Suggestions are welcomed. :slight_smile:

6 Likes