DIFSTR - Editorial

pawan_9617 · August 24, 2021, 9:44am

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;

}

iquoteonyou · August 24, 2021, 11:51am

Somebody please check my solution .
Link- CodeChef: Practical coding for everyone

iceknight1093 · August 24, 2021, 12:17pm

Couple of problems with that:

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
Even for small lengths your logic isn’t correct. Try input

1
1
1

where your output is 1

whocares05 · August 24, 2021, 1:52pm

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

iceknight1093 · August 24, 2021, 2:24pm

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.

mayurmg_2000 · August 24, 2021, 3:10pm

#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.

whocares05 · August 24, 2021, 3:49pm

Thank You very much for this.

iceknight1093 · August 24, 2021, 4:40pm

mayurmg_2000 · August 24, 2021, 4:47pm

Thank you so much

sahil_khar26 · August 26, 2021, 2:56am

nyc idea

sanskar_native · August 26, 2021, 9:16am

thanks : )

rahul8954 · August 27, 2021, 6:24am

–>very easy different approach
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;
}

yashwin_joshi · August 28, 2021, 3:11am

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);

iceknight1093 · August 28, 2021, 5:18am

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).

yashwin_joshi · August 28, 2021, 5:58am

thank you so much!

i got it right with scanner class👍

ayush1_20 · August 31, 2021, 6:01pm

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

int main( ) {
ios_base::sync_with_stdio(false);
cin.tie(NULL);

   int t,n,i,j;
  cin>>t;
    while(t--) {
        cin>>n;
       string a,b;
         
    for(i=0;i<n;i++) {
        
     for(j=0;j<n;j++)   {
       cin>>b[j]; }
       
        if(b[i]=='0') { 
          a[i]='1';}
          
        else {a[i]='0'; }
   
    cout<<a[i];}

     cout<<endl;  }
      
       return 0; }

// Why I am getting a SIGABRT (here) ?

dhruvtrehan · December 6, 2021, 7:29pm

My logic is:

Count the frequency of 1 and 0 respectively.

Check for these conditions:

Count of 1 == 0
Count of 0 == 0
Count of 1 < Count of 0
Count of 0 < Count of 1
Count of 1 == Count of 0

Respectively print ‘0’ and ‘1’ as required.

Here is my code:

#include<bits/stdc++.h>
using namespace std;
int main()
{
int tc;
cin>>tc;
while(tc–)
{
int n;
cin>>n;
vector res;
string d;
int count_zero = 0;
int count_one = 0;
int max_count_one = INT_MIN;
int max_count_zero = INT_MIN;
for(int i = 0 ; i < n ; i++)
{
cin>>d;
res.push_back(d);
}
for(auto i: res)
{
string d = i;
for(int j = 0 ; j < d.length() ; j++)
{
if(d[j] == 1)
{
count_one++;
}
else{
count_zero++;
}
}
max_count_one = max(max_count_one, count_one);
max_count_zero = max(max_count_zero, count_zero);
count_one = 0;
count_zero = 0;
}
if(max_count_zero == 0 or max_count_one == d.length())
{
for(int i = 0 ; i < max_count_one ; i++)
{
cout<<“0”;
}
cout<<endl;
}
else if(max_count_one == 0 or max_count_zero == d.length())
{
for(int i = 0 ; i < max_count_zero ; i++)
{
cout<<“1”;
}
cout<<endl;
}
else if(max_count_zero < max_count_one)
{
for(int i = 0 ; i < (max_count_one + max_count_zero) ; i++)
{
cout<<“1”;
}
cout<<endl;
}
else if(max_count_one < max_count_zero){
for(int i = 0 ; i < (max_count_zero + max_count_one) ; i++)
{
cout<<“0”;
}
cout<<endl;
}
else if(max_count_one == max_count_zero)
{
for(int i = 0 ; i < (max_count_zero + max_count_one) ; i++)
{
cout<<“1”;
}
cout<<endl;
}
else{

}
}

}

Can you please tell the error? Why, I can’t submit this code?

coderama · May 18, 2022, 12:44pm

Why am I getting WA? I have used the set approach. Sample and manually made testcases are giving correct answer on IDE.

import java.lang.reflect.Array;
import java.util.*;

public class CP {

    public static void main(String[] args) {
      try {
          Scanner s = new Scanner(System.in);
          StringBuffer sb = new StringBuffer();


          int t = s.nextInt();
          while(t-- > 0){
              int n = s.nextInt();
              String st[] = new String[n];
              for(int i = 0; i < n; i++){
                  st[i] = s.next();
              }
              Set<Integer> hs = new HashSet<>();
              for(int i = 0; i < n; i++){
                  hs.add(Integer.parseInt(st[i] , 2));
              }
              int  j = 0;
              while(hs.contains(j)){
                  j++;
              }
              String ans = Integer.toBinaryString(j);
              while (ans.length() != n){
                  ans = "0" +ans;
              }
              sb.append(ans+"\n");





          }







          System.out.println(sb);
      }catch (Exception e){
          System.out.println(e);
      }
    }
}

neel_04 · November 27, 2022, 11:49am

can anyone say why this didn’t work??

int n; cin>>n;

    string s, x;

    // x+='0';

    // for(int i=1; i<n-1; i++){

    //     x+='0';

    // }

    // x+='1';

    // int flag = 0;

    // int i=0;

    // while(n--){

    //     cin>>s;

    //     if(s==x){

    //         flag ==1;

    //         if(flag==1){

    //             if(x[i]=='0') x[i]='1';

    //             else x[i]='0';

    //             i++;

    //             flag = 0;    

    //         }

    //     }

    //     // else continue;

    // }

    // cout<<x<<endl;

rising_stark · December 18, 2024, 8:49pm

I did it using a trie. If both bits are present, take any one. Then whichever bit is not present, take that one.