Help needed in Solving a Problem

help
1

Problem Statement:
Given two Integers M,N and a Grid of size M x N, the task is to find number of Beautiful Paths from Top Left Cell (0,0) to Bottom Right Cell(M-1,N-1). A Beautiful Path has the following Constraints:

  • From each cell you can either move right or down
  • The Product of values along the path should have odd number of factors

Since the Output could be very large, compute it modulo 10^9+7.
Input Format:
First line contains T denoting the Number of Test Cases. Description of T Test cases follows.

  • First line of each Test Case contains two integers M,N
  • M lines follow, each line containing N integers.

Output Format:

  • For each test case, output on a single line, an Integer denoting the Number of Beautiful Paths from top left to bottom right cell modulo 10^9+7.

Constraints:

  • 1 \le T \le 10
  • 1 \le M,N \le 10^2
  • 1 \le A[i][j] \le 30\ \forall\ (i\isin[1,M], j\isin[1,N])

Sample Input:

1
3 2
1 1
3 1
3 1

Sample Output:

2

Explanation:

There are 2 Beautiful Paths

* A[0][0] -> A[0][1] -> A[1][1] -> A[2][1]
* A[0][0] -> A[1][0] -> A[2][0] -> A[2][1]

Please help @galencolin, @ssrivastava990
Not only the above people, anyone can help :slightly_smiling_face:

2

Can anyone please help :pleading_face:

3

in which company this question is asked ? @aryan12 @everule1 please can u share your your thought.

1 Like
4

It was asked in NCR coding test , here is my code which solves the problem :

The basic idea is to use 3-Dimensional-DP/Digit-Dp, maintain 1024 different dp states , and do the transitions.

Only 1024 states are needed for each cell, as there are only 10 primes less than equal to 30, so power(2,10)=1024

Time Complexity : O(N*M*1024)

3 Likes
5

I am actually not aware of the contest in which the question was asked. My friend called me and he dictated me the question and asked me to help him, however neither was able to solve it. I wanted to know the solution of it so I asked it.

6

Can you elaborate the following?

  1. DP States
  2. 3-Dimensional DP table
7

I assume you are well-versed with digit-dynamic-programming , or else it will be hard to decipher what I say .

Say, first prime number is given index 0 , second prime number given index 1, and so on…

So,
x[0]=2 ,
x[1]=3,

…

…

x[9]=29

Now, I want to represent a number with the help of these indices , so ,

let say x = 2^1 * 3^2 * 5^7 ,
so our tuple of 10 values will look like : {1,2,7,0,0,0,0,0,0,0} . This can be called as a state.

A number having odd number of divisors is a perfect square .

So, if a number is perfect square, its prime number representation will have all even powers.

Example of perfect square = 36 = 2^2 * 3^2 , power of 2 and 3 are even.

So dp[i][j][k] means number of paths which reach (i,j) and have dp-state k , by which I mean say , if k=4 , in binary , k=0000000100 , so the number paths whose product have odd power at index “3” , index {3} means prime number 5(mentioned) above.

Final answer after computing the Dp will be dp[n][m][0] , which means all paths having some product which have zero prime numbers having odd powers in their prime reapresentation. I agree the problem is pretty complicated but its cool to brush up digit dp

1 Like
8

Thanks for explaining it patiently. Gotta learn more.

1 Like