WGHTNUM - Editorial

My approach

for __ in range(readInt()):
n,w = readInts()
thoko = 0
for i in range(1,10):
    for j in range(10):
        if j-i==w :
            thoko+=1
sumi = pow(10,n-2,mod)
sumi%=mod
print (sumi*thoko)%mod

Include this problem in practice section with reduced TL if possible:)

Whats the problem with this submission, I have tried every possible solution but it doesn’t seem to pass even the first sub case.

Solution Link :

https://www.codechef.com/viewsolution/18314975

@jagreetdg u missed AC due to a typo:(

mod is 1e9+7 not 10e9+7.
1e9+7 -> 1000000007(10^9+7)

Is fast exponentiation same as modular exponentiation?

I am not good in maths… “So, we have cnt choices for D1,DN and 10N−2 choices for rest of the N−2 digits. Thus, the answer will be cnt∗10N−2%(109+7)”, how did 10N-2 come into picture?

Solutions will take some time as @admin links them to the page where they are uploaded. Sorry :frowning:

But, I made sure to comment almost all of my solutions so that theres a commented code :slight_smile:

Good :). You got the essence of the solution. Thoko taali xD

4 Likes

Why reduced TL?

Then i think everybody will try out the O(1) approach.

Nooo. xD. Thats a good approach, but lets not force it. Thing is, at times, making LogN solution fail, fails some of O(1) solutions as well due to tight time limit.

Also, question would be really complex and tough if we force that xD. Willing can try, else its fine. I will tell Misha you liked her approach though :stuck_out_tongue:

Yes as u say.
actually did this problem in just around 5 minutes in practice section during contest with straight forward fast expo trick.
Then today after this O(1) approach i was like …
and btw her,i thought him:)

xD . I am glad people from all divisions are liking the bonus contents. Really have to thank Misha for that though. Misha is great :smiley: :slight_smile:

Yes,Misha is great.

Yes, Misha is great :smiley: If it would be “she” xD

4 Likes

There is a difference between MOD=10e9+7 and MOD=1e9+7. Check the values yourself.

His solution is #1 in div2 for this question in terms of time taken and memory used :stuck_out_tongue:

0.00 seconds and 0M ,i see.
hahahahahaha

Just realized how much trouble a single ‘valueless’ 0 can cause.
Silly Typo XD

1 Like

Yes, @pavitra_ag Here we are calculating modular exponentiation. Name of method used is fast exponentiation. As the name suggest it is faster method to calculate power of a no. Sometimes both are used interchangeably to mean same.

1 Like