BRKNLIFE Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4

Setter: S.Manuj Nanthan
Testers: Abhinav Sharma[inov_360 | CodeChef User Profile for Abhinav sharma | CodeChef], Nishank Suresh [iceknight1093 | CodeChef User Profile for Nishank Suresh | CodeChef]
Editorialist: Pratiyush Mishra

DIFFICULTY:

Simple

PREREQUISITES:

None

PROBLEM:

You are given two strings S and A of lengths N and M respectively.

String S contains characters from the set {?, a, b, c, d, e}.
String A contains characters from the set {a, b, c, d, e}.
Let S′ denote the string formed by replacing all the ? in S using the characters from the set {a, b, c, d, e}.
Construct S′ such that A is not a subsequence of S′.

If multiple such S′ exist, output any. If no such S′ exists, print −1.

EXPLANATION:

It is obvious that if string A is already a subsequence of string S then there is no way to construct S’ so return -1.

For when it is not a subsequence of S, we keep a track of how much of prefix substring of A has been found as subsequence as we traverse the string. When we encounter a ‘?’ we place a character in S’ which is not same as the next index of the prefix substring. Thus avoiding replacing of a same characters as in string A. Continue this till all ‘?’ have been processed which results in S’ which does not have A as a subsequence.

TIME COMPLEXITY:

O(|S|) for each test case as we traverse the string once.

SOLUTION:

Editorialist’s Solution
Tester1’s Solution
Tester2’s Solution

Editorialist solution does not seem correct to me!!!
what if S = ?ab?a and A = aa ?

It was mentioned in the problem statement , that there is no question marks in string A.

what if S = ?ab?a and A = aa

ans will be -1 since A is already a subsequence of initial string S. (?ab?a) as mentioned in the first line of editorial.

Considering editorialist’s code , at some iteration we will have i = 5 and j = 2 and it checks first for the case j = m i.e. if we have got the second string as subsequence or not so the while loop will terminate at that point only printing -1 as output.

2 Likes

I don’t know why my solution passes. Weak TCs, maybe.

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

1 Like

My Solution should give TLE, also it is a randomised solution, still it passes. Weak test cases?

//can anyone tell me whats wrong with this approach… I can relate my approach to the editorial

#include<bits/stdc++.h>
using namespace std;

int main(){
int t;
cin>>t;
while(t–){
int n,m;
cin>>n>>m;
string s,k,z="",a=“abcde”;
cin>>s>>k;
if(n<m) cout<<-1;
else{
for(int i=0,j=0;i<n and j<m;i++){
if(s[i]==k[j]){
z+=s[i];
j++;
}
}
if(k==z) cout<<-1;
else{
int j=0;
for(int i=0;i<s.size();i++){
if(s[i]==’?’){
int fk=0;
for(fk=0;fk<5;fk++) if(a[fk]==k[j]) break;
fk++;
s[i]=a[fk%5];
}
}
cout<<s;
}
}
cout<<endl;
}
return 0;
}

                                                                   // MEDIPALLY ABINAY

Edit: The tests must be fine since my solution is not wrong. Practically my solution passes every single test case, but it is difficult to prove the correctness of my solution.

I did like this:-

(My first time writing something on cc)
1)if given string t is already is a subsequence of s then answer Is obviously -1

2)now, if t is not the subsequence…what we can do to replace ‘?’ in s so that we never gets the subsequence t? …we can replace the’ ? ’ with the character having least frequency in string t … Like if t=“ab”. Smallest least frequency character from set is ‘c’ hence we will replace ‘?’ with c…

This solution passed all test cases…

Some examples:-

S=“a?b?”
t=acb

Least frequency character in t is ‘d’ we will replace ? With d. …

adbd

1 Like

Sadly would fail on

1
5 5
?bcde
abcde

1 Like

No my loop of counting min goes till end of "abde " so last min frequency is e… hence ? Will be replaced with e

1
5 5
abcd?
abcde

What about this then? Don’t say you’ll replace by ‘a’ here.

1 Like

Yes here it will fail…
I was lucky I guess or test cases were weak