DIFSTR - Editorial

Kindly read once again, It says: " You need to find a binary string of length N which is different from all of the given strings."

1 Like

Looks like the tests didn’t manage to catch this wrong solution, not much else I can say (or do) about it now.

1 Like

is ‘000’ a valid solution to the first testcase?

Yes it is.

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mod 1000000007
#define inf (1LL << 60)
#define all(x) (x).begin(), (x).end()
#define prDouble(x) cout << fixed << setprecision(10) << x
#define triplet pair<ll, pair<ll, ll>>
#define goog(tno) cout << “Case #” << tno << ": "
#define fast_io
ios_base::sync_with_stdio(false);
cin.tie(NULL)
#define w(t)
int t;
cin >> t;
while (t–)
using namespace std;

void gshikhar84()
{
fast_io;
}

int main()
{
gshikhar84();
w(t)
{
int n;
cin >> n;
string arr[n];
set st;
string s;
string curr, finals;
for (int i = 0; i < n; i++)
{
cin >> s;
arr[i] = s;
st.insert(s);
}
bool flag = true;
for (int i = 0; i < n; i++)
{
curr = arr[i];
do
{
s = curr;
if (st.find(s) == st.end())
{
finals = s;
flag = false;
break;
}
} while (next_permutation(curr.begin(), curr.end()));
break;
}
if (flag)
{
for (int i = 0; i < n; i++)
{
curr = arr[i];
do
{
s = curr;
if (st.find(s) == st.end())
{
finals = s;
flag = false;
break;
}
} while (prev_permutation(curr.begin(), curr.end()));
break;
}
}
cout << finals << endl;
}
return 0;
}

Can Someone Please check this

This solution seems to assume that it’s possible to get an answer which is a permutation of one of the input strings, but that’s not true.

1
2
10
01

and your code prints nothing.

1 Like

void solve() {

cin >> n;
set<int> st;

// since 100 is less than 2^8;
// we can store first 8 bits of all the strings
// and then run a loop from 0 to 101, the first number which is not present will be our answer, then we will fill rest of the bits with 0(or 1, doesn't matter).

for(int i=0; i<n; i++) {
    cin >> str;
    int ans = 0;
    for(int i=0; i<min(n,8); i++) {
        if(str[i]-'0') ans += (1<<i);
    }
    st.I(ans);
}
int element = 0;
while(st.find(element)!=st.end()) {
    element++;
}
for(int i=0; i<min(n,8); i++) {
    if((element>>i)&1) cout << 1;
    else cout << 0;
}
for(int i=8; i<n; i++) {
    cout << 0;
}
cout << endl;

}

Somebody please check my solution .
Link- Solution: 50150396 | CodeChef

Couple of problems with that:

  1. You’re using stoi to convert the input strings to an integer, but a 100-bit binary number definitely won’t fit even in long long
  2. Even for small lengths your logic isn’t correct. Try input
1
1
1

where your output is 1

Hey @iceknight1093 , I Know this may be a silly question, but how you mange to debug solutions so fast, I mean Yeah obviously you are a 6* Coder and have a lot of experience but is there some tips for us to debug solutions ao fast as you used to do.

Ps: Consider me as a beginner and also very new to community. <3

It’s a combination of several things:

  • In this specific case I’ve solved these problems myself and seen discussions between the tester and setter about what could possibly be tricky cases/common wrong solutions, so if I see one of those I’ll know quickly
  • For C++ specifically, compiling with debug flags really helps (see this blog). Several solutions I’ve debugged had their issues revealed immediately when I just compiled them locally without even having to run the program (for example, I get a warning if a variable is used without its value being set)
  • Test on more than just the sample cases. The samples are often there just to make sure you haven’t completely misunderstood the problem, they don’t necessarily have to take all edge cases into account. If you aren’t sure where your program is going wrong, try lots of small cases. My comment immediately above shows that testing on even the most trivial case (n = 1) can bring out errors in your code.
  • Finally, you can always stress-test your solution. Either write a bruteforce or (if you have access to it) take a correct code from an accepted submission, then take your wrong code, generate lots of test cases, and compare the output. This will give you a testcase where you are failing, and you can then use that to debug your program.
  • Once you know a testcase where you’re wrong, general debugging advice still holds. Use lots of print statements and asserts to verify that your variables are actually holding the values you think they are, etc.
3 Likes

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

int main() {
// your code goes here
ll t;
cin>>t;
while(t–)
{
int n ;
cin>>n;

string str;
string temp="";
for(int i=0;i<n;i++)
{
cin>>str;
if(str[0]==‘1’)
temp+=‘0’;
else temp+=‘1’;
}

cout<<temp<<endl;
}

return 0;
}

Can anyone help me and guide what is wrong in this code. I wanted to change the first character from each string.

Thank You very much for this. :relieved:

1 Like
1
2
01
10

Thank you so much

nyc idea

1 Like

thanks : )

–>very easy different approach :grinning:
include <bits/stdc++.h>
#define ll long long
using namespace std;

string dtb(int n,int sz){
string ans="";
while(n){
ans+=to_string(n%2);
n=n/2;
}
int val=sz-ans.size();
string zero=“0”;
while(val–){
ans=zero+ans;
}
return ans;
}
string solve(vectora){
int num=a[0].size();
for(int i=1;i<pow(2,num);i++){
string t=dtb(i,num);
if(find(a.begin(),a.end(),t)==a.end())return t;
}
return “”;
}

int main(){
int t;
cin>>t;
while(t–){
int n;
cin>>n;
vectora;
for(int i=0;i<n;i++){
string s;
cin>>s;
a.push_back(s);
}
cout<<solve(a)<<endl;

}

return 0;
}

i have just changed the diagonal elements so the output string must be different from the given strings …please let me know where my code or the logic went wrong .
i have written my code in java.
Reader s=new Reader();
int t=s.nextInt();
while(t–>0) {
int n=s.nextInt();
String a[]=new String[n];
for(int i=0;i<n;i++) {
a[i]=s.readLine();
}
String ans="";
for(int i=0;i<n;i++) {
if(a[i].charAt(i)==‘0’)
ans+=“1”;
else
ans+=“0”;
}
System.out.println(ans);

I had to look at your actual submission to find the error. Please always link your code instead of pasting it here!

It seems like the reader class you’re using is an issue. I simply switched to taking input with Scanner and it passed (submission).

Unfortunately I know basically nothing about Java so I don’t really know why your Reader was wrong, you’ll have to figure that out yourself (or find someone who does know).

1 Like