PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Author: Pranav Rajagopalan
Tester: Rahul Dugar
Editorialist: Aman Dwivedi
DIFFICULTY:
Easy-Medium
PREREQUISITES:
Observation, Constructive
PROBLEM:
You are given a grid with N rows and M columns. You have R red tiles, G green tiles and B blue tiles such that R+G+B=N*M. Your task is to place tiles in such a way that for each tile, there are at-most two distinct colours among those tiles that are adjacent with it.
The tiles are said to be adjacent, if they share a common side.
QUICK EXPLANATION:
-
Sort the tiles in ascending order on the basis of the number of tiles that are present initially.
-
We can classify each cell of the grid on the basis of parity.
-
Fill the even parity cell of the grid. with the colour which has minimum number of tiles.
-
Fill the odd parity cell of the grid. with the colour which has second-most number of tiles.
-
Fill the remaining cells of the grid, with the colour which has maximum number of tiles.
EXPLANATION:
We are given a grid with N rows and M columns. We have R red tiles, G green tiles and B blue tiles such that R+G+B=N*M. Your task is to place tiles in such a way that for each tile, there are at-most two distinct colours among those tiles that are adjacent with it.
We can classify the cells of the grid on the basis of parity.
Claim: Parity of a cell and any cell which is adjacent to it is always different,
Proof
If there is a cell (i,j), then the adjacent cells of this cell are (i-1,j), (i+1,j), (i,j-1) and (i,j+1). We can distinguish the cells and its adjacent cells on the basis of parity.
S=(i+j) \\ S_{up}=(i-1+j) \\ S_{down}=(i+1+j) \\ S_{left}=(i+j-1) \\ S_{right}=(i+j+1)We can clearly see that the parity of S is different from that of S_{up}, S_{down}, S_{left} and S_{right}.
We can clearly see there are two types of cell on the basis of parity. We will try to fill the even parity cells with the colour that has minimum number of tiles, odd parity cells with the colour that has second-most maximum number of tiles. And the remaining cells with the colour that has maximum number of tiles.
This type of arrangement is beneficial because the colour with minimum number of tiles can never exceed the number of the cells with even parity. Similarly, we can say that for the colour with second-most maximum number of tiles and the number of odd parity cells.
Proof
When N*M is Odd.
The number of even parity cells in a grid are \lceil \frac{N*M}{2} \rceil, whereas odd parity cells are \lfloor \frac{N*M}{2} \rfloor. We are given with the condition as:
R+G+B=N*MFor a colour to exceed with the number of cells of any parity, the number of tiles of this colour should be at-least \lceil \frac{N*M}{2} \rceil. Let us suppose this colour be Red. Now,
\lceil \frac{N*M}{2} \rceil + G+B=N*M \\ G+B=\lfloor \frac{N*M}{2} \rfloorAs, \lceil \frac{N*M}{2} \rceil \ge \lfloor \frac{N*M}{2} \rfloor, we say that G+B \ge R. Hence R is the colour with the maximum number of tiles.
Similarly, We can prove when N*M is Even.
Our goal was to place tiles in such a way that for each tile, there are at-most two distinct colours among those tiles that are adjacent with it. This type of arrangement ensures us that for any tile there will be at-most two distinct colours among those tiles that are adjacent to it.
Colour with minimum number of tiles
A colour X which has minimum number of tiles will be always filled in the cells which has even parity. As a cell and any of its adjacent cell always have different parity, then there will be no tile of colour X, which is adjacent to it. Hence, there will be at-most two distinct colours among those tiles which are adjacent to it.
Colour with second-most maximum number of tiles
This case is exactly same as that of Colour with minimum number of tiles.
Colour with maximum number of tiles
A colour X which has maximum number of tiles can be filled in any cell. But when any cell is filled, then its up and left cell has already been filled
When colour of neither upper nor left tile is X.
It means that the colour of the upper tile and left tile is same, say Y since both the cells are of the same parity. Now the colour of the right cell and down cell will either be Y or X. Hence, we say, that there will be at-most two distinct colours among those tiles which are adjacent to it.
When colour of upper or left tile (possibly both) is X.
It means that the the colours which has minimum and second-minimum number of tiles have been filled. Now we are only left with the colour which has maximum number of tiles i.e. X. So the colour of right cell and down cell should be X. Hence, we say, that there will be at-most two distinct colours among those tiles which are adjacent to it.
Finally, we output the desired arrangement.
UNDERSTANDING WITH A SIMPLE ANALOGY
To expand on how this kind of a distribution of tiles would never allow a tile to be surrounded by more than 2 colours, let us consider a simpler analogy. In a chess board there are cells of 2 colours, the white ones being the cells with even parity while the black ones have an odd parity. There are thus no two adjacent cells of the same colour, the black ones being surrounded by all white cells and vice versa. Now suppose that a part of these cells was to be replaced by a different colour altogether, let us assume it to be grey for convenience.
Since no white cell is adjacent to another white one, if you were to replace some of these white cells with grey, the only difference it would make is in the number of colours that the neighbours of black cells possess, which would now be increased to two colours (white and grey) instead of white alone. On the other hand if you were to replace some of the the black cells with grey, since no two black cells are adjacent either, the only difference this replacement would make is in the number of colours of the neighbours of white cells, which would now be two (black and grey) instead of black alone. In either type of replacements, the number of neighbouring colours would not exceed two.
TIME COMPLEXITY:
O(N*M) per testcase.
SOLUTIONS:
Setter
#include <bits/stdc++.h>
#define int long long
using pii=std::pair<int,int>;
using namespace std;
const int maxn = 1005;
int t, n, m, x;
pii cnt[3];
char cols[3] = {'R', 'G', 'B'};
char grid[maxn][maxn];
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> t;
for(int cases = 0; cases < t; cases++)
{
cin >> n >> m;
for(int i = 0; i < 3; i++)
{
cin >> x;
cnt[i] = {x, i};
}
sort(cnt, cnt + 3); // Sort tiles by their count
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++)
{
// Check if we are on cells with odd or even parity
// (black or white cells in chess board terms)
int par = (i + j) & 1;
if(cnt[par].first > 0)
{
// First we use tiles of the given parity, clearly
// they can't exceed the number of cells of the given
// parity (otherwise they would be the max count)
cnt[par].first--;
grid[i][j] = cols[cnt[par].second];
}
else
{
// Now we pad the remaining cells of both parities
// with tiles of the highest count (these haven't
// been used for either parity except for this).
grid[i][j] = cols[cnt[2].second];
}
// So each parity has tiles of colours {parity, highest}.
// All cells adjacent to a given cell are of the opposite
// parity to it, therefore they all use the same two colours
// and each cell will have at max 2 distinct colours among
// tiles sharing a side with it.
}
for(int i = 0; i < n; i++)
{
for(int j = 0; j < m; j++)
cout << grid[i][j];
cout << "\n";
}
}
return 0;
}
Tester
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#ifndef rd
#define trace(...)
#define endl '\n'
#endif
#define pb push_back
#define fi first
#define se second
#define int long long
typedef long long ll;
typedef long double f80;
#define double long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define sz(x) ((long long)x.size())
#define fr(a,b,c) for(int a=b; a<=c; a++)
#define rep(a,b,c) for(int a=b; a<c; a++)
#define trav(a,x) for(auto &a:x)
#define all(con) con.begin(),con.end()
const ll infl=0x3f3f3f3f3f3f3f3fLL;
const int infi=0x3f3f3f3f;
//const int mod=998244353;
const int mod=1000000007;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> oset;
auto clk=clock();
mt19937_64 rang(chrono::high_resolution_clock::now().time_since_epoch().count());
int rng(int lim) {
uniform_int_distribution<int> uid(0,lim-1);
return uid(rang);
}
int powm(int a, int b) {
int res=1;
while(b) {
if(b&1)
res=(res*a)%mod;
a=(a*a)%mod;
b>>=1;
}
return res;
}
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();
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;
}
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();
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,' ');
}
char a[505][505];
int sum_nm=0;
void solve() {
int n=readIntSp(1,500),m=readIntSp(1,500);
int r=readIntSp(0,n*m),g=readIntSp(0,n*m),b=readIntLn(0,n*m);
sum_nm+=n*m;
assert(r+g+b==n*m&&sum_nm<=300'000);
vector<pair<char,int>> pp={{'R',r},{'G',g},{'B',b}};
set<vi> pp1;
fr(i,1,n)
pp1.insert({min(m,n-i+1),i,1});
fr(i,1,m)
pp1.insert({min(n,m-i+1),1,i});
for(auto j:pp)
while(j.se) {
auto it=pp1.upper_bound({min({j.se,n,m}),n,m});
it--;
j.se-=(*it)[0];
for(int x=(*it)[1],y=(*it)[2]; x<=n&&y<=m; x++,y++)
a[x][y]=j.fi;
pp1.erase(it);
}
fr(i,1,n) {
fr(j,1,m)
cout<<a[i][j];
cout<<endl;
}
}
signed main() {
ios_base::sync_with_stdio(0),cin.tie(0);
srand(chrono::high_resolution_clock::now().time_since_epoch().count());
cout<<fixed<<setprecision(10);
int t=readIntLn(1,15000);
// int t;
// cin>>t;
fr(i,1,t)
solve();
assert(getchar()==EOF);
#ifdef rd
cerr<<endl<<endl<<endl<<"Time Elapsed: "<<((double)(clock()-clk))/CLOCKS_PER_SEC<<endl;
#endif
}
Editorialist
#include<bits/stdc++.h>
using namespace std;
string col="RGB";
void solve(){
int n,m; cin>>n>>m;
int r,g,b; cin>>r>>g>>b;
vector <string> s(n);
pair <int,int> color[3];
color[0]={r,0};
color[1]={g,1};
color[2]={b,2};
sort(color,color+3);
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(color[(i+j)%2].first!=0){
s[i]+=col[color[(i+j)%2].second];
color[(i+j)%2].first--;
}
else{
s[i]+=col[color[2].second];
}
}
}
for(int i=0;i<n;i++){
cout<<s[i]<<"\n";
}
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int t; cin>>t;
while(t--){
solve();
}
return 0;
}