I have found a solution but not fully sure about it.

First of all if X < l then the answer is zero. And i must be <= L where L = min(r, X). Now let’s solve the problem for range (0, L). Let's Len = number of digits in L. Now we can divide the solution in two parts.

In the first part, for each k (1 <= k < Len) we'll try to find the number of valid i which has k digit in it's representation. We can do this easily because if i <= X then rev(i) <= will also hold. As total number of digits is smaller. So we can just ignore that rev(i) <= X condition for this part.

Let's sum1 is the summation of result for each k (1 <= k < Len). Now each of the number x in sum1 will contribute to the final result twice. Because for each x we can add some trailing zeroes in x to make it a Len digit number. As we are adding some trailing zeroes the conditions i <= X and rev(i) <= X will still hold.

Now we’ll solve the second part where we need to find the number of Len digit number which has no leading or trailing zeroes. I'll explain this with an example. Let's L = 372967524. Let's divide this L into 3 parts. P1 = 372, P2 = 9, P3 = 67524. Here P2 has only one digit.

Let's build a number i whose first 3 digit is fixed (same as P1). And at the 4th position we place a smaller digit than P2 (for example 8). So i now looks like this 3 7 2 8 _ _ _ _ _. So i has already become less than X. It doesn't matter what we place in the remaining 5 positions. Condition i <= X will always satisfy. So now we focus on selecting 5 digits for the remaining position such that rev(i) <= X satisfy.

The reverse of the trailing 5 digits of i is actually the 5 leading digits of rev(i). As we don't need to worry about i <= L condition any more, so now we'll do digit DP to find this first 5 leading digits of rev(i), comparing to the first 5 digits in X. We need to handle one more case here. As we have already placed the leading 4 digits in i whose reverse is actually the trailing 4 digits of rev(i), so after choosing the leading 5 digits in rev(i) we just need to check if the whole rev(i) satisfy the condition (<= X) or not.

As i said above, we’ll have to divide L in 3 parts. For each digit in L we’ll select it as P2. And the remaining two parts as P1 and P2. Then we repeat the same approach each time. The summation of all these results(including the one in part1) is our final answer.

Nice problem. Thank you :)

Beautiful problem! I used digit dp, bitmask, binary search- all in 1 problem!!

Solved it. A very nice problem. Thanks Vai :)

The maximum length of LIDS can be at max 10. So we can check for each length k, in how many ways we can make a number whose LIDS is k. We can then print the result we found for the maximum k.

I’m describing the states we need to find the number of ways we can build an LIDS of length k.

1. At which position we are.

2. Has the sequence already become less than y? (0 or 1)

3. Has the sequence already become greater than x? (0 or 1)

4. Did we place at least one non zero digit so far? (To handle the first digit of LIDS)

5. Last digit we have placed in the sequence.

6. Number of total digit in the LIDS sequence.

Basically we build two sequence parallelly. One is definitely the whole sequence, another one is the LIDS sequence (Which is the sub sequence of the original sequence). When ever we select a digit we want to place, it becomes the last digit of the original sequence till now. But we can also choose if we want to consider that digit in our LIDS sequence or not.

Here is the solution to LIDS problem using 3 flags for people who are looking for it.

const int N=11;
ll dp[N][N][N][2][2][2];
string a,b;
/*counts no. of subsequence of len==need using 
 remaining suffix starting with lastDigit set at (pos-1) + 3 flags*/
ll count(int pos,int lastDigit,int need,int flagA,int flagB,int flagZero)
{
        if(pos==b.size())
                return need==0;
        if(dp[pos][lastDigit+1][need][flagA][flagB][flagZero]!=-1)
                return dp[pos][lastDigit+1][need][flagA][flagB][flagZero];
        int l,r;
        if(flagA)
                l=0;
        else l=a[pos]-'0';
        if(flagB)
                r=9;
        else r=b[pos]-'0';
        ll res=0;
        for(int i=l;i<=r;i++)
        {
                res+=count(pos+1,lastDigit,need,flagA||i>l,flagB||i<r,flagZero||i);
                if(i>lastDigit && need && (flagZero || i))
                        res+=count(pos+1,i,need-1,flagA||i>l,flagB||i<r,flagZero||i);
        }
        return dp[pos][lastDigit+1][need][flagA][flagB][flagZero]=res;
}
void solve()
{
        int x,y;
        cin>>x>>y;
        a.clear(),b.clear();
        while(y)
        {
                b.pb(y%10+'0');
                y/=10;
        }
        while(x || a.length()!=b.length())
        {
                a.pb(x%10+'0');
                x/=10;
        }
        reverse(all(a)),reverse(all(b));
        for(int len=10;len>=1;len--)
        {
                memset(dp,-1,sizeof(dp));
                if(count(0,-1,len,0,0,0))
                {
                        cout<<len<<" "<<count(0,-1,len,0,0,0)<<endl;
                        return;
                }
        }
}

Initially we have the space of all numbers S = {0, 1, 2, 3, ..., 10¹⁷}.
This space is too big, so we want to reduce it.
From all that space we only need to consider the numbers with a special property (being palindrome) P ⊂ S.

Now let's consider another space where all of our original numbers are mapped into a different number S₂ = {f(0), f(1), f(2), f(3), ..., f(10¹⁷)}.

There is no point in cosidering this new space S₂ instead of original S if it has the same size.
Can you think of any mapping f: S⟶S₂ that will make the size of S₂ manageable?

I didn't solve them all but here goes my order

• Investigation

• Sum of Digits

• Digit Sum

• Bomb

• Ra-One Numbers

• LUCIFER Number

• G-One Numbers

• Digit Count

• Round Numbers

• Fast Bit Calculations

• Magic Numbers

• Maximum Product

  If you need help then you can look at this.

Take a look

yes

It was the simplest problem of DIGIT DP.

Yes, you are correct. 005 means 5 and 050 means 50. So the way i have written my code, it'll consider all the numbers <= N including the ones whose number of digits is less than the number of digits in N. So it'll work perfectly.

But when d = 0, my given code will produce an incorrect output. Because it'll count zero for the numbers who have leading zeroes. For example, for the number 005, it'll count zero two times. Which is wrong. Because we don't consider the leading zeroes in the decimal numbers. You have to handle this case separately.

How can we do that? We can use another boolean state, which will keep track if we have placed at least one non zero digits so far. If it's true in any state, then we'll count the zero in that state. Otherwise, we don't. Hope it helps you to understand.

just think about , what could be maximum sum of digits & does the value of k matters if it's greater than the sum of digits ?

It May Help you

Hello! There is a very detailed tutorial for this problem on Codechef. If you have further questions, feel free to ask(I was the setter).

dp[index][last_digit_placed][flag]

Can you send the problem link? I want to try my idea.

Based on just what you have mentioned, I have a sketch of a solution. Here

I'm curious whether this is correct. It could require some tweaks, as for case when d = 0, It also counts the leading zeros.

someguy you initialized 'tight' with 0 instead of 1 in your dp function!

That is the actually question asking for.

How many numbers x are there in the range a to b, where the digit d occurs exactly k times in x ?