yes @vijju123 i mean that
I think they might be there. Will have a look.
could you please elaborate more on what exactly is the role of the E_{next} and E parameter in the dp table?
Moreover, please correct me if i am wrong but, is UL same as R and is x the number under consideration?
We broke down query into 2 parts right? One for calculating answer for upto R, and then upto L-1. UL is the appropriate upper bound, i.e. either R or L-1 (or L - depending on your implementation) depending on our need. Basically UL is the upper bound for which we are calculating answer.
E basically tells if "After placing this digit, is my number equal to UL at indices [0,i] " or more simply, "Are all digits in range [0,i] in my current number same as that of UL".
E_{next} tells the same for (i+1) if we place the digit d there. You may refer to setter’s solution.
1 Like
My solution is kind of different,
Consider r = 1234 then I just calculated the loss for r 0011,0110,1100,0022,0220,2200,…,0990,9900. Add it up! Similarly for
l - 1. Subtract the loss of digits from the sum of integers
between l and r.
https://www.codechef.com/viewsolution/25844511
1 Like
I thought I am the only dumb who found out a pattern after scratching my head for whole day.
1 Like
Suppose we have a number 5821
Now we need to calculate the sum of all f(x) 0<=x<= 5821
Now string Processing approach
At every index we will find three parts sum_first,sum_second ,sum_third.
variable part_10 is appropriate power of 10 at every index.
The basic approach is to find all the occurrences of a particular number at a particular place
And simply multiply the number with its respective power and occurrences and add that to the final sum.
Sum_first
_ _ _ _ _ at 4th position
For numbers 0 to 4 then other positions can have 10 digits except the one just after the place we are at as it can have only 9 digits
Therefore calculate an initial multiplier and modify it at every iteration.
void Calculate_initial_multiplier()
{
int length = S.length();
int i = 2;
int r = length-2;
while(r>0)
{
multiplier_1 += ((((S[length-1-i]-'0')*part_10)%modulo)*9)%modulo ;
multiplier_1 = multiplier_1%modulo;
part_10 = (part_10*10)%modulo ;
i++;
r--;
}
part_10 = 1;
}
And then multiply the multiplier_1 with 45(sum of all digits from 0 to 9)
Sum_second
Is calculated for the cases when we have the final digits at the positions It has few case in it
As the place we are on the number should not be greater than S[i] (String S).
58_ _
int Calculate_sum_second(int index)
{
int sum_second = 0;
if(index == 0)
return 0;
int num1 = S[index-1] - '0';
int n = S[index] - '0';
int part_1 = 0;
int part_2 = 0;
if(num1 > 0 )
{
part_1 += num1*(45 - ((num1-1)*num1/2));
// deb(part_1);
part_1 += (num1 - 1)*((num1-1)*num1/2);
// deb(part_1);
}
if(n >0)
{
part_2 = n*(n-1)/2;
if(num1 <= n-1)
part_2 = part_2 - num1;
}
sum_second = ((((part_1 + part_2 )*part_10)%modulo)*part_10)%modulo;
// deb(sum_second);
return (sum_second%modulo);
}
Sum_third
It is for the case when we have 582_ that is S[i] at ith index
Now we need to count the total occurrence of S[i] at ith index called as multiplier_3 in the code
int Calculate_sum_third(int index)
{
int sum_third = 0;
sum_third = (((multiplier_sum_third*(S[index]-'0'))%modulo)*part_10)%modulo;
if(index != 0 && ( (S[index-1] - '0') == (S[index] - '0') ) )
{
sum_third = 0;
}
multiplier_sum_third += (((S[index]-'0')*part_10)%modulo);
multiplier_sum_third = (multiplier_sum_third%modulo);
// deb(sum_third)
return sum_third%modulo;
}
Keep updating multiplier_1 and multiplier_3 at every index
And part_10 as
Part_10 = (part_10*10)%modulo
I am deliberately leaving the part of counting ways as it will be a good exercise to figure out yourself
Thank you for reading.
Had to spent a day too ravaging through all the 10k inputs I got from brute force 
1 Like
You know i read every solution and i still not get it. I m a newbie here, and to be honest these codes are looking monstrous to me.
Wow. This is the first time I am hearing of ‘Digit DP’ 
. It’s dissapointing when you find out that the solution is rather simple. I spent almost two days coming up with a solution.
Still, this is how this is my approach :
I decomposed the query into multiple queries, similar to what the other users have done.
1.) There is a pattern in the number of occurence of digits in 1’s place, 10’s place, and so on for numbers in the range(10^k to 10^(k+1) - 1). Using this, I was able to derive a formula that calculates the sum of numbers from 1 to (10^k - 1) in constant time.
2.) We can calculate the sum from 10^(n - 1) to x where x is n digits long. This can be done in O(n) time. I will explain this part using an example :
Let’s say that I need to calculate the sum from 1000 to 3425. I will split this operation into 4 parts.
- 1000 - 2999 :
a = (1 + 2)1000 (Only considering thousand’s place)
Since each digit in thousands place is repeated 1000 times, a = a1000
b = 2*(sum of range 1 to 999)
c = 100 + 200 (We will subtract c from the final answer to eliminate the duplicate digits)
Since 1 occurs 100 times in the hundred’s place in 1000-1999 & 2 occurs 100 times in the hundred’s place in 2000-2999, c = c*100
The final answer for this will be ans = a + b - c- 3000 - 3399 :
a = (30 + 31 + 32 + 33)100 (Considering thousand’s & hundred’s place)
Since each digit is repeated 100 times, a = a100
b = 2*(sum of range 1 to 99)
c = (10 + 20 + 30)*10 (Subtract numbers whose hundred and ten’s digit are same)- 3400 - 3419 :
a = (340 + 341)10 (Considering thousand’s, hundred’s & tens place)
Since each digit is repeated 10 times, a = a10
b = 2*(sum of range 1 to 9)
c = (1)*1 (Subtract numbers whose tens and ones digits are same)- 3420 - 3429 :
For the last digit, simply find ∑ from f(3420) to f(3429)
Add the results from these four parts to get the final answer.
Using this approach I was able to write a solution that runs in just 0.04 seconds 
This is my solution : https://codechef.com/viewsolution/25900241
2 Likes
Why is it disappointing if the editorialist can explain the stuff as if its simple?
I feel you bro. Its not easy to grasp the editorial if you are not well versed with the pre-requisites. How far in general DP are you ? Like, did you look at classical problems like LIS, LCS etc?
1 Like
My solution is very much similar to the one in the editorial, but I don’t know why it gets TLE for some test cases of the last subtask. Can you please look into this solution and say what optimizations were needed to pass all the test cases.
Link to my solution : My solution
I think you should try going iterative. Recursion in JAVA and Python, unlike C++, are very much more expensive. I remember earlier a recursion depth of 10^6 used to give RE:NZEC in JAVA. Point is, its possible that recursion is being expensive here - we can get a clear picture once we see iterative solution.
2 Likes
yep, i know lcs ,edit distance and 2 or 3 more. But I just learned it past month.
Thats why I guess. The editorial will make much more sense when you delve a bit more into dp, like what are states , recurrences - and what possible states to keep track of in a problem and why. Basically at a level when you are able to grasp that what things you need to keep track of in your dp.
2 Likes
Long journey ahead i guess. Thanks
1 Like
your solution is same as mine!!
1 Like
It’s disappointing because the editorial solution is simple and easy to implement, compared to my solution. I’m disappointed in myself for not coming up with a clean solution like yours. That’s all 
1 Like