# REACTION - EDITORIAL

Practice

Contest: Division 1

Contest: Division 2

Tester: Teja Vardhan Reddy

Editorialist: Teja Vardhan Reddy

Cakewalk

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

// 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.

I donâ€™t understand this thing that if in the question it is given that â€śstrictly larger(larger and not equal to)â€ť then when my code with only â€ś>â€ť(strictly larger) not working and >=(larger) working?

from itertools import chain
tc=int(input())

def solve(arr,row,column):

if arr[0][0]>=2 or arr[0][column-1]>=2 or arr[row-1][0]>=2 or arr[row-1][column-1]>=2:
return "Unstable"
elif max(arr[0])>=3 or max(arr[-1])>=3 or max(arr[n][0] for n in range(row))>=3 or max(arr[n][-1] for n in range(row))>=3:
return "Unstable"
elif max(chain(*arr))>=4:
return "Unstable"
return "Stable"

for _ in range(tc):
r,c=map(int,input().split())
arr=[list(map(int,input().split())) for _ in range(r)]
print(solve(arr,r,c))


Isnâ€™t it supposed to be â€ś>â€ť in the logics as it has given â€śstrictly largerâ€ť in the question.About the code:-

1. The corner 4 elements always have 2 adjacent element so >=2
2. The corner sides always have 3 adjacent element(except corner oneâ€™s which have 2) so >=3
3. And the rest elements always have 4 adjacent elements so >=4

I am not so sure about time complexity of this code but pretty sure it is either of Linear time or less than that. As max() takes Linear time almost in worst case O(n) and there is 3 max() function. I could have use â€śheapqâ€ť module to make it â€śO(nlogn)â€ť complexity. So instead of doing it in O(n*m) we can do it in â€śO(nlogn)â€ť for sure.

3 Likes