ENCODING - Editorial

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.:wink:

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 ??

@vijju123

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

@vijju123 if u do concern with the problem please try to help with the following issue

I will let appropriate authorities know of your concern. :slight_smile:

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?