fun.contest.id's blog

A simpler solution to [861-C] Unlucky numbers using binary search
By fun.contest.id, 2 months ago, In English

Problem statement

Here is the Link to the problem

We need to find any number in the range $$$[l, r]$$$ with the least luckiness

Luckiness of a number is defined as the difference between its maximum and minimum digit

So for $$$n = 369$$$ the luckiness will be 9 — 3 = 6

Solution

Basic Idea

So for a number $$$n$$$ let the min and max digit be $$$m$$$ and $$$M$$$ respectively, we need to find n with the least value of $$$M - m$$$

  1. Since we want to minimize this difference, we can iterate over the differences in the range $$$[0, 9]$$$
  2. We can then choose the smallest digit $$$m$$$ for our number in the range $$$[0, 9]$$$
  3. Then, $$$M$$$ = $$$m + diff$$$

So we need to just check if there exists a number in the range $$$[l, r]$$$ such that all its digits are greater than equal to $$$m$$$ and less than equal to $$$M$$$. Also not forgetting that at least one digit must be $$$m$$$ and atleast one digit must be $$$M$$$ to get $$$diff = M - m$$$

Calculation of Predicate function

Lets define $$$count$$$$$$(n, m, M)$$$ as the count of non negative numbers $$$\le n$$$ whose digits lie in the range $$$[m, M]$$$

To find the count function we can iterate over the digits of n.

Say we are the $$$i^{th}$$$ digit from the left where we will have 2 choices

  1. Either to select a digit lesser than $$$d[i]$$$
    • In this case we will have all the options from $$$[m, min(M, d[i] - 1)]$$$
    • Since we have selected a smaller digit remaining positions can be filled by any digit in $$$[m, M]$$$
  2. Or we an simply select $$$d[i]$$$ and look for possibilities in the remaining number

If we see this count will also include those numbers which won't have digits $$$m$$$ and $$$M$$$ together, where all the digits are either in the range $$$[m + 1, M]$$$ or $$$[m, M - 1]$$$.

We need to remove those numbers from our count to get a $$$netCount(n, m, M)$$$ which gives the count of all the numbers which have atleast one digit $$$m$$$ and atleast one digit $$$M$$$ and all remaining digits satisfy the range $$$[m, M]$$$

$$$netCount(n, m, M)$$$ = $$$\ count(n, m, M)$$$ — $$$count(n, m + 1, M)$$$ — $$$count(n, m, M — 1)$$$ + $$$count(n, m + 1, M — 1)$$$

You can try some example cases to get why this thing works.

To check if such a number $$$\ge l$$$ and $$$\le r$$$ exists we can simply check using a predicate function $$$get$$$

$$$get(l, r, m, M)$$$ = $$$netCount(r, m, M)$$$ - $$$netCount(l -1,m, M) > 0$$$

Binary Search Part

After finding the optimal $$$m$$$, $$$M$$$, optimal $$$diff$$$ by iterating over the possible differences in the first part and checking if they satisfy the predicate function, we can use binary search.

Since $$$netCount$$$ is monotone (non decreasing function in our case),

We can find the first number in the range $$$[l, r]$$$ using binary search which satisfies the $$$get$$$ function and this will be our final answer which will have all the digits $$$\ge m$$$ and $$$\le M$$$ and the least difference $$$M-m$$$

With this binary search approach, i think we can even find $$$k^{th}$$$ smallest number with the optimal difference. You can try solving for that task

Here is the accepted submission

Finding kth smallest number with any difference

code which finds minimum number with least difference

code which finds median number with least difference

code which finds largest number with least difference

Thanks for reading my blog, have a great day :)

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

»
2 months ago, # |
  Vote: I like it +8 Vote: I do not like it

well, that`s preaty neat solution, definitely better than mine)) I used 6D dynamic programming approach

→ Reply
»
2 months ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

Interesting. I came up with the BS approach too and finding the kth term for a minimum and maximum digit took me time to arrive at.

I am pretty sure I have seen the concept in some past div 3 / 2 before.

→ Reply
  • »
    »
    2 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Yes if we can somehow calculate count function, we can always use binary search because having more numbers won't decrease count, it will either remain same or increase.

    I remember an interactive problem asked in Atcoder contest where we need to determine the position of a rook with some properties.

    → Reply
»
2 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Why have u used this ?

if(a != 0 and l > 1)
		if(options > 1)
			res += options * (binexp(options, l - 1) - 1) / (options - 1);
		else res += l - 1;
 
if(self) res++;
→ Reply
  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    All the numbers with digits lesser than those of n can be filled in any order with options available $$$[m, M]$$$.

    So we do $$$(options)^{l-1} + (options)^{l - 2} +........ options^{1}$$$

    If you see this is a geometric progression with

    $$$a = options, r = options, cnt = l - 1$$$

    This sum will be equal to

    $$$\displaystyle a\left(\frac{r^{cnt} - 1}{r - 1}\right)$$$

    Just substitute corresponding a,r, cnt in the function. Also we need to handle some cases when l = 0 or r = 1 or minimum_digit = 0

    → Reply
    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Ohh right, understood !!! Just 2 more question.

      1 — for options == 1, why have u added l-1 . All the digits must be same so order should be insignificant

      2 — What is 

      if(self) 
res++;

      used for ?

      → Reply
      • »
        »
        »
        »
        2 months ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        let say $$$n = 123456, a = 2, b = 2$$$, so we have only $$$1$$$ choice i.e placing $$$2$$$ on every position.

        So numbers with $$$5$$$ digits or less will be like $$$22222, 2222, 222, 22, 2$$$. So i added $$$(l - 1)$$$ i.e $$$(6 - 1) = 5$$$ to account for these numbers.

        This thing is nothing but the part of our gp series only, but we cant use $$$(options - 1)$$$ as it will come out to $$$0$$$ and will give us a runtime error.

        So we need to simplify it first and it will come out to be $$$1^{l - 1} + 1^{l-2} +......1^{1} = (l - 1)$$$

        $$$Self$$$ for if the number itself satisfy the properties

        → Reply
        • »
          »
          »
          »
          »
          2 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Now I am clear with each part of the code.

          Thank u for such neat blog and for being patient. Appreciate it

          → Reply
          • »
            »
            »
            »
            »
            »
            2 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Thanks bro, i am glad you understood and it helped you :)

            → Reply
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it 
Either to select a digit lesser than d[i]
In this case we will have all the options from [m, min(M, d[i] - 1)]
Since we have selected a smaller digit remaining positions can be filled by any digit in [m, M]

With numbers with the number of digits less than n starting with the digit 0, how do you handle it?

→ Reply
»
2 months ago, # |
  Vote: I like it +1 Vote: I do not like it

This solution is actually incredibly smart!

→ Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Your solution is witty and artistic. There were numerous base cases which I couldn't think of while analyzing the problem and your code and this post mentions them clearly. The algorithm for count function is genius. Thank you for the blog.

→ Reply