HackerEarth Puzzled Grid problem solution

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

HackerEarth Puzzled Grid problem solution.

Second solution

Leave a Reply