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 | tourist | 3911 |

2 | maroonrk | 3606 |

3 | MiracleFaFa | 3604 |

4 | Benq | 3583 |

5 | Radewoosh | 3545 |

6 | slime | 3486 |

7 | ecnerwala | 3457 |

8 | greenheadstrange | 3430 |

9 | sunset | 3338 |

10 | ksun48 | 3334 |

# | User | Contrib. |
---|---|---|

1 | YouKn0wWho | 213 |

2 | Monogon | 200 |

3 | Um_nik | 192 |

4 | awoo | 187 |

5 | -is-this-fft- | 184 |

6 | sus | 177 |

7 | Errichto | 176 |

8 | antontrygubO_o | 174 |

9 | SecondThread | 167 |

9 | maroonrk | 167 |

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'.

↑

↓

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jan/17/2022 09:37:40 (h1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Auto comment: topic has been updated by himanshu1212 (previous revision, new revision, compare).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 the`last digit is d`

, then any digit we append in the last must be`greater than or equal to d.`

It's very easy to understand but still if you have any doubt please reply.SpoilerWould 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...

bro if you solved this then provide me approach of this problem which dont show TLE