skywalkert's blog

By skywalkert, 5 weeks ago, In English,

This is a problem I met on a Chinese online judge six years ago.

I'm not sure if it is a problem from another place.

It's SGU 420 -- Number Permutations from 2007-2008 Summer Petrozavodsk Camp, Petr Mitrichev Contest 3. (Thanks to Claris.)

Here's the problem:

Two different positive integers are considered similar if the numbers of their digits are the same, and the multisets of their digits are the same as well.

Given integers $$$l$$$ and $$$r$$$, count the number of integers $$$x$$$ ($$$l \leq x \leq r$$$) such that there is exactly one integer $$$y$$$ ($$$l \leq y \leq r$$$, $$$x \neq y$$$) satisfying that $$$x$$$ and $$$y$$$ are similar.

$$$1 \leq l \leq r \leq 10^{15}$$$

A few random examples of similar numbers:

  • 6892, 6928, 6982, 8269 are similar
  • 5986656, 5986665, 6556689, 6556698 are similar
  • 2983321011, 2983321101, 2983321110, 3011122389 are similar
  • 797776555322101, 797776555322110, 901122355567777, 901122355576777 are similar

UPD: I've solved this problem. I'll soon elaborate my solution in the comment.

 
 
 
 
  • Vote: I like it
  • +20
  • Vote: I do not like it

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

What is the meaning of the first constraint "numbers of their digits are the same"? It seems redundant given the multiset condition.

  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Yes, it's redundant. Probably the statement wants to emphasize that $$$x$$$ and $$$y$$$ both have no leading zeros.

»
5 weeks ago, # |
Rev. 3   Vote: I like it +20 Vote: I do not like it

Let $$$next(x)$$$ be the number $$$y$$$ whose digits are the next lexicographically-ordered permutation of digits of $$$x$$$. In case $$$y$$$ doesn't exist, let $$$next(x)$$$ be $$$\infty$$$.

Let $$$prev(y)$$$ be the number $$$x$$$ whose digits are the previous lexicographically-ordered permutation of digits of $$$y$$$. In case $$$x$$$ doesn't exist or $$$x$$$ contains leading zeros, let $$$prev(y)$$$ be $$$-\infty$$$.

It is equivalent to count the pairs of $$$(x, y)$$$ such that $$$next(x) = y$$$ and $$$prev(x) < l \leq x < y \leq r < next(y)$$$. Obviously, the answer is twice its number.


Let's take a look at the algorithm (in linear time complexity) to find the next permutation of an array $$$a_1, a_2, \ldots, a_m$$$:

  • First, we need to find the rightmost $$$i$$$ such that $$$i < m$$$, $$$a_i < a_{i + 1}$$$. If no such $$$i$$$, no permutation is greater than the array, since $$$a_1, a_2, \ldots, a_m$$$ are in non-increasing order.
  • Then, we need to find the rightmost $$$j$$$ such that $$$i < j$$$, $$$a_i < a_j$$$. It always exists since $$$a_i < a_{i + 1}$$$.
  • Finally, we need to swap $$$a_i$$$ and $$$a_j$$$, and then reverse the elements $$$a_{i + 1}, a_{i + 2}, \ldots, a_m$$$.

For example, $$$12\color{red}{3}\color{blue}{4} \to 12\color{blue}{4}\color{red}{3}$$$, $$$\color{red}{1}\color{blue}{2}11 \to \color{blue}{2}11\color{red}{1}$$$ and $$$\color{red}{5}9866\color{blue}{6}5 \to \color{blue}{6}5\color{red}{5}6689$$$.

When we care about at most $$$4$$$ adjacent permutations of digits, those digits that are useful for the algorithm of finding next permutation must be in the lowest $$$3$$$ non-increasing blocks, for instance, $$$\color{red}{7}\color{green}{9777655532210}\color{blue}{1}, \color{red}{7}\color{blue}{97776555322110}, 9011223555\color{red}{6}\color{blue}{7777}, 9011223555\color{red}{76}\color{blue}{777}$$$. But actually, do we really need to care about maybe a huge number of situtations? No.


In most cases, the difference between integers corresponding to $$$2$$$ adjacent permutations is quite small, such as $$$(6556689, 6556698)$$$ and $$$(797776555322101, 797776555322110)$$$. It is because the lowest non-decreasing block is long enough, and we can only consider them when finding the next permutation.

The case that the difference between two adjacent similar integers $$$x, y$$$ is large is when the lower integer has a long non-increasing block. But in that case, the next similar integer $$$z$$$ usually comes with a fairly small difference of $$$(z - y)$$$.

It inspires that, in most cases, we can enumerate $$$(prev(x), x)$$$ or $$$(y, next(y))$$$, such that the difference of those two is small enough. The reason we only enumerate these two kinds but $$$(x, y)$$$ is that no matter in which of those two cases, we know $$$x$$$ or $$$y$$$ is close to $$$l$$$ or $$$r$$$.

In case that $$$prev(x) = -\infty$$$ and $$$next(y) = \infty$$$, we can conclude $$$12 \leq x < y \leq 98$$$, since $$$x$$$ must have at least two types of digits, and thus the number of all possible permutations of its digits is no less than its length. Since the difference is small, this situation can be enumerated by the above method, so we can avoid discussing it.

In case that $$$prev(x) = -\infty$$$, the digits of $$$x$$$ is in non-decreasing order, which implies the difference $$$(prev(y) - y)$$$ may be considerable. So as for $$$next(y) = \infty$$$.

Let's assume that we have handled all the cases with differences less than $$$10^3$$$. What are the rest cases? You may observe that the rest case is only like $$$(677777, 767777)$$$ and $$$(676666, 667666)$$$. Why? Because if the lowest $$$3$$$ digits are not the same, it will form many permutations and be enumerated in the above. Hence, we can enumerate the lowest digits in the form of $$$(p q q \ldots q, q p q \ldots q)$$$, $$$(p q p \ldots p, q p p \ldots p)$$$, and determine if they could form an interval that covers $$$l$$$ or $$$r$$$.


In summary:

  • For covering most cases, we enumerate the numbers that are close to the endpoints of $$$[l, r]$$$ and forcibly check if they can be included in the answer.
  • For covering the rest cases, we enumerate the possible suffix digits of $$$x$$$ or $$$y$$$ (i.e. $$$p$$$, $$$q$$$ and the length of the lowest same digits), and forcibly check again.

Time complexity: $$$\mathcal{O}(D^3 L + D^2 L^2)$$$, where $$$D = 10$$$ is the number of possible digits, $$$L = 15$$$ is the maximal length of a number.