In this HackerEarth Puzzled Grid problem solution Today, you need to solve a problem on a Puzzled Grid game. "In a grid of n x n size, where each cell has a positive integer, two players compete in several rounds.

Each round starts by both players putting a rock in a random location of the grid. Then, the two players must connect the two rocks with a line that passes through the grid cells (e.g: from a grid cell the line can can expand either horizontally or vertically and never out the grid). Since there may be a lot of ways to connect the two stones, we are only interested in those lines that minimizes the highest cell in their path (e.g: the cell with the highest number should be as small as possible).

You need to find and print this minimized maximum. Can you do it?


HackerEarth Puzzled Grid problem solution


HackerEarth Puzzled Grid problem solution.

#include <stdio.h>
#include <vector>
#include <algorithm>
#include <map>
#include <set>

#define maxn 3000

using namespace std;

int p[maxn*maxn];
int sizeOf[maxn*maxn];

int get( int x ) {
if( p[x] != x ) {
p[x] = get(p[x]);
}
return p[x];
}

void Union( int x, int y ) {
x = get(x), y = get(y);

if( x != y ) {
if( sizeOf[x] < sizeOf[y] ) {
swap(x, y);
}

p[y] = x;
sizeOf[x] += sizeOf[y];
}
}

void init( int n ) {
for( int i = 0; i < n; i++ ) {
p[i] = i;
sizeOf[i] = 1;
}
}

int grid[maxn][maxn];
vector<pair<int,int>> cells[1000001];
vector<int> s[1000001];


int main( void ) {
int n, q;
scanf("%i %i", &n, &q);

const int max_num = 1000000;

for( int i = 0; i < n; i++ ) {
for( int j = 0; j < n; j++ ) {
scanf("%i", &grid[i][j]);
cells[grid[i][j]].push_back(make_pair(i,j));
}
}

vector<int> X1(q), Y1(q), X2(q), Y2(q);
vector<int> lo(q), hi(q), ans(q);

for( int i = 0; i < q; i++ ) {
scanf("%i %i %i %i", &X1[i], &Y1[i], &X2[i], &Y2[i]);
lo[i] = 1, hi[i] = int(1e6)+1;
}

int lg = 21;
while( lg-- ) {
for( int i = 0; i < q; i++ ) {
if( lo[i] <= hi[i] ) {
int mid = (lo[i] + hi[i]) / 2;
s[mid].push_back(i);
}
}

init(n*n);

for( int e = 1; e <= max_num; e++ ) {
if( !cells[e].empty() ) {
for( auto cell : cells[e] ) {
int dx[] = {0, 0, +1, -1};
int dy[] = {+1, -1, 0, 0};

int x = cell.first, y = cell.second;
for( int c = 0; c < 4; c++ ) {
int nx = x + dx[c], ny = y + dy[c];

if( (nx >= 0) && (nx < n) && (ny >= 0) && (ny < n) ) {
if( grid[nx][ny] <= grid[x][y] ) {
int cellId0 = (x * n) + y;
int cellId1 = (nx * n) + ny;
Union(cellId0, cellId1);
}
}
}
}
}

if( !s[e].empty() ) {
for( int idx : s[e] ) {
int cellId0 = (X1[idx] * n) + Y1[idx];
int cellId1 = (X2[idx] * n) + Y2[idx];

if( get(cellId0) == get(cellId1) ) {
ans[idx] = e;
hi[idx] = e - 1;
} else {
lo[idx] = e + 1;
}
}
}
}

for( int i = 1; i <= max_num; i++ ) {
s[i].clear();
}
}

for( int i = 0; i < q; i++ ) {
printf("%i\n", ans[i]);
}

return 0;
}

Second solution

#include <fstream>
#include <iostream>
#include <string>
#include <complex>
#include <math.h>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <stdio.h>
#include <stack>
#include <algorithm>
#include <list>
#include <ctime>
#include <memory.h>
#include <assert.h>

#define y0 sdkfaslhagaklsldk

#define y1 aasdfasdfasdf
#define yn askfhwqriuperikldjk
#define j1 assdgsdgasghsf
#define tm sdfjahlfasfh
#define lr asgasgash
#define norm asdfasdgasdgsd
#define have adsgagshdshfhds

#define eps 1e-6
#define M_PI 3.141592653589793
#define bs 1000000007
#define bsize 350

using namespace std;

const int INF = 1e9;
const int N = 531;
const int M = 600031;

int n, m, ar[N][N];
int x1[M], y1[M], x2[M], y2[M];

vector<pair<int, pair<int, int> > > val_list;
int l[M], r[M];

vector<int> qu_list[M];
int w[M];

int get(int x)
{
if (x == w[x])
return x;
return w[x] = get(w[x]);
}

bool outside(int a, int b)
{
if (a < 0 || a >= n || b < 0 || b >= n)
return true;
return false;
}

void merge(int a, int b)
{
w[a] = b;
}

bool is_inside(int a, int b)
{
return (a >=0 && a < n&&b >= 0 && b < n);
}

void run_merger(int a, int b)
{
for (int dx = -1; dx <= 1; dx++)
{
for (int dy = -1; dy <= 1; dy++)
{
if (abs(dx) + abs(dy) != 1)
continue;
if (outside(a + dx, b + dy))
continue;
if (ar[a + dx][b + dy] > ar[a][b])
continue;
int id1 = a*n + b;
int id2 = (a + dx)*n + (b + dy);
id1 = get(id1);
id2 = get(id2);
merge(id1, id2);
}
}
}

int main(){
ios_base::sync_with_stdio(0);
//cin.tie(0);

//cin >> n >> m;
assert(cin >> n >> m);

assert(2 <= n &&n <= 500);
assert(m >= 1 && m <= 1e5);

for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
//cin >> ar[i - 1][j - 1];
assert(cin >> ar[i - 1][j - 1]);
assert(ar[i - 1][j - 1] >= 1 && ar[i - 1][j - 1] <= 1e6);
}
}

for (int i = 1; i <= m; i++)
{
// cin >> x1[i] >> y1[i] >> x2[i] >> y2[i];
assert(cin >> x1[i] >> y1[i] >> x2[i] >> y2[i]);
assert(x1[i] != x2[i] || y1[i] != y2[i]);
assert(is_inside(x1[i], y1[i]));
assert(is_inside(x2[i], y2[i]));
}

for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
val_list.push_back(make_pair(ar[i - 1][j - 1], make_pair(i - 1, j - 1)));
}
}

sort(val_list.begin(), val_list.end());

for (int i = 1; i <= m; i++)
{
l[i] = 0;
r[i] = val_list.size() - 1;
}

int I = 0;

while (true)
{
for (int i = 0; i < val_list.size(); i++)
qu_list[i].clear();

int flag = 0;

for (int i = 1; i <= m; i++)
{
if (l[i] == r[i])
continue;
flag = 1;
int mid = l[i] + r[i];
mid /= 2;
qu_list[mid].push_back(i);
}

++I;
if (flag == 0)
break;

for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
w[i*n + j] = i*n + j;
}
}

for (int i = 0; i < val_list.size(); i++)
{
int qi = val_list[i].second.first;
int qj = val_list[i].second.second;

run_merger(qi, qj);

for (int j = 0; j < qu_list[i].size(); j++)
{
int id = qu_list[i][j];
int ps1 = x1[id] * n + y1[id];
int ps2 = x2[id] * n + y2[id];
// cout << ps1 << "%" << ps2 << endl;
ps1 = get(ps1);
ps2 = get(ps2);
// cout << id << "%" << i << endl;
if (ps1 == ps2)
r[id] = i;
else
l[id] = i + 1;
}
}
}

for (int i = 1; i <= m; i++)
{
cout << val_list[l[i]].first << endl;
}

cin.get(); cin.get();
return 0;
}