OA Question || Need Help

Count number of sequences of length n whose every adjacent elements product is less than or equal to p.
n <= 100
1 <= p <= 1e9

p=3 , n=2
ans = 5
(1,1) , (1,2) , (2,1) , (1,3) , (3,1)

Other testcases

p=10, n=2
ans = 27

p=1, n=5
ans = 1

p=4, n=4
ans = 47

A key observation in this problem is that for any two adjacent numbers, one of them must be less than or equal to \sqrt{p}.

Then dynamic programming can be used. The state design is as follows. Let dp(i,j,f) denote the current i-th position from left to right, f=0 when the number in this position is j, while f=1 when the number in this position is in the interval (\lfloor\frac{n}{j+1}\rfloor,\lfloor\frac{n}{j}\rfloor]. It follows that j is about \sqrt{p}, and so the number of states is O(n\sqrt{p}).

As for the equation is slightly more complicated, each time to transfer from the previous position of a section of the interval, the also need to maintain each i corresponding to \sum_j dp(i,j,p), that is, the prefix sum.

Time Complexity: O(n \sqrt{p})

1 Like