BRKNLIFE Editorial

editorial
, , ,
1

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

1 Like
2

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

3

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

4

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

5

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
6

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

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

1 Like
7

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

8

//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
9

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.

10

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
11

Sadly would fail on

1
5 5
?bcde
abcde

1 Like
12

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

13

1
5 5
abcd?
abcde

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

1 Like
14

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