DIFSTR - Editorial

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3

Author: Deepak Barnwal
Tester: Shubham Anand Jain
Editorialist: Nishank Suresh

DIFFICULTY:

Easy

PREREQUISITES:

None

PROBLEM:

Given N binary strings of length N each, find a binary string of length N which is different from all of them.

QUICK EXPLANATION:

If the input strings are S_1, S_2, \dots, S_N, one possible solution is to set ans[i] to be the opposite of S_i[i].

EXPLANATION:

The quick explanation says it all!

There are 2^N binary strings of length N, and N < 2^N for every N \geq 1 so an answer always exists.
Since the length of the strings equals their number, we can use the i-th position of the answer to make it different from the i-th string. That leads to the following construction:
Create a binary string of length N whose i-th character is the opposite of the i-th character of the i-th input string.
This ensures that the created strings differs from each input string at at least one position, which is exactly what we want.

ALTERNATE SOLUTIONS:

The above solution is not the only one - several others exist as well. A couple are outlined below.

Solution 1

Since N strings are given, one can try N+1 different strings and check whether each of them is among the given strings.
The pigeonhole principle tells us that at least one of these N+1 strings will be an answer.
To make implementation easy, these N+1 strings can be the N-bit binary representations of 0, 1, 2, \dots, N.
N is small enough that this \mathcal{O}(N^3) solution works comfortably.

Solution 2

N is much less than 2^N, so the space of possible answers is extremely large. So large, in fact, that one can generate a random binary string and check whether it is in the given set - and if it is, repeat till one which isn’t is generated.
The probability that a random binary string is not among the given N is 1 - \frac{N}{2^N}. The expected number of trials till an answer is found is thus \frac{2^N}{2^N - N}, which is \leq 2 for all N \geq 1. For N\geq 10 it’s basically 1.
Each trial works in \mathcal{O}(N^2) (comparing the generated string against all existing strings) so this runs in expected \mathcal{O}(N^2)

If you have a different solution, feel free to share it in the comments below!

TIME COMPLEXITY:

\mathcal{O}(N) or \mathcal{O}(N^2) or \mathcal{O}(N^3) per testcase, depending on implementation.

SOLUTIONS:

Setter's Solution
#include "bits/stdc++.h"
using namespace std;
#define  FastIO ios_base::sync_with_stdio(false); cin.tie(NULL);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define int long long
void solve(int TC){
    int n,i;
    cin>>n;
    string s[n];
    for(i=0; i<n; i++){
        cin>>s[i];
    }
    int a;
    for(i=0; i<n; i++){
        a = (s[i][i] - '0');
        cout<<!a;
    }
    cout<<'\n';
}
signed main(){
    
    FastIO;
    int Test = 1;
    cin>>Test;
    for(int i=1; i<=Test; i++){
        solve(i);
    }
    return 0;
}
Tester's Solution
//By TheOneYouWant
#include <bits/stdc++.h>
using namespace std;
#define fastio ios_base::sync_with_stdio(0);cin.tie(0)

int main(){
	fastio;

	int tests;
	cin >> tests;

	while(tests--){

		int n;
		cin >> n;
		string s[n];
		string ans;
		for(int i = 0; i < n; i++){
			cin >> s[i];
			if(s[i][i]=='0') ans += '1';
			else if(s[i][i]=='1') ans += '0';
		}
		cout << ans << endl;
	}
	
	

	return 0;
}
Editorialist's Solution
for _ in range(int(input())):
    n = int(input())
    have = set()
    for i in range(n):
        s = input()
        have.add(s)
    for i in range(n+1):
        cur = ''
        for bit in range(n):
            cur += '1' if i&(1<<bit) else '0'
        if cur in have:
            continue
        print(cur)
        break
6 Likes

I think, there is something wrong with this question’s test cases, I mean look at below code (accepted during contest), The task is to find different string from given strings.

#include <bits/stdc++.h>

using namespace std;
#define ll long long

int main()
{
	ll test, n;
	std::cin >> test;

	while (test--)
	{
		std::cin >> n;
		std::string text[n], res;

		for (ll i = 0; i < n; i++)
		{
			std::cin >> text[i];
			res.push_back('0');
		}

		ll j = 0;
		for (ll i = 0; i < n; i++)
		{
			if (text[i] == res)
			{
				if (res[j] == '0')
					res[j] = '1';
				else
					res[j] = '0';

				j++;
			}
		}
		std::cout << res << "\n";
	}

	return 0;
}

But entering below Inputs, Output string is similar to given strings:
Input:

1
4
1101
1000
1001
0000

Output:

1000

Input:

1
3
101
100
000

Output:

100

So, @iceknight1093 How it got AC ?, Please correct me, If I’m wrong!

1 Like

I wonder if there are any tests.

8 Likes

Not all those who wonder are lost

A different approach: CodeChef: Practical coding for everyone

This is actually based on something called the Hilbert Hotel
Nice Video on the topic: How An Infinite Hotel Ran Out Of Room - YouTube

6 Likes

It was the easiest approach bro! well done

Thnx!

Nailed it…i never thought of this…took me a while to get it lol

1 Like

I have implemented my solution remembering this video. I am following this channel for long time.

I did this problem easily by considering:

  • there are N strings given
  • if I see the number of consecutive 1s from the most significant bit, there are N + 1 cases available.

eg: for N = 5, there are 6 possibilities.

  • there can be 0 consecutive 1s from left(eg, 01111)
  • there can be 1 consecutive 1s from left(eg, 10000)
    …
  • there can be 5 consecutive 1s from left(eg, 11111)

I see which among these N + 1 cases is not in the N cases given and print it : )

  • if i find that 3 is not present, i print “11100”.
  • if i find that 4 is not present, i print “11110”.
  • if i find that 1 is not present, i print “10000”.
    and so on…

Submission Link: CodeChef: Practical coding for everyone

1 Like

I had a different solution.
Take a string of length n which has all one’s. If this isn’t already in the given strings you have the answer else you can try to put zero at each position, you can put zero at N indices so one of them surely will not be present in the given string as we have tried N+1 strings.

1 Like

Elegant solution indeed : )

1 Like

I tried the randomized approach but got TLE. Can anyone please guess why ?
Submission link : 50117979

How is it any different from the setter’s solution?

I am sorry, I had not seen the setter’s solution. Smh!

No problem, that was a nice approach nonetheless.

Your random number generation is bad.
Even on the sample, running your code a few times shows that every once in a while, it generates an extremely large number of strings because it generates the same one over and over again (around 5e5 times locally).

Easy fix: use a better generator (fixed code)

1 Like

def bot(a):
cnt=0
while a!=0:
a=a>>1
cnt+=1
return cnt
print(bot(7))

import math as m
for T in range(int(input())):
n=int(input())
if n==1:
st=int(input())
if st==1:
print(0)
print(1)
else:
s=set()
st=input()
temp2=int(“0b”+st,2)
temp=temp2+1
s.add(temp2)
flag=0
for i in range(n-1):
st=input()
c=int(“0b”+st,2)
s.add(c)
for i in range(n):
if temp in s:
temp+=1
else:
v=bot(temp)
if v>n:
flag=1
break
else:
ans=""+bin(temp)
print(ans[2:])
break
#print("#")
if flag==1:
#print("$")
for i in range(n):
if temp2 in s:
temp2-=1

            else:
            #v=m.ciel(m.log2(temp))
                ans=""+bin(temp2)
                print(ans[2:])
                break
            #print(bin(temp2[2:]))

can anyone tell where my solution fails

There are several cases where your code fails.
Here are a couple:

Input
2
1
1
2
10
11
Your output
0
1
1

As you can see, the output should be 2 strings: the first with length 1 and the second with length 2.
You print 3 strings all of length 1, which is clearly wrong.

question states that a string is different when when it differs from the given string or when it of diff size . The string i answered was of different size and my submission wasnt accepted