Naruto and Chunin Exams - (Code Chef Easy Question)

Hello Everyone , Today we will be talking about another interesting yet easy question based on grids and graphs.

Problem:- This is the link to the problem or the question on code chef

We will be following the same approach and similar code we discussed in this blog -> https://knightsprogrammingblog.blogspot.com/2020/04/the-easy-solution-graph-theory.html


The concepts required to understand this problem are :- 
1. Basic Grid Theory (part of graph theory basics )
2. Basic grid traversal code
3. Simple queue implementation

So to solve this problem in the given time limit in the constraints given , we need to first sort the given power queries along with their ith position so that we know where to display its answer .
After sorting the queries , we know that the answer of the ith query will always be less than i+1th query .
So instead of computing the function for all queries step by step , we check till where can the first power person go , we store the answer in the ith position of the array of answers , then for the next query we start from all the blocks where the previous query power couldnt go and continue the code and store the new ans + old ans in the corresponding position of the array of answers.

Finally we output the array of answers and voila , our code is done.

My instance ran in 0.93 seconds which is just under the given time limit of 1s.

After every ith query , we store wherever the ninja couldnt go in a queue and in the next run of function we check if the next ninja can go there and so on .



Here is the C++ code :-
Go through it and you will understand better.


#include <iostream>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;


long int n,m,ans=0,sr,sc,r,c;
long int p;
queue <long int> rq,cq,rq2,cq2;
long int grid[1000][1000];

bool visited[1000][1000]={0};
long int nodes_left_in_layer=1;
long int nodes_in_next_layer2=1;
long int nodes_in_next_layer=0;

long int dr[4]={1,-1,0,0};
long int dc[4]={0,0,1,-1};


void explore_neighbours(long int r,long int c)
{
    long int rr,rc;
    for(int i=0;i<4;i++)
    {
        rr=r+dr[i];
        rc=c+dc[i];
        if(rr>=n || rc>=n)
        {
            continue;
        }
        if(rr<0 || rc<0)
        {
            continue;
        }
        if(visited[rr][rc]==true)
        {
            continue;
        }
        else
        {
            visited[rr][rc]=true;
         if(p>grid[rr][rc])
         {
              ans++;
        rq.push(rr);
        cq.push(rc);
        nodes_in_next_layer++;
         }
         else
         {  visited[rr][rc]=true;
             rq2.push(rr);
             cq2.push(rc);
             nodes_in_next_layer2++;
         }
        }
       
     
       
    }
}


int solve()
{
    nodes_left_in_layer=nodes_in_next_layer2;
    nodes_in_next_layer2=0;
    nodes_in_next_layer=0;
    nodes_left_in_layer=0;
    long int z=rq2.size();
    while(z--)
    {
        if(grid[rq2.front()][cq2.front()]<p)
        {
            ans++;
            visited[rq2.front()][cq2.front()]=true;
            rq.push(rq2.front());
            cq.push(cq2.front());
            rq2.pop();
            cq2.pop();
            nodes_left_in_layer++;
        }
        else
        {
            rq2.push(rq2.front());
            rq2.pop();
            cq2.push(cq2.front());
            cq2.pop();
        }
           
    }
   
 while(rq.size()>0)
 {
     r=rq.front();
     c=cq.front();
     rq.pop();
     cq.pop();
    /* if(r==n-1 && c==n-1)
     {
         return ans;
         break;
     }
     else
     {*/
   
           explore_neighbours(r,c);
         nodes_left_in_layer--;
         if(nodes_left_in_layer==0)
         {
             nodes_left_in_layer=nodes_in_next_layer;
             nodes_in_next_layer=0;
             //ans++;
         }
     
     //}
 }
   
   
 return ans; 
   
}



int main() {
   
    long int t;
    cin>>t;
    while(t--)
    {
        while(cq2.size()>0)
        {
            cq2.pop();
            rq2.pop();
        }
        while(cq.size()>0)
        {
            cq.pop();
            rq.pop();
        }
        ans=0;
        long int q;
        long int x;
       
        cin>>n;
        cin>>q;
    int i=0,j=0;
        while(i!=n)
    {
        j=0;
        while(j!=n)
        {
            cin>>x;
            grid[i][j]=x;
            visited[i][j]=false;
            j++;
        }
        //cout<<endl;
        i++;
    }
    i=0;j=0;
 
  i=0;
  long int arr[q];
  vector<pair<long int,int>> v;
  while(i!=q)
  {
      cin>>arr[i];
      v.push_back(make_pair(arr[i],i));
      i++;
     
  }
  sort(v.begin(),v.end());
  rq2.push(0);
  cq2.push(0);
  i=0;
  while(i!=q)
  {
      p=v[i].first;
      arr[v[i].second]=solve();
   
      i++;
  }
 
  i=0;
  while(i!=q)
  {
      cout<<arr[i]<<endl;
      i++;
  }   
    }
   
// your code goes here
return 0;
}





Hope you understood the question and its solution.
Stay tuned for solutions of more problems , If you want me to solve a particular question , do let me know in the comment section .
Subscribe to get free updates and follow to stay tuned !
Signing off for now