PROBLEM LINKS
DIFFICULTY
MEDIUM
EXPLANATION
At first, we use Dynamic Programming (DP) to solve the problem of counting number of PDSnums which are not greater than X, called F(X). To do this, we come over each possible digits-sum, then use a DP function G(L, S, P) which is number of PDSnums having length of L, digits-sum of S and digits-product of P. Make it a little bit more details so you could easily solve it. Then, we pre-calculate results of all possible functions G to support the main calculation. The main part, we just use binary search to find the smallest X satisfying F(X) = N and output such that X.
Setter’s comments:
The simplest solution to calculate G function is:
- Parse X to string A of length L,
- Choose respective possible sum of digits - D to calculate G function,
- With a chosen sum D, let G(i, k, s, p) be number of PDSnums which is constructed from position i (from left); k = true/false whether constructed part [1…i - 1] is less than part of A[1…i-1] of not; sum of digits is s & product of digits is p.
- To calculate G(i, k, s, p), we consider: which digit used to build the i-th digit, foreach we calculate the new DP status (i’, k’, s’, p’) with i’ = i+1; k’ = (k’ || chosen digit < A[i]); s = s + chosen digit and p = p * chosen digit.
Take some simple optimization: there is just around 40 possible sums of digits; just store p by remainder when dividing it to D… and some more than you will get the suitable running time.
SETTER’S SOLUTION
Can be found here.
TESTER’S SOLUTION
Can be found here.