You are not logged in. Please login at www.codechef.com to post your questions!

×

WGHTNUM - Editorial

4
3

PROBLEM LINK:

Div2
Practice

Setter- Varad Kulkarni
Tester- Misha Chorniy
Editorialist- Abhishek Pandey

DIFFICULTY:

SIMPLE

PRE-REQUISITES:

Fast Exponentiation

PROBLEM:

Given a value of $N$, number of digits in a number $D_1D_2D_3...D_N$, and $W$ which is given by $W=\sum_{i=2}^N (D_i - D_{i-1})\,$, we have to find number of $N$ digit numbers which have weight $W$ modulo ${10}^{9}+7$.

QUICK EXPLANATION:

We can reduce the expression to $W=D_n-D_1$ where $D_n$ is the rightmost digit, and $D_1$ is the leftmost digit. We see that we can find valid numbers only for $-9\le W \le 8$, for all other values of $W$ the answer is $0$. If $-9\le W \le 8$, we brute force the pair of digits $(D_1,D_N)$ such that $D_N-D_1=W$. Let this be denoted by $cnt$. Clearly, answer is $cnt*{10}^{N-2}\% ({10}^{9}+7)$

EXPLANATION:

" Oh...This question...This question has that $"\sum"$ symbol...It must be..It must be very difficult."

If you left the question because of above belief, then dont read this editorial. You're gonna regret that decision of yours :(

For this question, since Editorialist's , Tester's, and Setter's, all three have use a similar approach, so the approach will be described in a bit more detail. After discussing the intuition and approach, we will see tester's idea to further reduce time complexity in the bonus section :).

Editorialist's/Tester's/Setter's Solution-

The very first thing we need to look at is the constraints. We have number of test cases, $T$ as $1\le T \le {10}^{5}$ and $2 \le N \le {10}^{18}$ , which clearly hints that we need to answer to answer each test case in $O(logN)$ or $O(1)$ complexity.

With that in mind, we should first try to simplify the summation. Carefully look at the summation $W=\sum_{i=2}^N (D_i - D_{i-1})\,$ and try to expand it. On expanding it, we get-

$W=\sum_{i=2}^N (D_i - D_{i-1})\,$

$=(D_2-D_1)+(D_3-D_2)+(D_4-D_3)......(D_N-D_{N-1})$

We see that we can cancel some terms above. Upon cancelling, we are left with-

$W=D_N-D_1$ where $0 \le D_i\le9$.

This means $W$ is nothing but difference of first and last digit of the number. This restricts valid values of $W$ to $-9\le W \le 8$. No answer exists for any value outside this range.

The first conclusion, hence, is that answer for $W$ outside the range $[-9,8]$ is $0$ as no such $N$ digit number exists.

Now, how to find $W$ for $-9\le W \le 8$ $?$

We notice that for answer to exist, we need to put adjust only $D_n$ and $D_1$, while any other digit $D_i$ in between can take any value from $[0,9]$. Lets focus on valid pairs of $(D_1,D_N)$ right now.

What we can do is, we can brute-force all possible pairs of $(D_1,D_N)$, and count the number of pairs satisfying $D_N-D_1=W$. Let this be denoted by $cnt$. Or, you can simply find the number of valid pairs by this formula-

if(w>=0)//Proof -By simple counting of pairs
    cnt=9-abs(w);
else
    cnt=10-abs(w);

Please note that $D_1$ (leftmost digit) cannot be $0$ as leading $0's$ are not allowed.

Now we have the number of valid pairs of $(D_1,D_N)$ in $cnt$. What about the rest of the digits? We see that the answer is independent of all other digits. Thus, all the remaining $N-2$ digits can take any value between $[0,9]$.

So, we have $cnt$ choices for $D_1,D_N$ and ${10}^{N-2}$ choices for rest of the $N-2$ digits. Thus, the answer will be $cnt*{10}^{N-2}\% ({10}^{9}+7)$. We will calculate ${10}^{N-2}\% ({10}^{9}+7)$ using fast exponentiation. (Link to algo given under pre-requisites).

$Time$ $Complexity=$ $O(T*LogN)$

SOLUTION:

Setter
Tester - $O(Log(MOD)$ solution by Misha. :)
Tester - $O(1)$ solution by Misha :D
Editorialist's

CHEF VIJJU'S CORNER:

1.During contest, this question was flooded with comments- with everyone speaking the same thing - "Are constraints wrong?" or "How can W be >10? Why do constraints have W upto 300?" . &etc. While almost EVERYONE derived that formula that $W=D_N-D_1$, they all got stuck at this trivial stuff that why is $W$ upto 300 in problem statement. Whats worse, they started feeling that since $|W|\le 300$ in the question, perhaps their derivation and understanding of the question is wrong. I have nothing to say here, except that if you yourself arent confident at your solution, dont expect anyone else to. Have confidence in what you do, and at the same time learn to accept when you go wrong. Balance these two things, and thats the secret of life :).

2. I have to mention Misha's immense variety of solution. If you see tester's code (the $O(Log(MOD))$ one), he has used something different. He used bpow(10, (n - 2) % (MOD - 1)), while setter and me have simply used count*fastExpo(10,n-2) (fastExpo and bpow, both are same). He framed that solution based on Euler's Totient Function and Euler's theorem. Go through the given links, try to derive the expression. Answer is in the tab below to cross check :).

View Content

3. Dont open the tab below.

View Content

Now, Misha did not want to stop at $O(Log(MOD)$ solution, so he devised an $O(1)$ solution! Basically, that solution uses pre-processing. What he did is, we know that $MOD <{2}^{30}$. Hence, the highest value which we deal with can be represented within $30$ bits.

He took the binary representation of number , and partitioned it into 3 parts, consisting 10 bits each. (Remember we can represent the numbers within 30 bits).

Now, he uses his $POW00[],POW10[],POW20[]$ arrays to calculate any power of $10$ from $[0,MOD]$ in $O(1)$ time. $POW00[]$ is simple, it just stores powers of 10 mod ${10}^{9}+7$ for powers from $[0,1023]$. Imagine it like this, we partitioned the $30-bit$ number into $3$ part of $10$ $bits$ each. $POW00[]$ deals with lowest 10 bits. Multiplying previous element by $10$ is like adding $1$ to power of previous element, (which , in terms of binary numbers, is essentially adding $1$ to binary representation of the number. ) Recurrence formula-

$POW00[i]=10*POW[i-1];$

He does the same in $POW10[]$ array. He adds $1$ to binary representation of number- but he is careful of one thing. $POW00[]$ dealt with numbers from $[0,{2}^{10}-1]$, where the value of $LSB$ is 1. However, in case of $POW10[]$, the $LSB$ is (in reality) the $11$ $'th$ bit of the number. Hence, we multiply it with ${10}^{1024}$ instead of $10$.

$POW10[i]={10}^{{2}^{10}}*POW10[i-1];$

Similarly, in $POW20[]$, the recurrence relation is $POW20[i]={10}^{{2}^{20}}*POW20[i-1]$. Its basically, he is adding $1$ to the $LSB$ of the $10-bit$ partition. And adding one there, means we must multiply it with 10, raised to power equal to value of that $LSB$. His generator code is given below for the curious :).

View Content

4. Some of the good questions on fast exponentiation-

This question is marked "community wiki".

asked 08 Apr '18, 03:51

vijju123's gravatar image

5★vijju123 ♦♦
15.4k12066
accept rate: 18%

edited 18 Apr '18, 17:17

admin's gravatar image

0★admin ♦♦
19.8k350498541


Well Explained but solution are not opening :(

link

answered 17 Apr '18, 16:56

drjaat's gravatar image

2★drjaat
267112
accept rate: 6%

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

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

(17 Apr '18, 17:02) vijju123 ♦♦5★

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
link

answered 17 Apr '18, 17:00

harrypotter0's gravatar image

4★harrypotter0
318110
accept rate: 1%

edited 17 Apr '18, 17:01

4

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

(17 Apr '18, 17:04) vijju123 ♦♦5★

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

link

answered 17 Apr '18, 18:04

des1997's gravatar image

2★des1997
203
accept rate: 0%

Why reduced TL?

(17 Apr '18, 18:07) vijju123 ♦♦5★

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

(17 Apr '18, 18:45) des19972★

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

(17 Apr '18, 19:12) vijju123 ♦♦5★

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

(17 Apr '18, 20:07) des19972★

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

(17 Apr '18, 20:12) vijju123 ♦♦5★

Yes,Misha is great.

(17 Apr '18, 20:26) des19972★
4

Yes, Misha is great :D If it would be "she" xD

(18 Apr '18, 01:11) mgch6★
showing 5 of 7 show all

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

link

answered 18 Apr '18, 22:09

jagreetdg's gravatar image

3★jagreetdg
2189
accept rate: 9%

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

(18 Apr '18, 22:40) vijju123 ♦♦5★
1

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

(19 Apr '18, 14:00) jagreetdg3★

@jagreetdg u missed AC due to a typo:(

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

link

answered 18 Apr '18, 22:33

des1997's gravatar image

2★des1997
203
accept rate: 0%

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

(18 Apr '18, 22:49) vijju123 ♦♦5★

0.00 seconds and 0M ,i see. hahahahahaha

(18 Apr '18, 22:54) des19972★

Is fast exponentiation same as modular exponentiation?

link

answered 20 Apr '18, 10:14

pavitra_ag's gravatar image

4★pavitra_ag
696
accept rate: 5%

1

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.

(20 Apr '18, 10:20) aryanc4036★
1

Means calculate a to the power b and then take mod n. This method takes O(logn) time. And is quite fast to calculate a to the power b and then take mod n.

(20 Apr '18, 10:21) aryanc4036★
2

Yes, you can call them essentially the same, aside from minor difference @aryanc403 pointed out. People use them interchangeably :)

(20 Apr '18, 14:25) vijju123 ♦♦5★

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?

link

answered 21 Apr '18, 22:32

montycs's gravatar image

0★montycs
1057
accept rate: 0%

This is due to no of digits which can be at D2 is 10,D3 is 10,D4 is 10 and so on. All these satisfy given requirement so we multiply by 10 for all these no.

e.g. - Let w=8. n=4 We have D4=9, D1=1.

possible combinations are - 9001, 9011, 9021... 9091, 9101, 9111, 9021... 9191, 9201, 9211, 9221... 9291,

9901, 9911, 9921... 9991. As you can see all no except 1 and 4 can form a 2 digit no from 0 to 99. Hence 100 possible no.

(21 Apr '18, 22:50) aryanc4036★

For w=7. n=4 you can try 9002, 8001. And write no in similar fashion. There will be 100 possible combinations for 2m3 digit and for 1 and for 2 possible, And we will get 200 poss answers.

(21 Apr '18, 22:50) aryanc4036★
1

Basic combinatorics. What are the possible values which all the $N-2$ digits can take (except first digit and last digit)? Anything from $0$ to $9$. Total choices per digit $=10$. Number of digits$= N-2$. Hence $Ans= 10*10*10....N-2$ $times$. Hence ${10}^{N-2}$

(21 Apr '18, 23:07) vijju123 ♦♦5★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×3,766
×307
×89
×9

question asked: 08 Apr '18, 03:51

question was seen: 2,802 times

last updated: 23 Apr '18, 02:09