Even Dillema

Link:https://www.codechef.com/CODN2018/problems/EVNDIL

Can anyone explain the solution for this?

@hemanth_1 could u explain?

The problem is to find the number of ways we can have an even number of zeros in a string. So for some 2i number of zeroes, 0 \leq i \leq {\dfrac{k}{2}}, the number of possible strings of length k are {k\choose 2i}\cdot 9^{k-2i}, this is k\choose k-2i ways of selecting the positions for the non zero characters, and 9^{k-2i} number of ways we could select these characters.

Now the problem reduces to finding the summation:

\sum_{i = 0}^{\lfloor k/2\rfloor}{k\choose 2i}\cdot 9^{k-2i}

It would take \Omega(k) time to compute, which is infeasible under one second since k can be upto 10^{18}. So this needs to be simplified further which can be done using the binomial expansions of (9 + 1)^k and (9 - 1)^k in the following way:

(9 + 1)^k=\sum_{i = 0}^{k}{k\choose i}\cdot 1^i\cdot 9^{k - i}
(9 - 1)^k=\sum_{i = 0}^{k}{k\choose i}\cdot (-1)^i\cdot 9^{k-i}
\therefore 10^k + 8^k = 2\cdot \sum_{i = 0}^{\lfloor k/2\rfloor}{k\choose 2i}\cdot 9^{k-2i}
($\because$ the odd terms cancel out leaving behind two times every even term)
\implies \sum_{i = 0}^{\lfloor k/2\rfloor}{k\choose 2i}\cdot 9^{k-2i} = \dfrac{10^k + 8^k}{2}

Both 10^k and 8^k could be computed using repeated exponentiation which would take \mathcal{O}(log(k)).

Here’s a simple implementation in C++, and a Python one liner.

2 Likes

first see the constraints

k\leq 10^{18} \text{ & } t\leq 10^4

.
From there the time complexity can’t be anything more than O(\log{k}).

The solution : consider the k digit strings which have x 0’s. You can choose x places for 0’s in kCx ways and other places can be filled by other 9 numbers in 9^{k-x} ways. So no. of ways in which we have x 0’s in k string are kCx*9^{k-x}.

Total no. of k strings having even no. of zeroes are

kC_0*9^k + kC_2*9^{k-2} + kC_4*9^{k-4}+...... = \frac{(9+1)^k + (9-1)^k}{2} = \frac{10^k+8^k}{2}

Now you can find 10^k , 8^k in O(\log{k}) time.
also since 10^9 + 7 is a prime using fermat’s theorem we can find modular inverse of 2 using modular exponentiation as 2^{num-2}\mod{num} where num is 10^9+7.

Here is my submission for your reference.

2 Likes

You can also solve this problem using MATRIX-EXPONENTIATION ! But I have realised that this is an overkill after seeing the solutions of other contestants ! So,what you can do is first find the answer for k=1,k=2,k=3 nd k=4 then using the same technique which we use for finding nth term in fibonacci series you can find the answer for n=k ! My solution : https://www.codechef.com/viewsolution/17865825 !
Hope you like it ! Happy coding !

we don’t even need to find it for k=2,3,4. we know that F(0)=1 , F(1)=9 and the recurrence relation F(n)=18F(n-1)-80F(n-2). that’s it

My idea uses matrix exponentiation, but the solutions mentioned here are much simpler and better :slight_smile:

yeah exactly !

@hemanth_1, I am not able to figure out how you arrived at the recurrence relation (to be used in matrix exponentiation) without knowing that the answer is \frac{10^k+9^k}{2} .Once you know the formula it’s easy to reach F(n)=18F(n-1)-80F(n-2).But how you figured it out without knowing this. Can you please elaborate on it

That was not the recurrence that I got. What I thought was:

Even(i) = Number of strings of length ‘i’ having even number of '0’s.

Odd(i) = Number of strings of length ‘i’ having odd number of '0’s.

Even(i) = 9*Even(i-1) + Odd(i-1)

Odd(i) = 9*odd(i-1) + Even(i-1)

1 Like

why do we went upto k/2 iterations ??

" print(((pow(10, k, 1000000007) + pow(8, k, 1000000007)) * (500000004)) % (1000000007)) " Why it is multiplied by 500000004 ??

@harrypotter0 500000004 is inverse of 2 mod 10^9+7.
Since we have to divide 8^k+10^k by 2 , we multipied by its mod by inverse of 2.

if we divide it by 2 I was getting WA .

yes because (a/b)%mod !=(a%mod / b%mod)

1 Like

yes instead it’s \frac{a}{b} \equiv ab^{-1}\mod{m}, but GCD(b,m) must be equal to 1

okk thanks for your help :slight_smile: