Where did this code fail
#include <bits/stdc++.h>
#pragma GCC optimize(“Ofast”)
#pragma GCC target(“avx,avx2,fma”)
#define ll long long int
#define pii pair<int,int>
#define vi vector
#define umap unordered_map<ll,ll>
#define uset unordered_set
using namespace std;
int main()
{
int t; cin >> t;
while(t--)
{
int n, count = 0, flag = 0; cin >> n;
vector<char> a(n), b(n);
for(auto &x : a) cin >> x;
for(auto &x : b) cin >> x;
if(a==b)
{
cout<<0<<endl;
cout<<n<<" ";
for(int i=0;i<n;i++)
{
cout<<i<<" ";
}
continue;
}
map<char, set<int> > hmap;
map<char,int> amap, bmap;
for(auto x : a) amap[x]++;
for(auto x : b) bmap[x]++;
for(auto x : b)
{
if(amap[x] == 0 && bmap[x] != 0)
{
flag = 1;
break;
}
}
if(flag)
{
cout << -1 << endl;
}
else
{
for(int i=n-1;i>0;i--)
{
if(a[i]!=b[i])
{
hmap[b[i]].insert(i);
for(int j=0;j<i;j++)
{
if(a[j]==b[i])
{
hmap[b[i]].insert(j);
}
}
for(int j=i+1;j<n;j++)
{
if(a[j]==b[i])
{
hmap[b[i]].insert(j);
}
}
a[i]=b[i];
}
else
{
continue;
}
}
cout<<hmap.size()<<endl;
for(auto x : hmap)
{
cout << x.second.size() << " ";
for(auto y : x.second) cout << y << " ";
cout << endl;
}
}
}
return 0;
}
Ohh…didn’t pay much attention …thought there could be multiple answers …thanks!..WOw
I got partial points, please tell me what’s wrong with this with this code.(approach is similar to editorialist’s solution). CodeChef: Practical coding for everyone
THANKS IN ADVANCE.
If I print the answer from z to a it gives AC , but from a to z it gives WA
But mathematically it can be proven that each set has unique elements.
Here is link to my submission
https://www.codechef.com/viewsolution/33503396
If you change the loop from 25 to 0 which is written as (0 to 25) on line number 91 the solution get accepted
Can anyone help to understand why it gives WA for printing solution in ascending order
Can someone help me to figure out why I am getting WA in 1st subtask while getting AC in 2nd? I have checked all test cases, but can’t find the error? plz help.
https://www.codechef.com/viewsolution/33486726
There is no ONE FIXED SOLUTION, the main thing is not the S subset, but the minimum number of steps required
We can prove that it is optimal to apply operations in decreasing order of chchch as it doesn’t affect candidate positions for **special positions** for subsequent positions.
How to prove this part?
What I have thought yet is after checking both of the conditions of “-1”.
If it is possible to make A to B then,
For all characters from z to a that are present in B, at an instance let the character be ch in B. We are updating all the characters in A that should be equal to ch, but are greater than ch. So, it will never affect our special positions for subsequent positions.
Lets assume that it does affect the subsequent positions then, it means that the character ch has already been replaced in A by any other smaller character. But it is not possible since we are at an instance updating all the characters in A that are greater ch, but should be equal to ch.
Eg.
A = a, c, d, e
B = a, a, c, d
In the string A characters c and d are special positions because they help in updating the other positions and gets updated to some other character as well.
Suppose our ch is d in B, so, if A to B conversion is possible then, d will always be present in A since we have only updated those characters in A which were greater than d. So, if d is not present in A, it means that we have already updated “d” to “c” or any other smaller character, which is not possible since we are converting from z to a, so we will convert from d first and then, c.
Therefore, conversion from z to a is optimal and doesn’t affect special positions.
i got wa , i can,t figure it out… please help me to find
https://www.codechef.com/viewsolution/33518415
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:
https://www.codechef.com/viewsolution/33520197
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.
1 Like