CHFTNS -Editorial

editorial
,
1

PROBLEM LINK:

MasterChef
Chef Dynasty

Author and Editorialist Tejas Dhanait
Tester: Nandini Kapoor

DIFFICULTY:

SIMPLE

PREREQUISITES:

Brute Force , Implementation

PROBLEM:

  • A string Consisting of W and L is given, in which certain positions which are either divisible by K1 or K2 are locked. We can interchange the character of unlocked positions . We have to change the string in such a way that while traversing through the string the number of W appearing should always be strictly greater than the number of L appearing.
  • If there are multiple strings present then we have to print lexiographically smallest one.

EXPLANATION:

  • We will maintain Two Counters For the count of W and L. Also We will maintain a vector ( we can even use stack, queue ) , in which we will push positions of all those characters which are ā€˜Lā€™ and for whose positions are neither divisible by K1 nor by K2.

  • We are maintaining the vector as we want the modified string to be lexicographically smallest, and hence as L<W therefore we would try to change L to W (if required ) , as late as possible in the string

  • So now while traversing through the string if anywhere the count of L becomes greater or equal to W then

  1. if vector is empty then, it means we can not modify the string to a winning combination. Hence Print -1.
  2. If vector is not empty then , we will change the last position present in the vector form L to W. Update the L and W counters accordingly. And pop back the position from the vector once that position has been modified from L to W.
  • Finally if the winning combination is possible for the given string then print the number of characters changed in the string followed by the modified string in the next line.

Time Complexity :

 O(N)

SOLUTIONS:

Setter's Solution (C++) 
 /* Author : Tejas Dhanait ( tejas_1309) */
#include<bits/stdc++.h>
using namespace std;
int main()
{
int test;
cin>>test;

while(test--)
{
    
    string s;
    cin>>s;
    int k1,k2;
    cin>>k1>>k2;

    int win=0,lose=0;
    int ans=0,flag=0;
    vector<int> pos;

     for(int i=0;i<s.length();i++)
        {
            if(s[i]=='L')
             {
                  lose++;
                  if((i+1)%k1!=0 && (i+1)%k2!=0)
                     {
                       pos.push_back(i);
                     }
             }
            else
             {
                   win++;
             }
    
    
           if(lose>=win)
            {
                 if(pos.size()==0)
                   {
                     cout<<-1<<endl;
                     flag=1;
                     break;
                   }
                  else
                   {
                     int k=pos.back();
                     s[k]='W'; 
                     lose--;
                     win++;
                     pos.pop_back();
                     ans++;
                    }
             }
    
        }
    if(flag==0)
    {
    cout<<ans<<endl;
    cout<<s<<endl;
    }
  
   }

  }
Tester's Solution (Python) 
t = int(input())
for _ in range(0,t):    
s = input().  
str = list(s)
k1,k2 = map(int,input().split())
w=0; l=0; flag=0; ans=0;
lis = []
for i in range(0,len(s)):
    if str[i] == 'W':
        w+=1
    else:
        l+=1
        if (i+1)%k1!=0 and (i+1)%k2!=0:
            lis.append(i)
    if l>=w:
        if len(lis) == 0:
            flag=1
            break
        else:
            str[lis[len(lis)-1]]='W'
            lis.pop()
            w+=1
            l-=1
            ans+=1
if flag: print(-1)
else:
    print(ans)
    for i in str:
        print(i,end="")
    print()
5 Likes