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
Oh is it Like in one go calculate all possible digits which can be placed at a given index and check which digits can be placed using dp and calculate it’s contribution ??
Roughly on the surface, yes.
@admin there is a problem with some of ur test cases as in Python it is showing " end of file error while reading "error which is ur backend mistake I believe
@admin u can see this in the following submission CodeChef: Practical coding for everyone Most of Python users who made correct program had to face this issue please correct it and reissue the ranking
I will let appropriate authorities know of your concern. 
1 Like
Hi,
I cross checked the input format using the standard template (which asserts that all constraints are adhered to and that there are no extra characters except the one specified in input). It does not give any error related to wrong format of input (it’d throw RE:SIGBRT due to failed assert elsewise).
Link - CodeChef: Practical coding for everyone
Can you cross check your claim once?