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.
#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("%in", 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;
}
