FCBARCA - Editorial

editorial
, , , , ,
21

can anyone tell me the logic behind dividing by 1000000007

22

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ā€¦

23

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!

24

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

25

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: https://www.codechef.com/viewsolution/15011756

26

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