I want to provide a hint for people who are still trying to wrap their head around the problem. One advanced book that is on topic is, "Combinatorial Algorithms", by Kreher and Stinson.

My breakthrough happened when I printed out a few tables. Given a function that converts decibinary to its decimal value, the 1 digit numbers have their obvious decimal values. I recommend printing tables of decibinary numbers in groups of 10, then you will start seeing a pattern.

In python, this might look like,

>>> [ db_value(x) for x in range(0,10) ]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> [ db_value(x) for x in range(10,20) ]
[2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
>>> [ db_value(x) for x in range(20,30) ]
[4, 5, 6, 7, 8, 9, 10, 11, 12, 13]
>>> [ db_value(x) for x in range(90,100) ]
[18, 19, 20, 21, 22, 23, 24, 25, 26, 27]
>>> [ db_value(x) for x in range(100,110) ]
[4, 5, 6, 7, 8, 9, 10, 11, 12, 13]

Example tests:

2
1104
1963

result:

11111 (31 in decibinary)
10406 (38 written in decibinary)

I could not able to understand the question plz help me to undestand the question.

C++ solution which is logically the same as the one posted previously but hopefully a little easier to understand.

const int dmax = 300000;
const int digits = 10;
const int powers = 20;

vector<vector<long>> v(dmax, vector<long>(powers));
vector<long> c(dmax);

// Complete the decibinaryNumbers function below.
void preCompute() {
  // Compute the number of duplicates for each value, number of digits.
  for (int i = 0; i < dmax; i++) {
    v[i][0] = i < digits;

    for (int j = 1; j < powers; j++) {
      // Duplicates is sum of all shorter numbers duplicates for each digit.
      for (int k = 0; k < digits; k++) {
        int value = i - k * (1 << j);

        // Exit if using digit creates number larger than target value.
        if (value < 0)
          break;
        v[i][j] += v[value][j - 1];
      }
    }
  }

  // Calculate the absolute offset for the first duplicate of each number.
  for (int i = 1; i < dmax; i++) {
    c[i] = v[i - 1][powers - 1] + c[i - 1];
  }
}

long decibinaryNumbers(long x) {
  long result = 0;
  auto l = upper_bound(c.begin(), c.end(), x - 1) - 1;
  int value = l - c.begin();
  long offset = (x - 1) - *l;

  // Find each digit.
  for (int i = powers - 1; i >= 1; i--) {
    int power = 1 << i;

    // Find the digit which takes us closest to offset.
    for (int digit = 0; digit < digits; digit++) {
      // Calculate value of remaining digits.
      int v1 = value - digit * power;

      // If index is less than duplicates for remainder we have our digit.
      if (offset < v[v1][i - 1]) {
        result += digit;
        value -= power * digit;
        break;
      }

      // Subtract number of duplicates for this digit from offset.
      offset -= v[v1][i - 1];
    }

    result *= 10;
  }

  // Whatever is left must be the last digit.
  result += value;
  // cout << x << ":" << result << ":" << l - c.begin() << endl;

  return result;
}

I've read the problem a lot of times, but I wasn't able to understand this challenge. According to me, explications and examples are not enough.

Anyone passed test case 7 & 8 with python3?

I don't understand how x = 20 is 110.

x = 11 bidecimal = 5, x = 12 bidecimal = 13, x = 13 bidecimal = 21, x = 14 bidecimal = 101, x = 15 bidecimal = 6, x = 16 bidecimal = 14, x = 17 bidecimal = 22, x = 18 bidecimal = 102, x = 19 bidecimal = 110

Which one am I missing?

My submission is getting a wrong answer on Test Case 3. My list of decibinary numbers appears to be shorter than the expected, because the decibinary number at index 'x' in my list is smaller than the expected decibinary number. Any feedback would be appreciated:

public static long decibinaryNumbers(long x)
{
    long idx = x - 1;
    int n = 0;
    long count = 0;
    while (true)
    {
        List<long> repsForN = generateAllDbReps(n);
        if (idx >= count && idx < count + repsForN.Count)
        {
            return repsForN[(int)(idx - count)];
        }
        count += repsForN.Count;
        n++;
    }
}

public static List<long> generateAllDbReps(int n)
{
    List<long> result = new List<long>();
    if (n == 0)
    {
        result.Add(0);
        return result;
    }

    int place = (int)Math.Floor(Math.Log(n, 2));
    long dbNum = 0;
    internalGenerateAllDbReps(n, place, dbNum, result);
    return result;
}

private static void internalGenerateAllDbReps(long n, int place, long dbNum, List<long> result)
{
    if (n == 0)
    {
        result.Add(dbNum);
        return;
    }

    if (place < 0)
    {
        return;
    }

    long pp2 = (long)Math.Pow(2, place);
    long maxDigit = n / pp2;
    if (maxDigit > 9)
    {
        return;
    }

    long pp10 = (long)Math.Pow(10, place);
    for (int digit = 0; digit <= maxDigit; digit++)
    {
        internalGenerateAllDbReps(n - (digit * pp2), place-1, dbNum + (digit * pp10), result);
    }
}

How is the 20th decibinary number 110? I guess it has to be 7. Am i missing something here?

This was an interesting problem, until the end. My solution wasn't fast enough for the last data set. I forfeited points to read the editorial and found that my solution was equivalent to the problem setter's, even more optimized. (I tried both filling up dp at the beginning and also using it for memoization w/ recursion; former was faster in PHP.)

PHP is just too slow for this one. I got 48/60 with PHP, which is the best for PHP on the leaderboard.