We have to count the numbers up to N(N can be up to 10^17) such that the digits from the smallest possible permutation for example if I take N=13 then the answer would be 12 since 10 is not the smallest permutation of the digits '0' and '1'.
# | User | Rating |
---|---|---|
1 | jiangly | 3640 |
2 | Benq | 3593 |
3 | tourist | 3572 |
4 | orzdevinwang | 3561 |
5 | cnnfls_csy | 3539 |
6 | ecnerwala | 3534 |
7 | Radewoosh | 3532 |
8 | gyh20 | 3447 |
9 | Rebelz | 3409 |
10 | Geothermal | 3408 |
# | User | Contrib. |
---|---|---|
1 | maomao90 | 173 |
2 | adamant | 164 |
3 | awoo | 161 |
4 | TheScrasse | 160 |
5 | nor | 159 |
6 | maroonrk | 156 |
7 | SecondThread | 152 |
8 | pajenegod | 146 |
9 | BledDest | 144 |
10 | Um_nik | 143 |
We have to count the numbers up to N(N can be up to 10^17) such that the digits from the smallest possible permutation for example if I take N=13 then the answer would be 12 since 10 is not the smallest permutation of the digits '0' and '1'.
Name |
---|
i am unable to understand this question can u give some more details to problem.
This problem can be easily solved using recursion, assume the current number is
n
and its the smallest permutation, and thelast digit is d
, then any digit we append in the last must begreater than or equal to d.
It's very easy to understand but still if you have any doubt please reply.Would it perform well on values of N up to 10^17?
Yes I checked, it's running within 1 sec.
bro, this also shows TLE
sad life
I ran it in CF custom invocation and this is the vedict for n = 1e17
We can view this question as the typical problem of counting the number of paths on a grid. Going to the right can be seen as choosing the next digit equal to the previous digit and going up $$$x$$$ cells on the grid represents that the next digit is equal to the previous plus $$$x$$$. The answer will be the total number of ways to reach the right part of the grid (at any height), notice that every path represents a different number whose digits are in non-decreasing order.
Let $$$k$$$ be the largest non-negative number such that $$$10^{k} \leq n$$$, then $$$n$$$ has $$$k + 1$$$ digits. First, we count the number of numbers with the desired property that are less than $$$10^{k}$$$, which for the previous analysis we can represent as the number of different paths on a grid of size $$$10 \times k$$$ (there are $$$k$$$ digits with values between $$$0$$$ and $$$9$$$), also we have to subtract the path representating $$$0$$$.
Then, the answer for that is equal to $$$\binom{k}{0} + \binom{k + 1}{1} + \binom{k + 2}{2} + \dots + \binom{k + 9}{9} - 1 = \binom{k + 10}{9} - 1$$$. If the most significant digit of $$$n$$$ is $$$a_{k + 1}$$$ we add the number of different paths to travel a grid of size $$$(a_{k + 1} - 1) \times (k + 1)$$$ (since the first digit could be anything between $$$1$$$ and $$$a_{k + 1} - 1$$$, note that including numbers with most significant digit equal to $$$a_{k + 1}$$$ would result in a overcount) to the previous result. We continue this way until the digits of $$$n$$$ are not in non-decreasing order (because after this point there won't be more numbers satisfying the conditions), for example if the $$$(k + 2 - i)$$$-th, $$$i \neq k + 1$$$, most significant digit of $$$n$$$ is $$$a_{i}$$$ we add to the answer the number of paths in a $$$(a_{i} - a_{i + 1}) \times i$$$ grid.
Path-counting on a grid is so powerful...