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
Can anyone share the codeforces blog for digit dp mentioned in the editorial? Thanks in advance
Its linked in the pre-requisite section. Just click on Digit DP there.
1 Like
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
You can simplify it further but good one.
1 Like
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
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.
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;
Don’t Know as of now .I will look into it.
1 Like
pow(x, m - 2) is the modular inverse of x modulo m. That is, a * pow(2, m - 2) is the same as a/2 modulo m.
1 Like
This gives me 500000003 Infinity in a compiler
long a = (long) 1e9+7; long m = (long) 1e9+7; System.out.println((a/2)%m+" "+a*Math.pow(2L,m-2L));
It should give 500000004. Also, note that pow() is slow and has bugs, better write your own function for raising to a power in log(exponent) time. Also check this
Yeah, I have power function, and yes I was thinking the same it should give 50…004 not 3, dont know why