PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: notsoloud
Tester: yash_daga
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
None
PROBLEM:
Given N, construct an N\times N boolean matrix such that the 2N strings representing its rows and columns are all distinct.
EXPLANATION:
If N = 2, it’s impossible to construct a valid matrix: this is covered by the sample cases.
For N \geq 3, it’s always possible to find a valid matrix.
There are several constructions, here’s one:
Suppose you had two binary strings A and B. Two simple conditions for when they aren’t equal are:
- A and B start with different characters (for example, 1001 and 0001); or
- A and B start with the same character, but the longest equal prefix is of different length (for example, 0001 and 0011).
Using these ideas, a natural starting point is a matrix that looks something like
That is, a matrix whose lower triangle and diagonal are entirely filled with ones, and upper triangle with zeros.
You might notice that this matrix almost works: the rows are distinct from each other since they start with different numbers of ones; similarly the columns are distinct from each other.
Also, every row starts with a 1 and almost every column starts with a 0, so they’re distinct as well.
The only issue is that the first column equals the last row.
All we need to do is find a minor change in one of them that makes them different, while keeping the others distinct.
One way to do this is to change exactly one cell, and set A_{2, 1} = 0.
This results in the matrix
which satisfies the conditions when N \geq 3.
TIME COMPLEXITY
\mathcal{O}(N^2) per testcase.
CODE:
Setter's code (C++)
//clear adj and visited vector declared globally after each test case
//check for long long overflow
//Mod wale question mein last mein if dalo ie. Ans<0 then ans+=mod;
//Incase of close mle change language to c++17 or c++14
//Check ans for n=1
// #pragma GCC target ("avx2")
// #pragma GCC optimize ("O3")
// #pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define int long long
#define IOS std::ios::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL);cout.precision(dbl::max_digits10);
#define pb push_back
#define mod 1000000007ll //998244353ll
#define lld long double
#define mii map<int, int>
#define pii pair<int, int>
#define ll long long
#define ff first
#define ss second
#define all(x) (x).begin(), (x).end()
#define rep(i,x,y) for(int i=x; i<y; i++)
#define fill(a,b) memset(a, b, sizeof(a))
#define vi vector<int>
#define setbits(x) __builtin_popcountll(x)
#define print2d(dp,n,m) for(int i=0;i<=n;i++){for(int j=0;j<=m;j++)cout<<dp[i][j]<<" ";cout<<"\n";}
typedef std::numeric_limits< double > dbl;
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
//member functions :
//1. order_of_key(k) : number of elements strictly lesser than k
//2. find_by_order(k) : k-th element in the set
const long long N=200005, INF=2000000000000000000;
const int inf=2e9 + 5;
lld pi=3.1415926535897932;
int lcm(int a, int b)
{
int g=__gcd(a, b);
return a/g*b;
}
int power(int a, int b, int p)
{
if(a==0)
return 0;
int res=1;
a%=p;
while(b>0)
{
if(b&1)
res=(1ll*res*a)%p;
b>>=1;
a=(1ll*a*a)%p;
}
return res;
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int getRand(int l, int r)
{
uniform_int_distribution<int> uid(l, r);
return uid(rng);
}
void solve(int n)
{
if(n==2) {
cout << "-1" << endl;
return;
}
string s = "";
for(int i=1;i<=n;i++) {
s += "0";
}
cout<<s<<endl;
s.clear();
for(int i = n-2; i >= 0; i--){
s += "1";
for(int j = 0; j<n-1; j++){
if(j == i) s += "1";
else s += "0";
}
cout<<s<<endl;
s.clear();
}
}
int32_t main()
{
// IOS;
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
if(n<13)
solve(n);
else
{
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
cout<<getRand(0, 1);
cout<<"\n";
}
}
}
}
Tester's code (C++)
//clear adj and visited vector declared globally after each test case
//check for long long overflow
//Mod wale question mein last mein if dalo ie. Ans<0 then ans+=mod;
//Incase of close mle change language to c++17 or c++14
//Check ans for n=1
// #pragma GCC target ("avx2")
// #pragma GCC optimize ("O3")
// #pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define int long long
#define IOS std::ios::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL);cout.precision(dbl::max_digits10);
#define pb push_back
#define mod 1000000007ll //998244353ll
#define lld long double
#define mii map<int, int>
#define pii pair<int, int>
#define ll long long
#define ff first
#define ss second
#define all(x) (x).begin(), (x).end()
#define rep(i,x,y) for(int i=x; i<y; i++)
#define fill(a,b) memset(a, b, sizeof(a))
#define vi vector<int>
#define setbits(x) __builtin_popcountll(x)
#define print2d(dp,n,m) for(int i=0;i<=n;i++){for(int j=0;j<=m;j++)cout<<dp[i][j]<<" ";cout<<"\n";}
typedef std::numeric_limits< double > dbl;
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
//member functions :
//1. order_of_key(k) : number of elements strictly lesser than k
//2. find_by_order(k) : k-th element in the set
const long long N=200005, INF=2000000000000000000;
const int inf=2e9 + 5;
lld pi=3.1415926535897932;
int lcm(int a, int b)
{
int g=__gcd(a, b);
return a/g*b;
}
int power(int a, int b, int p)
{
if(a==0)
return 0;
int res=1;
a%=p;
while(b>0)
{
if(b&1)
res=(1ll*res*a)%p;
b>>=1;
a=(1ll*a*a)%p;
}
return res;
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int getRand(int l, int r)
{
uniform_int_distribution<int> uid(l, r);
return uid(rng);
}
void solve(int n)
{
if(n==2) {
cout << "-1" << endl;
return;
}
string s = "";
for(int i=1;i<=n;i++) {
s += "0";
}
cout<<s<<endl;
s.clear();
for(int i = n-2; i >= 0; i--){
s += "1";
for(int j = 0; j<n-1; j++){
if(j == i) s += "1";
else s += "0";
}
cout<<s<<endl;
s.clear();
}
}
int32_t main()
{
// IOS;
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
if(n<20)
solve(n);
else
{
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
cout<<getRand(0, 1);
cout<<"\n";
}
}
}
}
Editorialist's code (Python)
for _ in range(int(input())):
n = int(input())
if n == 2: print(-1)
else:
for i in range(1, n+1):
if i != 2: print('1'*i + '0'*(n-i))
else: print('01' + '0'*(n-i))