Hi, I have tried similar approach.
Could someone please point out why it is WA?
https://www.codechef.com/viewsolution/33505917
Thanks.
check this test case
4
acbc
abac
I did similar way but got WA in subtask 2.
Cant figure what went wrong.
heres the code link:
hey i checked your code for this
1
5
defgb
bbebb
this gives
2
4 0 1 3 4
1 2
but this output is wrong because you should convert bigger letters first if you convert 0 1 3 4 they will all be ‘b’ and now there will no ‘e’ be availaible for conversion.
the correct ouput should be
2
2 1 2
4 0 1 3 4
please Reply @tanha_barati
Can someone tell me what is the corner case I am missing such that my code is not running in subtask 2. Although I have checked most of the cases.
Here is the link
CodeChef: Practical coding for everyone
Thanks
Looking at the tester’s time complexity, isn’t it O(A*N) instead of O(A+N)?
ya got that i got AC now! but there is an accepted solution of someone where the code fails and hes getting AC
your code gives -1 on this input
1
4
acbc
abac
whereas the correct output would be
2
2 1 2
2 0 2
1 Like
So I take string as individual character and store it in a string( ar for first string and arr for second string). Then I start from the first index of second string(i loop) and find all the character equal to the character of first index using a j loop.
If(arr[i]==arr[j]) then i check if(ar[j]!=arr[j]) I add that index to matrix and also i maintain a flag array to not traverse with j loop again if that character is already traversed.
I also check if(ar[i]!=arr[i]) i add the value into matrix as j loop starts from i+1. I initially checked for ar[i]<arr[i] for each character, if yes flagg=1 and break. Also if the character is not present break. At the end of each traversal I store the size of each row at the end of the matrix. If the size is <=1 i skip that index and count the rest(mat[i][1002]>1) and print that value as m(here i used k to count them). Then from z to a if the length of each row is greater than 1, I print those value.
I skipped those index with substring length less than equal to one because,
abb
aba
for this case it store it as,
2 0 2
1 1
where i dont want to print 1 1.
Also i finally check whether both the string are equal.
If flagg==0 and k==n(all the char are equal)
print matrix
else
-1
I think the only mistake that you are making is traverse the list while making the changes from the start. There might be cases where the index of characters in string A that you are might wanna use to make changes later have already been changed by that step. For example:
1
3
bca
aba
Here your code’s output is:
2
2 0 2
2 0 1
Now, if you notice that according to your code’s output, you first change the ‘b’ in string A to ‘a’ and then try to use that ‘b’ again to change the ‘c’ to ‘b’ in the second step which is not possible.
Hence, the only correction that you have to do is to traverse the list in reverse order.
I changed your code slightly and just traversed the list in the reverse direction and now it gets AC on both test cases.
-
CodeChef: Practical coding for everyone
Hope that helps!)
1 Like
CodeChef: Practical coding for everyone i got 30 marks, can anyone suggest any test cases where my code get wrong answer
the subset chosen is of a single element {2} ie. character b
Got 30/100.
Can someone help me with the case which fails ?
https://www.codechef.com/viewsolution/33525069
I dont know why i am getting this (SIGSEGV) error. can anyone please help me to understand what is the exact problem in my code.
#include<bits/stdc++.h>
using namespace std;
#define debug(x) cout << ‘>’ << #x << ‘:’ << x << endl;
#define f0(i,a,b) for(ll i=a;i<b;i++)
#define f1(i,a,b) for(unsigned long long i=a;i<=b;i++)
#define fr(i,a,b) for(ll i=b-1;i>=a;i–)
#define ll long long
const int MOD = 998244353;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int t;
//t=1;
cin >> t;
while(t–){
int n;
cin >> n;
string a, b;
cin >> a >> b;
bool flag = true;
// first case if a[i] < b[i] than we can not convert a into b.
f0(i, 0, n){
if(a[i] < b[i]){
flag= false;
break;
}
}
set<char> char_a;
f0(i, 0 ,n){
char_a.insert(a[i]);
}
// case 2 here we need to check whether all elements of b are present in a or not. if not than result is -1;
f0(i, 0, n){
// cout << ((char_a.find(b[i]) == char_a.end())) << endl;
if(char_a.find(b[i]) == char_a.end()){
flag = false;
}
}
/* for(auto ss : char_a){
//cout << ss << endl;
}*/
if(!flag){
cout << "-1\n";
continue;
}
map<char, vector<int> > mymap;
f0(i, 0, n){
if(a[i] != b[i]){
mymap[b[i]].push_back(i);
}
}
for(auto e : mymap){
char ch = e.first;
f0(i, 0, n){
if(a[i] == ch){
mymap[ch].push_back(i);
break;
}
}
}
/* for(auto e : mymap){
cout << e.first << " ";
for(auto t : (e.second)){
cout << t << " ";
}
cout << endl;
} */
//debug(t)
auto tt = mymap.end();
tt--;
cout << mymap.size() << endl;
for(;tt != mymap.begin();--tt)
{
cout << (tt->second).size() << " ";
cout << (tt->second).back() << " ";
vector<int> vec = tt->second;
for(int i=0;i<(vec.size()-1);i++){
cout << vec[i] << " ";
}
cout << endl;
}
if(tt == mymap.begin()){
cout << (tt->second).size() << " ";
cout << (tt->second).back() << " ";
vector<int> vec = tt->second;
for(int i=0;i<(vec.size()-1);i++){
cout << vec[i] << " ";
}
cout << endl;
}
}
return 0;
}
Ok I find my mistake. I have not add one important edge case 
if (a==b){
cout << “0\n”;
continue;
}
Yes. That’s a logical error. I think either the tcs are weak or they checked for the optimal steps required and not the processional changes. Anyway thanks for point that out, It will require one more check to ensure if after changes we come in a deadlock or not. I’ll update my solution accordingly 
1
3
bca
aba
check this case.