PROBLEM LINK:
Practice
Div-3 Contest
Div-2 Contest
Div-1 Contest
Setter: Daksh Garg, Aditya Kumar Singh
Tester: Shikhar Sharma,Istvan Nagy
DIFFICULTY:
Easy-Medium
PREREQUISITES:
Constructive Algorithms, Greedy
PROBLEM:
A maxpool filter of 2x2 matrix is applied on a matrix of N X N with all distinct elements from 1 to N^2. That is for each 2 X 2 matrix you have to write the maximum element in corresponding matrix of size (N−1) X (N−1).
You have to derive any valid question matrix(must contain all the numbers from 1 to N * N ) back from the (N-1)*(N-1) matrix.
EXPLANATION:
Greedily travel the input matrix from smaller to larger value and fill it in corresponding valid position in output matrix and for remaining vacant position for all the filter of that value fill the smallest remaining element that is not present in the matrix.
I am explaining the solution using the example:
2
7 7
9 8
Initial matrix
0 0 0
0 0 0
0 0 0
Using smallest elements in the matrix and {7,8,9} i.e 7
Remaining elements {1,2,3,4,5,6}
Fill 7 at any valid position and fill all the vacant positions that gives filter 7 by remaining smallest elements
1 7 4
2 3 5
0 0 0
Similarly
Using smallest elements in the matrix and {8,9}
Remaining elements {6}
1 7 4
2 3 5
0 8 6
Similarly
Using smallest elements in the matrix and {9}
Remaining elements {}
1 7 4
2 3 5
9 8 6
Important point: Elements can occur at most four times and valid positions can be found easily.
Filling remaining smaller elements is best because next elements which are greater would not come in that filter.
SOLUTIONS:
Setter's Solution
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define is insert
#define rep1(i,a,b) for(long long i=a;i<=b;i++)
#define F first
#define S second
#define file ifstream fin("input.txt");ofstream fout("output.txt");
#define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define fr(n) for(long long i=0;i<n;i++)
#define rep(i,a,b) for(long long i=a;i<b;i++)
#define ALL(x) (x).begin(), (x).end()
typedef long long int ll;
typedef long double ld;
typedef vector<ll> vi;
ll ans[205][205],n,a;
set<ll>se,absent;
vector<pair<ll,ll> >pos[100000];
void fill_(ll x)
{
ll i=0,j=0;
for(auto p:pos[x])
{
i=max(i,p.F);
j=max(j,p.S);
}
if(ans[i][j]!=0)
{
if(pos[x].size()==1)
{
i=pos[x][0].F;
j=pos[x][0].S;
if(ans[i+1][j]==0)
i++;
else if(ans[i][j+1]==0)
j++;
else if(ans[i+1][j+1]==0)
{
i++;
j++;
}
}
else if(pos[x].size()==2)
{
i=pos[x][0].F+1;
j=pos[x][0].S+1;
}
}
ans[i][j]=x;
for(auto p:pos[x])
{
for(int i=p.F;i<(p.F+2);i++)
{
for(int j=p.S;j<(p.S+2);j++)
{
if(i<=n&&j<=n&&ans[i][j]==0)
{
ans[i][j]=*absent.begin();
absent.erase(absent.begin());
}
}
}
}
}
void solve()
{
se.clear();
absent.clear();
cin>>n;
for(int i=0;i<=(n*n);i++)pos[i].clear();
rep(i,0,n)rep(j,0,n)ans[i][j]=0;
n--;
rep(i,0,n)
{
rep(j,0,n)
{
cin>>a;
se.is(a);
pos[a].pb({i,j});
}
}
for(int i=1;i<=((n+1)*(n+1));i++)
if(se.find(i)==se.end())
absent.is(i);
for(auto x:se)
fill_(x);
rep(i,0,n+1)
{
rep(j,0,n+1)
{
cout<<ans[i][j]<<" ";
}
cout<<endl;
}
}
int32_t main()
{
#ifndef ONLINE_JUDGE
freopen("inputf.in", "r", stdin);
freopen("outputf.in", "w", stdout);
#endif
fast;
ll t=1;
cin>>t;
while(t--)
solve();
return 0;
}
Tester's Solution
#include<bits/stdc++.h>
using namespace std;
#define int long long int
#define mp(a,b) make_pair(a,b)
#define vi vector<int>
#define mii map<int,int>
#define mpi map<pair<int,int>,int>
#define vp vector<pair<int,int> >
#define pb(a) push_back(a)
#define fr(i,n) for(i=0;i<n;i++)
#define rep(i,a,n) for(i=a;i<n;i++)
#define F first
#define S second
#define endl "\n"
#define fast std::ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define mod 1000000007
#define dom 998244353
#define sl(a) (int)a.length()
#define sz(a) (int)a.size()
#define all(a) a.begin(),a.end()
#define pii pair<int,int>
#define mini 2000000000000000000
#define time_taken 1.0 * clock() / CLOCKS_PER_SEC
//const long double pi = acos(-1);
//mt19937_64 mt(chrono::steady_clock::now().time_since_epoch().count());
//primes for hashing 937, 1013
template<typename T, typename U> static inline void amin(T &x, U y)
{
if (y < x)
x = y;
}
template<typename T, typename U> static inline void amax(T &x, U y)
{
if (x < y)
x = y;
}
long long readInt(long long l,long long r,char endd){
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true){
char g=getchar();
// char g = getc(fp);
if(g=='-'){
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g && g<='9'){
x*=10;
x+=g-'0';
if(cnt==0){
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);
assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd){
if(is_neg){
x= -x;
}
// cout << x << " " << l << " " << r << endl;
assert(l<=x && x<=r);
return x;
} else {
assert(false);
}
}
}
string readString(int l,int r,char endd){
string ret="";
int cnt=0;
while(true){
char g=getchar();
// char g=getc(fp);
assert(g != -1);
if(g==endd){
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt && cnt<=r);
return ret;
}
long long readIntSp(long long l,long long r){
return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
return readString(l,r,'\n');
}
string readStringSp(int l,int r){
return readString(l,r,' ');
}
const int maxn = 200, maxt = 5;
void shikhar7s(int cas)
{
int n,i,j;
n = readIntLn(2, maxn);
int a[n][n],x,re[n][n];
vp v[n*n+5];
memset(a,0,sizeof(a));
fr(i,n-1)
{
fr(j,n-1)
{
x = (j == n - 2 ? readIntLn(1, n * n) : readIntSp(1, n * n));
v[x].pb(mp(i,j));
}
}
fr(i,n)
{
fr(j,n)
{
re[i][j]=4;
int x=i,y=j;
if((!x||x==n-1)&&(!y||y==n-1))
re[i][j]=1;
else if(!x||!y||x==n-1||y==n-1)
re[i][j]=2;
}
}
int vis[n][n],co,k;
queue<pii> q;
memset(vis,0,sizeof(vis));
for(i=n*n;i;i--)
{
if(sz(v[i]))
{
int x=v[i][0].F,y=v[i][0].S;
mpi c;
c[mp(x,y)]=1;
c[mp(x,y+1)]=1;
c[mp(x+1,y)]=1;
c[mp(x+1,y+1)]=1;
rep(j,1,sz(v[i]))
{
int x=v[i][j].F,y=v[i][j].S;
c[mp(x,y)]++;
c[mp(x,y+1)]++;
c[mp(x+1,y)]++;
c[mp(x+1,y+1)]++;
}
x=v[i][0].F;
y=v[i][0].S;
int xx,yy;
vp w;
if(c[mp(x,y)]==sz(v[i]))
w.pb(mp(x,y));
if(c[mp(x,y+1)]==sz(v[i]))
w.pb(mp(x,y+1));
if(c[mp(x+1,y)]==sz(v[i]))
w.pb(mp(x+1,y));
if(c[mp(x+1,y+1)]==sz(v[i]))
w.pb(mp(x+1,y+1));
c.clear();
int jj;
fr(jj,sz(w))
{
x=w[jj].F;
y=w[jj].S;
a[x][y]=i;
co=0;
if(x&&y)
{
int ma=0;
for(j=-1;j<=0;j++)
{
for(k=-1;k<=0;k++)
ma=max(ma,a[x+j][y+k]);
}
if(ma==i)
co++;
}
if(x<n-1&&y)
{
int ma=0;
for(j=0;j<=1;j++)
{
for(k=-1;k<=0;k++)
ma=max(ma,a[x+j][y+k]);
}
if(ma==i)
co++;
}
if(x&&y<n-1)
{
int ma=0;
for(j=-1;j<=0;j++)
{
for(k=0;k<=1;k++)
ma=max(ma,a[x+j][y+k]);
}
if(ma==i)
co++;
}
if(x<n-1&&y<n-1)
{
int ma=0;
for(j=0;j<=1;j++)
{
for(k=0;k<=1;k++)
ma=max(ma,a[x+j][y+k]);
}
if(ma==i)
co++;
}
a[x][y]=0;
if(co==sz(v[i]))
{
xx=x;
yy=y;
break;
}
}
a[xx][yy]=i;
fr(jj,sz(v[i]))
{
int xx=v[i][jj].F;
int yy=v[i][jj].S;
for(j=0;j<=1;j++)
{
for(k=0;k<=1;k++)
{
if(xx+j>=0&&xx+j<n&&yy+k>=0&&yy+k<n)
{
re[xx+j][yy+k]--;
if(!re[xx+j][yy+k]&&!a[xx+j][yy+k])
q.push(mp(xx+j,yy+k));
}
}
}
}
}
else
{
int x=q.front().F;
int y=q.front().S;
q.pop();
a[x][y]=i;
int jj;
fr(jj,sz(v[i]))
{
int xx=v[i][jj].F;
int yy=v[i][jj].S;
for(j=0;j<=1;j++)
{
for(k=0;k<=1;k++)
{
if(xx+j>=0&&xx+j<n&&yy+k>=0&&yy+k<n)
{
re[xx+j][yy+k]--;
if(!re[xx+j][yy+k]&&!a[xx+j][yy+k])
q.push(mp(xx+j,yy+k));
}
}
}
}
}
}
fr(i,n)
{
fr(j,n)
{
cout<<a[i][j]<<" ";
}
cout<<endl;
}
// cerr << "HI";
}
signed main()
{
fast;
//freopen("input.txt", "rt", stdin);
//freopen("output.txt", "wt", stdout);
int t=readIntLn(1, maxt);
int cas=1;
while(cas<=t)
{
//cout<<"Case #"<<cas<<": ";
shikhar7s(cas);
cas++;
}
assert(getchar()==-1);
return 0;
}