pratyushk82010's blog

DP problem from NCR online coding round held on 3rd October
By pratyushk82010, history, 4 years ago, In English

Here is a DP problem on which I have struggled really bad but in vain. Hence, I would really appreciate you guys to help me out.

Problem : You are given a 2-D grid of n*m dimensions. You are requested to print the number of unique paths from top-left corner to the bottom-right corner such that the product of all the values in the path contains odd numbers of divisors. For each cell you can either move to right or down.

Input: n, m Output: Print a single integer denoting number of unique paths from top-left to bottom-right corner such that the product of all values in the path contains odd number of divisors. Print answer modulo 1e9 + 7.

Constraints: 1 <= n, m <= 100 value[i, j] <= 30

Example: Input: n = 3, m = 2

grid:  1 1
           3 1
           3 1 

      Output: 2

Explanation: Here are 2 unique paths: 1-> 3-> 3-> 1, Product = 9, Number of divisors of 9 are 1, 3, 9 which is odd. 1-> 1-> 1-> 1, Product = 1, Number of divisors of 1 is only 1 only, which is odd.

Tags #dp
  • Vote: I like it
  • -9
  • Vote: I do not like it

Comments Comments (7)
| Write comment?
»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it
Sample Code
→ Reply
  • »
    »
    13 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you please explain your approach?

    → Reply
    • »
      »
      »
      13 months ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Hey I've not done the problem myself but let me just talk about my idea real quick. If a number has odd number of divisors, the number would be a square number. So we can do something like bitmask since the value is small.

      Make a prime list for every prime $$$\leq 30$$$. Then let $$$dp_{i,j,k}$$$ to be the number of paths to reach cell $$$(i,j)$$$ with a bitmask $$$k$$$ where if a bit in $$$k$$$ is on, it means that the prime number's occurence would be odd. The transitions are obvious. Answer will be $$$dp_{n,m,0}$$$ because the every prime should appear even for a square number.

      → Reply
      • »
        »
        »
        »
        13 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I am not able to understand the transitions. Can you please explain the transitions (in great detail if possible)?

        → Reply
        • »
          »
          »
          »
          »
          13 months ago, # ^ |
          ← Rev. 3   Vote: I like it 0 Vote: I do not like it
          $$$ a=\prod prime_i^{a_i} \\ b=\prod prime_i^{b_i} \\ a*b= \prod prime_i^{a_i+b_i} $$$

          Since we only need to know if its even/odd => ai+bi = ai ^ bi

          → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it
My accepted code
→ Reply