PROBLEM LINK:
Setter: Mohammad Solaiman
Tester: Teja Vardhan Reddy
Editorialist: Teja Vardhan Reddy
DIFFICULTY:
Cakewalk
PREREQUISITES:
Implementation
PROBLEM:
Given a m*n grid. Check for all cells if the number of adjacent cells is strictly greater than number written in that cell ( i.e all cells are stable). Two cells are adjacent if they share a side.
EXPLANATION:
-
Each cell has 4 sides. Hence, there can be atmost 4 adjacent cells to it.
-
For a cell (x,y) possible adjacent cells are (x+1,y),(x,y+1),(x-1,y),(x,y-1). Among these four possible adjacent cells, we need to check how many of them are inside the grid.
-
For a cell (x,y) to be in the grid, 1 \lt x \leq m and 1 \lt y \leq n must hold.
-
Now we iterate over all the m*n cells and count number of adjacent cells for each of them. And then check if for every cell if the number of adjacent cells is strictly greater than number written in that cell.
TIME COMPLEXITY:
-
Counting number of adjacent cells for each cell and checking if a cell is stable takes O(1) time.
-
In the grid we have m*n cells , Hence time complexity is O(m*n).
SOLUTIONS:
Setter's Solution
/// author's solution
#include<bits/stdc++.h>
using namespace std;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
int a[13][13];
int R, C;
int adjacentCells(int i, int j)
{
int cnt = 0;
for (int k = 0; k < 4; k++) {
int x = dx[k]+i;
int y = dy[k]+j;
if (x < 1 || y < 1 || x > R || y > C) continue;
cnt++;
}
return cnt;
}
int main()
{
// freopen("input2.txt", "r", stdin);
// freopen("output2.txt", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(0);
int t;
cin >> t;
for (int ti = 1; ti <= t; ti++) {
cin >> R >> C;
for (int i = 1; i <= R; i++) {
for (int j = 1; j <= C; j++) {
cin >> a[i][j];
}
}
bool isStable = true;
for (int i = 1; i <= R; i++) {
for (int j = 1; j <= C; j++) {
isStable = isStable and (a[i][j] < adjacentCells(i, j));
}
}
cout << (isStable?"Stable":"Unstable") << "\n";
}
return 0;
}
Tester's Solution
//teja349
#include <bits/stdc++.h>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <utility>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <iomanip>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
//setbase - cout << setbase (16); cout << 100 << endl; Prints 64
//setfill - cout << setfill ('x') << setw (5); cout << 77 << endl; prints xxx77
//setprecision - cout << setprecision (14) << f << endl; Prints x.xxxx
//cout.precision(x) cout<<fixed<<val; // prints x digits after decimal in val
using namespace std;
using namespace __gnu_pbds;
#define f(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) f(i,0,n)
#define fd(i,a,b) for(i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define vi vector< int >
#define vl vector< ll >
#define ss second
#define ff first
#define ll long long
#define pii pair< int,int >
#define pll pair< ll,ll >
#define sz(a) a.size()
#define inf (1000*1000*1000+5)
#define all(a) a.begin(),a.end()
#define tri pair<int,pii>
#define vii vector<pii>
#define vll vector<pll>
#define viii vector<tri>
#define mod (1000*1000*1000+7)
#define pqueue priority_queue< int >
#define pdqueue priority_queue< int,vi ,greater< int > >
#define flush fflush(stdout)
#define primeDEN 727999983
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// find_by_order() // order_of_key
typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
int a[123][123];
int r,c;
int check(int i,int j){
if(i<0 || j<0 || i>=r || j>=c)
return 0;
return 1;
}
int d1[4]={1,-1,0,0};
int d2[4]={0,0,-1,1};
int main(){
std::ios::sync_with_stdio(false); cin.tie(NULL);
int t;
cin>>t;
while(t--){
//int r,c;
cin>>r>>c;
int gg=true;
int i,j;
rep(i,r){
rep(j,c){
cin>>a[i][j];
}
}
int k;
int cnt;
rep(i,r){
rep(j,c){
cnt=0;
rep(k,4){
if(check(i+d1[k],j+d2[k])){
cnt++;
}
}
if(cnt<=a[i][j]){
//cout<<cnt<<" "<<i<<" "<<j<<endl;
gg=false;
}
}
}
if(gg==true){
cout<<"Stable"<<endl;
}
else{
cout<<"Unstable"<<endl;
}
}
return 0;
}
Feel free to Share your approach, If it differs. Suggestions are always welcomed. 