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.
1 Like
Hello,
You can refer to the editorial for further clarifications on the problem 
There were a couple of ways of approaching it… My solution shows yet another possibility 
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
8 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:
- 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.
- 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:
-
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. -
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
nice explanation!!thanks!!