FCBARCA - Editorial

editorial
, , , , ,
1

PROBLEM LINK:

Practice
Contest

Author: Bruno Oliveira
Tester: Hiroto Sekido
Editorialist: Anton Lunyov

DIFFICULTY:

SIMPLE

PREREQUISITES:

Simple Math

PROBLEM:

Let Messi have index 0, while all other players have indexes from 1 to K.
Denote as f[n][x] the number of sequences {a[0], a[1], …, a[n]} of integers such that:

  • 0 ≤ a[j] ≤ K for j = 0, 1, 2, …, n;
  • a[0] = 0, a[n] = x;
  • a[j−1] ≠ a[j] for j = 1, 2, …, n.

We need to find f[N][0] mod P, where P = 1000000007.

QUICK EXPLANATION:

Let K be fixed and g[n] denotes f[n][0] mod P. Then g[0] = 1, g[1] = 0 and
g[n] = ((K − 1) * g[n−1] + K * g[n−2]) mod P for n ≥ 2.
See EXPLANATION for proof.

So the problem can be solved using simple loop. But be careful with modular arithmetic. The following code:

g[n] = ((long long) (K-1) * g[n-1] + (long long) K * g[n-2]) % 1000000007;

is safe at C++ for calculating g[n] for the above recurrence. Not writing long long will cause int overflow.

Alternatively the problem can be solved using formula (KN + K * (−1)N) / (K + 1). But using this formula requires either inverse residue modulo P or arbitrary precision arithmetic. So use it on your own risk :slight_smile:
See ALTERNATIVE SOLUTION for details.

EXPLANATION:

At this section we justify recurrence for g[n].
It is clear that f[0][0] = 1 and f[0][x] = 0 for x = 1, …, K.
Basic combinatorial reasoning yields that f[n][x] for n > 0 is the sum of f[n−1][y] for all y from 0 to K, inclusive, such that y ≠ x. Indeed, term a[n−1] can be any number from 0 to K, inclusive, except x. So after fixing y = a[n−1] and deleting a[n] we get the arbitrary sequence that is counted by f[n−1][y].

The constraints are very soft. So even such quadratic DP will pass the TL, but we continue further.
It is clear that f[n][1] = f[n][2] = … = f[n][K] since all players except Messy are non-distinguishable by the above definition. Hence denoting g[n] = f[n][0] and h[n] = f[n][1] we can get the following formulas for g[n] and h[n]:

g[n] = f[n][0] = f[n−1][1] + … + f[n−1][K] = K * h[n−1];

h[n] = f[n][1] = f[n−1][0] + f[n−1][2] + … + f[n−1][K] = g[n−1] + (K−1) * h[n−1].

Summarizing we get:
g[0] = 1, h[0] = 0,
g[n] = K * h[n−1],
h[n] = g[n−1] + (K−1) * h[n−1].

By theses formulas we already get simple O(N) solution (refer to the tester’s solution).
But we can get another simplification.
Multiplying formula for h[n] by K we get:
K * h[n] = K * g[n−1] + (K−1) * (K * h[n−1]).
Note that K * h[n] = g[n+1] and K * h[n−1] = g[n].
Hence we get
g[n+1] = K * g[n−1] + (K−1) * g[n] for n > 1.
Together with g[1] = K * h[0] = 0 we get the solution described in the QUICK EXPLANATION section.

Note also that using exponentiation by squaring for 2 × 2 matrices we can solve the problem in O(log N) time using recurrent formulas for g[n] and h[n]. Most of the related problems listed below require similar considerations but also require some advanced technique like exponentiation by squaring in the end.

ALTERNATIVE SOLUTION:

Here we prove the explicit formula mentioned in the QUICK EXPLANATION section.
We apply the basic theory of linear homogeneous recurrence relations with constant coefficients to the recurrent sequence g[n]. For this we write down the characteristic polynomial:

**p(t) = t2 − (K−1) * t − K**.

Its roots are r1 = −1 and r2 = K. Hence the general solution for this recurrence is

**g[n] = C1 * r1N + C2 * r2N = C1 * (−1)N + C2 * KN**.

Constants C1 and C2 can be found from relations g[0] = 1, g[1] = 0.
Namely, substituting n = 0 and n = 1 to the general form of g[n] we get

 C1 + C2 = 1; −C1 + K * C2 = 0.

Solving this 2 × 2 system we get C1 = K / (K + 1) and C2 = 1 / (K + 1).
Hence g[n] = (Kn + K * (−1)n) / (K + 1) and we are done.

The simplest way to use this formula is to use language with built-in arbitrary precision arithmetic like Java or Python and calculate the above expression directly and then take it modulo P in the end.

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.
Tester’s solution can be found here.

RELATED PROBLEMS:

Codeforces Round #113 (Div. 2) - Problem E - Tetrahedron
NEWSCH
CKISSHUG
CROWD
CSUMD
CHESSGM
HAREJUMP
CAKEDOOM

8 Likes
2

I got lucky by somehow guessing the recursive function:

def solve(n, k, cache):
    if (n, k) in cache:
        return cache[(n, k)]
    if n == 1:
        return 0
    ans = cache[(n,k)] = (pow(k, n, 1000000007) - solve(n - 1, k, cache)) % 1000000007
    return ans

Then noticed all my answers were K times too big, so multiplied by inverse(k).

Edit: BTW - Thanks for the fun problem! :slight_smile:

3

I did the recursion split into two arrays a[] and b[] where a[i] denotes the number of ways in which a player can get the ball back after ith pass and b[i] denotes that some other player will get the ball after ith pass. a[1] = 0, b[1] = k. and a[i+1] = b[i], b[i+1] = k*a[i] + (k-1)*b[i] can be obtained using simple Permutations and Combinations. http://www.codechef.com/viewplaintext/2010447 here is the implementation of the above recursion.

EDIT 1: It can also be thought of as, consider a graph with vertices = total number of players (including Messi). Now lets call the adjacency matrix(with Messi representing the first row and the first column) for the graph as M. The number of ways in which Messi will get the ball back after nth pass will now be M[0][0] in M raised to power n which can be obtained using repeated squaring.

1 Like
4

I read the EDIT 1 part somewhere, so I will be glad if someone comes up with a proof for the same.

5

I have used the ‘Alternative Solution’ technique, except that I have used the Geometric Progression series in its raw form.

http://www.codechef.com/viewsolution/2010842

Could you please tell where have I gone wrong?

6

@avinrox >> You can check your fault here: http://ideone.com/gPImVm I ran your code with the following tests 999 10, 999 9

1 Like
7

thank you for the site… but it doesn’t help me understand why the approach is wrong!

8

@avinrox >> I thought you should have made out. Actually, you’ve wrote result = (Kn - result)%FACT and you’re also maintaining Kn after MOD. so there might be a case when Kn < result. In that case result will be negative. See, I edited the code, to display what was happening at each step. Note the places where result went negative. http://ideone.com/vuF5jJ

1 Like
9

Can someone explain this line:“It is clear that f[n][1] = f[n][2] = … = f[n][K] since all players except Messy are non-distinguishable by the above definition”
i know its a bit silly to ask such question but do provide some examples if u have any.

10

at the time during contenst ,thought about EDIT1,you are explaining but i fail to implement that…however i have done the problem using series generated by Permutation of players.

11

I did the problem in a different way:
for k : number of player
and n : be number of player
problem states that messi will start and end with the ball…hence we are assured that the pattern will be of the type :

M…M

now for passes to be n there will be n-1 players in between two M hence we have:
M ( n-1 players) M.

now we check for n=2

M _ M will be the pattern. and no two same player can be adjacent hence the there can be kC1 = k players can be placed in b/w two M.
hence f(2)=k.

now for n=3

M _ _ M will be the pattern hence there will kC1*(k-1)C1 ways to insert two players.
hence f(3)=k^2-k.

now for n=4

we have M _ _ _ M here

case 1:When M is not in middle:

we have 1 out of k players can be placed at first position but at second position we can place 1 out of k-1 players and on third place we can place 1 out of (k-2 remaining + 1 which is placed at first place) hence we have: kC1*(k-1)C1*(k-1)C1

case 2:When M is in Middle:
then there will be kC1*kC1 ways to place the players.


hence
f(4)=case1+case2=k*(k-1)^2+k^2 = k^3-k^2+k

now for n=5

case 1: When no M is in places 1 to 4:

then there will be kC1*k-1)C1*(k-1)C1*(k-1)C1


case 2:When there is only one M:
then there will be 2C1*kC1*kC1*(k-1)C1 no. of ways to place k players.here 2C1 multiplied because there are two possibilities of M are M _ M _ _ M and M _ _ M _ M.
hence f(5)= case1+case2=`k*(k-1)^3+2*k^2*(k-1)=k^4-k^3+k^2-k`

similarly for n=6 we get
f(6)=k^5-k^4+k^3-k^2+k

hence we have a generalised formula for calculating
f(n)=k^(n-1)-k^(n-2)+k^(n-3)-.........+((-1)^n)*(n).

however we can make an recursive solution by analysing above formula that
f(n)=k^(n-1)-f(n-1). with f(2)=k as the initial result.

but i solve it using formula You can see my solution at http://www.codechef.com/viewsolution/2012785
7 Likes
12

My approach was this:

  • we have fixed number of players K + Messi

  • we want to calculate F(N) - number of ways

  • we have to recognize two cases - Messi was the last player or not

  • if Messi was the last player, next pass is to one of K players

  • if Messi wasn’t last player, next pass can be to Messi or to one of K-1 players

  • because Messi is the first one F(N) = F(N, ‘Y’) where second parameter is flag described above

  • we have recursion now, we have to solve ending condition - N=1, but as we know, Messi have to be last, so F(1, ‘N’) = 1 and while pass is to another player F(1, ‘Y’) = 0

    F(N) = F(N, ‘Y’)

    F(N, ‘Y’) = K * F(N-1, ‘N’)

    F(N, ‘N’) = F(N-1, ‘Y’) + (K-1) * F(N-1, ‘N’)

My solution in Java - http://www.codechef.com/viewsolution/1982017

7 Likes
13

because of symmetry, no one is different from others.

14

fun(n,k)=k^n-1 - fun(n-1,k)
fun(0,k)=1;
i think !!

15

I used the same method and generalized by mathematical induction…Wise minds :stuck_out_tongue:

1 Like
16

Hey there,

I came up with the formula i.e for f(n,k)=k^(n-1)-k^(n-2)+k^(n-3)…with alternate + - ending with appropriate sign for k^(1).

http://www.codechef.com/viewsolution/2005353 …Using simple method O(nlogn) of evaluating (k^n)%m for each term & adding or subtracting them as necessary,this solution gave me WA…As I know on 250,6 it gives negative answer…but on higher values like 1000 10 it gave me right answer.I strongly think my powmod(…) func is right…plz help.

Also http://www.codechef.com/viewsolution/2012479 …I used O(n) for evaluating such polynomial which got AC :), but I wanna know where’s my above approach is wrong…

17

Well, apart from the for loop in main() I can’t actually see many differences on the other approach… Even data types are correct… :frowning:

18

Yes u are correct, in AC sol.n i didn’t called that powmod() so neglect it. I instead used a simpler version of calculating polynomials like this ax^n + bx^n-1…O(n).

I am just asking why did the above approach of simply calculating first ax^n then bx^n-1 upto last term didn’t worked out(I know the error is in powmod())…I feel strongly that it’s correct…I just want the flaw in it…
Thanks.

19

@xpertcoder Your powermod is very correct.

But, you get WA because, you have some subtractions in your code, and subtractions in modular arithmetic doesn’t just work the way you coded.

In modular arithmetic (say, modulo n), actual negative numbers also become positive under the modulo. So, -k will be represented as n-k.

I added that change to your code, and voila!!

There are two positions in your code, to add that check and I have done both. Have a look: http://www.codechef.com/viewplaintext/2056117 and http://www.codechef.com/viewplaintext/2056109 (Both are AC solutions)

2 Likes
20

OMG!!! That’s it.I didn’t knew that…All I know was whenever you get (a-b)%m all you do is ((a%m)-(b%m))%m. I left that case of yours.Now I am gonna remember that for a very long tym. THANKS A LOT. :slight_smile:

1 Like