PROBLEM LINK:
Author: Anudeep Nekkanti
Tester: Mahbubul Hasan
Editorialist: Jingbo Shang
DIFFICULTY:
Easy-Medium
PREREQUISITES:
Dynamic Programming, Counting
PROBLEM:
How many ordered sequence of N positive numbers such that there are no two numbers whose product is greater than K.
EXPLANATION:
A special case N = 1
You should print -1 which means infinity.
General cases N > 1
First, we need to observe that the constraints here are equivalent to that the product of largest two numbers are not greater than K. Therefore, the second largest one should be no more than sqrt(K).
So, we can enumerate the second largest number, denoted as X (1<=X<=sqrt(K)). Then, we know that there are K / X - X + 1 different choices for the largest one. For the other N - 2 numbers, they should be no more than X. For this part, we can design a dynamic programming algorithm to solve it.
Let F[i][j] as the number of choices that i numbers are selected and they are all no more than j. Initially, F[0][li] = 1. Then, following the loops give the computational ordering:
[/li]
for i = 1 to N:
for j = 1 to sqrt(K):
F[i][j] = (F[i - 1][j] + F[i][j - 1]) % MOD
There are two terms for adding, one is that we take a number j, therefore, from F[i - 1][j]; the other one is that we have no more numbers j, therefore, from F[i][j - 1].
This F array is independent from the input cases, which could be pre-computed.
AUTHOR’S AND TESTER’S SOLUTIONS:
Solutions will be available soon.
Author’s solution can be found here.
Tester’s solution can be found here.