ARRANGE2 - Editorial

PROBLEM LINKS

Practice
Contest

DIFFICULTY

HARD

EXPLANATION

One solution is to precompute such valid numbers and store them in the solution. However, there are too many of them to store. The next step is to observe that most numbers actually have the same digits, but just differently arranged. Thus, we just precompute unique digit sequences such that permutations of these digits give valid numbers. There are only 13 such sequences. Precomputation shouldnt take too long (takes around 3 minutes for me).

Now, we start by generating all valid numbers. For each of these 13 sequences, we consider all permutations of them and check which ones are valid numbers. There are around 56000 of them. Now, each query can be answered in logarithmic time by sorting this array of valid numbers and performing binary search to see how many numbers in this sequence are in the range A…B.

1 Like

It would be great help if you can throw some more light on this:

most numbers actually have the same
digits, but just differently arranged.
Thus, we just precompute unique digit
sequences such that permutations of
these digits give valid numbers.

I am unable to understand the unique digit sequences you are talking about…An example would be great