# DISTMAT - Editorial

Author: notsoloud
Tester: yash_daga
Editorialist: iceknight1093

TBD

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

\begin{bmatrix} 1 & 0 & 0 & \ldots & 0 \\ 1 & 1 & 0 & \ldots & 0 \\ 1 & 1 & 1 & \ldots & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & 1 & 1 & \ldots & 1 \end{bmatrix}

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

\begin{bmatrix} 1 & 0 & 0 & \ldots & 0 \\ \textcolor{red}{0} & 1 & 0 & \ldots & 0 \\ 1 & 1 & 1 & \ldots & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & 1 & 1 & \ldots & 1 \end{bmatrix}

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

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

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


Superb.
Can you provide the proof??
@iceknight1093

thanks

Proof of what, that the rows and columns are distinct in my construction?
Most of that is already present in the editorial.

• Every row starts with a different number of ones (1, 0, 3, 4, \ldots, N, so they’re all distinct)
• Similarly every column starts with a different number of zeros
• Almost every row starts with 1 and almost every column starts with 0, so they’re different from each other
• The only exceptions are:
• Row 1 and column 1 start with a 1, but are obviously different (100\ldots and 101\ldots)
• Column 1 and rows \geq 3 start with a 1, but again are obviously different
• Row 2 starts with a 0, but again you can see it’s different from all the columns that start with a 0 (since none of the columns are 010\ldots)

All of this relies on the fact that N\geq 3, which is fine since we took care of N = 2 separately.

1 Like