What is logic behind the problem FCBARCA?

What is the logic behind solving this problem of April 2013 long contest??

It was a simple dynamic programming problem.
a[i][j]=Math.pow(i,j-1)-a[i][j-1];

here is a link to the editorial.

link

1 Like

Hello,

You can refer to the editorial for further clarifications on the problem :slight_smile:

There were a couple of ways of approaching it… My solution shows yet another possibility :wink:

Best regards,

Bruno

I think we can find a recursive formula to solve this problem.

I spent an hour to find that one i think this will help you.
You have N passes and start with messi and end with messi this means that you have total N+1 places where a ball will be.
but the starting and last one will be same(i.e. same player). so basically we have to think for N-1 places.

For N = 2
We have 1 places where we have to set players and we have total 3 (N+1) places.

at that position messi cannot be because messi is at first and last position and we are thinking about second place. so we have K players at 2nd place.

So Answer is = K;

For N = 3;
We have 2(2nd and 3rd) places where we have to set players and we have total 4 (N+1) places.

for second position : Messi cannot be there because messi is at 1st position so we have K players to set there.

for third place : Messi is also cannot be there bacause messi is at 4th position so we have K-1 playes to set there because 1 players who is at 2nd cannot be at 3rd.

So Answer is = K*(K-1);

For N = 4;
We have 3(2nd and 3rd and 4th) places where we have to set players and we have total 5 (N+1) places.

for second position : Messi cannot be there because messi is at 1st position so we have K players to set there.

for third place : Messi can be there so for 3rd place we have two choice either messi or other if messi sit at 3rd place then we have only 1 choice otherwise we have K-1 because one playes is already at 2nd place.

for fourth place : it depends on 3rd if at 3rd position messi is there then we have total K playes to set at 4th but if messi is not there then we have K-1 players to set there.

Case 1: If messi sit at 3rd place:
then we have K*1*K;

Case 2: If other player sit at 3rd place;
then we have K*(K-1)*(K-1)
So the total ways = Case 1 + Case 2.

= `K*K + K*(K-1)*(K-1);`

= `K*( K*(K-1) + 1); /*See alternate + and - */`

You can also find for more players say for N = 4, 5, 6…

So finally the recursive formula is :
my code is:

fun(N) {
    if(N == 2)
        return K;
    else 
        return K*( fun(N-1) + (n%2)?-1:1);
} 

You can see my solution also [link][1]

I think will help for those who are not so much familiar with dynamic programming

Happy Coding !!!
[1]: http://www.codechef.com/viewsolution/1990175

11 Likes

@rajat_121292 >> You can have a look at the editorial as directed by @aichemezee.

I can help you with my approach, let me know if it helps:

Lets define two arrays a[] and b[] where

a[i] denotes the number of ways in which a player will get the ball back after ith pass
b[i] denotes the number of ways in which some other player will get the ball after ith pass

Now lets build up these arrays one by one:

  1. a1 will be the number of ways in which a player can get the ball back after 1 pass, since this is impossible hence a1 = 0.
  2. b1 will be the number of ways in which some other player will get the ball after 1st pass, so suppose Messi had the ball and there are K other players so he can pass it to any of them in K ways. Hence b1 = total number of players - 1. (since that 1 player is the one himself who is passing the ball to any of the remaining players.

Now, a[i+1] = b[i]*1
Why?

Because, a player(say Messi) will get the ball back after i+1th pass if some other player had received the ball after ith pass (i.e. b[i]), and now that player can pass the ball back to Messi in only one way.

b[i+1] = k * a[i] + (k-1) * b[i]
Why?

Because, a player can pass the ball to some other player after (i+1)th pass in the following two possible scenarios:

  1. after ith pass that player(Messi) only got the pass, and then he passed to any of the remaining players (k), so this can be done in a[i] * k ways.
    Note that Messi got the ball after ith pass in this case (and not after (i+1)th pass), which he passed to some other player.

  2. OR some other player got the ball after ith pass (in b[i] ways) and he passed it to any other player excluding Messi (in k-1 ways), so this can be done in (k - 1) * b[i] ways.

Note that since in the problem k was the number of players excluding Messi, so here when the (i+1)th pass can not be made to Messi in the above case, hence number of ways = (k-1) * b[i] ways

Now you have the recursion:

a[i+1] = b[i] 

and

b[i+1] = k * a[i] + (k-1) * b[i]

You want to know the number of ways in which Messi will get the pass back after n passes, so a[n+1] will give you that (assuming indexing started at 1).

Now, while implementing be careful about the overflows, and use mod 1000000007 as and wherever required.

PS: Be careful about the notations used in the explanation and in the problem. In the problem, k is the number of players excluding Messi and I have put this explanation in my own words.

[Here][1] is my implementation of the above idea.

Put in your doubts and queries regarding this explanation.

OR you can always switch over to the editorial which incorporates a detailed explanation.
[1]: http://www.codechef.com/viewplaintext/2010447

2 Likes

for any value of n and k, answer is

k * [ k^n-2 - k^n-3 + k^n-4 - k^n-5 … +/- k^0 ]

which turns out to be a geometric progression and can be simplified as

k * (k^n-1 - 1)/k+1 when n is odd

k * (k^n-1 + 1)/k+1 when n is even

@akshaykhanna please explain how did you get this GP…

3 Likes

Thank you very much for the detailed explanation @upendra1234 :smiley:

thanks @kuruma

1 Like

nice explanation!!thanks!!