PROBLEM LINKS
DIFFICULTY
MEDIUM
EXPLANATION
Please, before reading this article read some tutorials about dynamic programming, like this one: http://www.codechef.com/wiki/tutorial-dynamic-programming
This problem is the unification of some trivial DP problems (dynamic programming) and problem ‘find somthing k-th’.
In problems like this, when you need to find k-th lexicographically minimal sequence, it is useful to notice that if we at each step (i. e. at each position starting from 0 to n-1) will always choose the minimal possible integer at that position, here ‘possible’ means that if we place at some position some integer it must be possible to place the rest of positions (without violating the rules described in the statement).
Imagine that we are on position i. All numbers before i-th are already placed in array R. We need to find k-th minimal correct suffix of size n-i. The question is what number we should place on i-th position. The answer is that it must be the minimal positive integer x not greater than m and for which Count(x-1, mask) < k. mask is a set (array or bitmask) of possible values of F(x) that can be placed on i-th position (if i = 0 it is any integer, if C[i-1] = 1 it is only F(R[i-1]) and if C[i-1] = 0 it is any integer except F(R[i-1])). Now what is Count(x, mask)? It is the number of valid suffixes of last n-i positions if at first position of that suffix (i. e. i-th position in total array) we place integer not greater then x. Imagine now that we have such function done. How to quickly find x? Of course, you can use binary search in this case, because function Count will be non-decreasing with increasing of x. And the last note in this section: when you will have x, dont forget to subtract Count(x-1, mask) from k, because all number from 1 to x-1 will lead to lesser sequences.
The description of Count function is at the end because we need several additional functions.
Let LuckyCount(x, num) will be the number of such integers a (1 <= a <= x) that F(a) = num. It can be calculated with trivial DP with states [pos][less][cnt], here pos is the position of digit in decimal representation of x, less = 0 if current prefix is lesser than corresponding prefix in x and 1 if it is equal, cnt - the number of lucky digits in current prefix. If we are in state [pos][less][cnt] we can iterate through all digits d from 0 to 9 (inclusive) and try to place it on the next position in prefix. If we find transitive state [pos’][less’][cnt’] for any digit then we just do DP[pos’][less’][cnt’] += DP[pos][less][cnt], where DP is or dynamic programming array. Of course, pos’ = pos+1, because we are adding single digit. If less = 0 then less’ is also 0, because if our prefix is already less than corresponding prefix in x it doesn’t matter what digit we will place to the right, if less = 1 and d < x[pos] then less’ = 0, if less = 1 and d = x[pos] then less’ = 1, otherwise, if less = 1 and d > x[pos] then we cant use digit d (the prefix will be greater than corresponding prefix in x), here x[pos] is pos-th digit of decimal representation of x (strarting from the rightmost digit). cnt’ = cnt if d is not equal 4 or 7, otherwise it is cnt+1. The return value for function, of course, will be DP[size(x)][0][num] + DP size(x)[num], where size(x) is the size of decimal representation of x. Note that the strating state of DP, the sate DP0[0] equals to 1.
Let SuffixCount(len, last) will be the number of valid placements of last len numbers (in this case we can place any numbers from 1 to m, inclusive at that positions) of our array considering that the first number at position n-len has the number of lucky digits equal to last. Calculating this DP we should keep track on values of array C. Imagine that we are in the state [len][last]. As transitions we iterate through all possible values next of function F for the next number to the left (i. e. at position n-len-1), which will not be greater than 9 and doing DP[len+1][next] += DP[len][last]*LuckyCount(m, next). But note that if C[n-len-1] is 1 then next may be only the same as last, otherwise it should not be equal to last. The return is just DP[len][last]. DP[0][0] = 1.
And now the last function Count(x, mask). Iterate through all possible values of F we can place at i-th position, i. e. numbers in mask (generally it will not increase 9 because it is impossible to place more than 9 lucky digits in any number not greater than 10^9), let it be integer f. We know that the number of such number not greater than x and with the number of lucky digits equal to f is LuckyCount(x, f). Then the number of valid suffixes with F(R[i]) equal to f is *LuckyCount(x, f)SuffixCount(n-i-1, g) for all valid g (depending on C[i]). The sum of such values for all f in mask will be the result for Count function.
Also please note that in this problem you need a lot of memoization, i. e. you need to save your results in different DP states in order to get green Accepted
SETTER’S SOLUTION
Can be found here.
TESTER’S SOLUTION
Can be found here.