AALIEN - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Contest

Author & Tester: Chaitali Srivastava

Editorialist: Chaitali Srivastava

DIFFICULTY:

EASY

PREREQUISITES:

Dynamic Programming

PROBLEM:

You are given a matrix containing primes and non-primes. Given a cell’s coordinates (x_i,y_i) for each of the q queries, determine the least number of primes you could encounter in your path from (1,1) to (x_i,y_i). You could move either right or down in the matrix.

QUICK EXPLANATION:

  • Form a 2 - D DP matrix, initialize the first row and the first column.
  • For every other cell of this matrix set its value as the minimum of the values of the cell above it and the cell left to it.
  • Increment its value by 1 if the corresponding cell in the given matrix is also prime.
  • For each query (x_i,y_i), print the corresponding cell of the DP matrix.

EXPLANATION:

Since we are dealing with prime numbers, it is ideal to store the primes in a sieve before moving further.
At each cell, we have a choice, either to move downward or to move right. This choice gives the intuition of DP.
So, declare another matrix of the same size as the given matrix, lets call it the DP matrix . Each cell of the DP matrix is the answer for the corresponding cell in the matrix given in the question(lets call it grid A).

  • Set the first cell of the matrix as 0 or 1 depending if its prime or not.

  • For the first row of the DP grid, we have only one choice at each cell,i.e., to come from the left. So, set
    dp[0][i] = dp[0][i-1], for every i, where 1 \leq i < n . Also, if A[0][i] is prime, increment the value by 1.

  • For the first column of the DP grid, we have only one choice at each cell,i.e., to come from the cell just above it. So, set
    dp[i][0] = dp[i-1][0], for every i, where 1 \leq i < n Also, if A[i][0] is prime, increment the value by 1.

  • For the rest of the cells, we have two possibilities, either we came to this cell from the left or from above. Since, we want the minimum number of primes, we will check which of the two paths is containing the minimum number of prime cells, and assign it to our current cell, i.e.,
    dp[i][j]=min(dp[i-1][j],dp[i][j-1])
    If A[i][j] is in itself a prime number we will increment dp[i][j] by 1, since we will encounter this prime as well to A[i][j].

  • Now, for each query (x_i,y_i), print the corresponding cell of the dp matrix.

SOLUTIONS:

Setter's Solution 
#include<bits/stdc++.h>
using namespace std;
#define ll long long


int main()
{

  ll v=3000;
  bool prime[v + 1];
  memset(prime, true, sizeof(prime));
 
  for (int p = 2; p * p <= v; p++)
    {
        if (prime[p] == true)
        {
            for (int i = p * p; i <= v; i += p)
                prime[i] = false;
        }
    }
    
ll t;cin>>t;while(t--){
    
ll n,q,i,j;
cin>>n>>q;

ll a[n][n];

for(i=0;i<n;i++) for(j=0;j<n;j++) cin>>a[i][j];

ll dp[n][n];

memset(dp, 0, sizeof(dp));


if(prime[a[0][0]])
{dp[0][0]=1;
}

for(i=1;i<n;i++)
{dp[0][i]=dp[0][i-1];
if(prime[a[0][i]]) dp[0][i]++;
}

for(i=1;i<n;i++)
{
dp[i][0]=dp[i-1][0];
if(prime[a[i][0]]) dp[i][0]++;
}

for(i=1;i<n;i++)
for(j=1;j<n;j++)
{
dp[i][j]=min(dp[i-1][j],dp[i][j-1]);
if(prime[a[i][j]]) dp[i][j]++;
}

while(q--)
{
ll x,y;
cin>>x>>y;
cout<<dp[x-1][y-1]<<endl;
}


}
}

SPACE COMPLEXITY:

Since we are using another matrix of size N*N, our space complexity would be O(N^2).

TIME COMPLEXITY:

Since we have to traverse the matrix of size N*N, our time complexity would be O(N^2).

3 Likes