HackerEarth Roy and Tiles problem solution

In this HackerEarth Roy and Tiles problem solution, Roy is playing Tiles game. It consists of a Source node and Destination node and a tiles grid of size NxN.

Grid lies in between Source and Destination (See the image below).

All of them have some value associated with them denoted by S (Source value), D (Destination value) and grid[i][j] (tile value) where 1≤i≤N, and 1≤j≤N.

Roy is at the Source node and he has to reach Destination node to finish the game. Rules of the game are:

We can move from Source to any tile of row1, if the value of that tile is 1 greater than Source. In other words, we can move from source to grid[1][j] , if grid[1][j] = 1+S where 1≤j≤N.

We can move from rowi to any tile of rowi+1, if the value of the tile at rowi+1 is 1 greater than the current tile's value. In other words, we can move from grid[i][j1] to grid[i+1][j2], if grid[i+1][j2] = 1+grid[i][j1] where 1≤j1, j2≤N.

We can move from last row to Destination node, if the value of the Destination node is 1 greater than the current tile's value. In other words, we can move from grid[N][j] to Destination node, if D = 1+grid[N][j] where 1≤j≤N.

Your task is to find the number of ways Roy can move from Source to Destination node. Since the answer can be very large, output it modulo 1000000007. Note that there are several queries with separate values of S and D on the same grid.

HackerEarth Roy and Tiles problem solution.

#include <bits/stdc++.h>
#define MOD 1000000007
using namespace std;
int main()
{
    int t;
    scanf(" %d",&t);
    while(t--)
    {
        int n;
        scanf(" %d",&n);
        vector <long long> grid[n+1];
        long long tmp;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                scanf(" %lld",&tmp);
                grid[i].push_back(tmp);
            }
            //we sort each row, it will help us to find number of occurences of any number in logn
            //we can also use a map and store frequency count, it will have the same complexity
            sort(grid[i].begin(),grid[i].end());
        }
        int q;
        scanf(" %d",&q);
        while(q--)
        {
            long long start, dest;
            scanf(" %lld %lld",&start,&dest);
            if((dest-start) != (n+1))
            {
                printf("0\n");
            }
            else
            {
                long long res = 1;
                long long look_up = start+1;
                for(int i=1;i<=n;i++)
                {
                    long long count;
                    vector<long long>::iterator low, up;
                    low = lower_bound(grid[i].begin(), grid[i].end(), look_up);
                    up = upper_bound(grid[i].begin(), grid[i].end(), look_up);
                    count = (up-grid[i].begin()) - (low-grid[i].begin());
                    res *=count;
                    res %= MOD;
                    if(count == 0)
                    {
                        break;
                    }
                    else
                    {
                        look_up++;
                    }
                }
                if(dest == look_up)
                {
                    res *= 1;
                }
                else
                {
                    res *= 0;
                }
                printf("%lld\n",res);
            }
        }
    }
    return 0;
}

Second solution

#include <cstdio>
#include <vector>
#include <algorithm>
#include <cassert>
#include <map>
 
using namespace std;
 
#define MAXT 10
#define MAXN 1000
#define MAXV 1000000000
#define MAXQ 1000
#define MOD 1000000007
 
int S, D, N, Q;
map<int,int> G[MAXN];
 
int main(){
    int T, v;
    int qn = 0;
    scanf("%d", &T);
    assert(T>0 and T<=MAXT);
    while(T--){
        for(int i=0;i<MAXN;i++)
            G[i].clear();
        scanf("%d", &N);
        assert(N>0 and N<=MAXN);
        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                scanf("%d", &v);
                assert(v>=0 and v<=MAXV);
                //G[i].push_back(v);
                if(G[i].find(v)!=G[i].end())
                    G[i][v] = G[i][v] + 1;
                else
                    G[i][v] = 1;
            }
            //sort(G[i].begin(), G[i].begin()+N);
        }
 
        scanf("%d", &Q);
        assert(Q>0 and Q<=MAXQ);
        qn = qn + (long long)Q*(long long)N;
        while(Q--){
            scanf("%d %d", &S, &D);
            assert(S>0 and S<=MAXV);
            assert(D>0 and D<=MAXV);
            //assert(S<=D);
            long long ans = 1;
            for(int i=0;i<N;i++){
                S++;
                if(G[i].find(S)!=G[i].end()){
                    ans = (ans*(long long)G[i][S])%MOD;
                }else
                    ans = 0;
                //printf("%d %lld\n", i, ans);
            }
            //test1
            if(S!=D-1)
                ans = 0;
            printf("%lld\n", ans);
        }
    }
    assert(qn<=MAXN*MAXQ);
    return 0;
}