ENCODING - Editorial

editorial
, , , , ,
30

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.:face_with_thermometer::face_with_head_bandage:

31

Wow. This is the first time I am hearing of ‘Digit DP’ :sweat_smile:. 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 = a    1000
    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 = a    100
    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 = a    10
    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 :upside_down_face:
This is my solution : https://codechef.com/viewsolution/25900241

2 Likes
32

Why is it disappointing if the editorialist can explain the stuff as if its simple? :stuck_out_tongue:

33

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
34

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

35

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
36

yep, i know lcs ,edit distance and 2 or 3 more. But I just learned it past month.

37

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
38

Long journey ahead i guess. Thanks

1 Like
39

I got ac without using dp.
Here is my solution

1 Like
40

your solution is same as mine!!

1 Like
41

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 :joy:

1 Like
42

Can anyone share the codeforces blog for digit dp mentioned in the editorial? Thanks in advance

43

Its linked in the pre-requisite section. Just click on Digit DP there.

1 Like
44

Hey look at my solution, you’ll understand without requiring any DP. Sometimes you just look for a pattern and you’ll its just math Encoding solution

1 Like
45

You can simplify it further but good one.:wink:

1 Like
46

Yeah by merging oneArr, 45, tenArr into one, and precalculating sum of numbers till 9, yeah but I thought of keeping it understandable by dividing it into pieces.

Hey I have a doubt, I never used this thing,. like few people used val= val*pow(2,MOD-2)%MOD, what is it, why is is used? Ref

1 Like
47

part_10 = part_10* 10 % m;
here it is done so because whenever you are going to multiply appropriate power of 10 with a number you will need its modulus in first place.
As
(A * B)%mod = (A%mod * B%mod)%mod

Hopefully you were talking about this thing.

48

In the link, refer line 108 and 110, he wrote, sum1 = sum1 * pow(2, m - 2) % m; and sum2 = sum2 * pow(2, m - 2) % m;

49

Don’t Know as of now .I will look into it.

1 Like