FCBARCA - Editorial

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

9 Likes

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:

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

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?

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

10 Likes

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 - CodeChef: Practical coding for everyone

8 Likes

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

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

CodeChef: Practical coding for everyone …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 CodeChef: Practical coding for everyone …I used O(n) for evaluating such polynomial which got AC :), but I wanna know where’s my above approach is wrong…

can anyone tell me the logic behind dividing by 1000000007

the logic behind dividing it by 1000000007 is that to make the answer in range of int datatype so that we can store the answer…otherwise if answer becomes very big then it cannot be stored in any datatype and we can’t output it…

I did it another way and got an AC in the first go.
I’d like to share what I did, as I believe it is quite simple and being a beginner myself, it was a huge surprise to have a method of solving a question that is not mentioned in the editorial.

For n passes to be completed, there must be n-1 people between the first pass delivered by Messi and the last pass received by him. Eg, for 4 passes, the structure looks like this->

M -> _ -> _ -> _ -> M

To fill in these n-1 blanks, we have ‘k’ number of players everytime (Total no. of players= k+1 ; since a player cannot pass the ball to himself, at every stage there are k possible options for passing).

Hence, the number of combinations is k^(n-1).

However, if, Messi is the one who has received the (n-1)th pass, then he cannot pass the ball to himself in the (n)th turn.

So, if somehow we found how many combinations are there such that Messi ends up with the ball after the (n-1)th pass, then we can just subtract this number from k^(n-1) and that would give the correct answer.

Wait a minute, isn’t this number exactly the number which is the solution for k=k and n=n-1? Indeed it is! So, if we generated the correct answer for {i,j-1}, then the solution for {i,j} is j^(i-1) - answer_for_{i,j-1}

So, first we populate an array ar[1001][11] with ar[i][j] as j^(i-1) except when i=0 or 1, in which case, ar[i][j]=0 (because there is no way).

Now, we generate our final array, say ans[1001][11], as ans[i][j] = ar[i][j] - ans[i-1][j].

Use of right-to-left modular exponentiation for calculating j^(i-1) in each turn gives AC in 0.0000 sec!

1 Like

What is the meaning of f[0][x] ??

I solved different set of subproblems to get the answer. We have to complete n passes using k players and messi. So I solved for n=2, then n=3 so on upto n. I used the bottom up approach.
Link to solution: CodeChef: Practical coding for everyone

Hi Guys,
I am getting WA .I think I am having some overflow issues but can’t figure it out.I followed the Matrix Exponentiation approach.Please help me out,below is my code


[1]


  [1]: https://ideone.com/eO26Td

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

@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

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

@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

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.

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.