Help required for GDP from Alquora Contest

general
,
1

Link to question: https://www.codechef.com/ALQU2018/problems/GDP . Can anyone explain the solution(required formulation ) of the problem.

Thanks

2

First you can fix the number of plantinum to suppose z (0<=z<=n), Now for a fixed z you can fix the number of diamond from 0 to n-z and then the remaining will be the Gold. So you get a series in GP with terms

For a fixed z for diamond you have following GP

(2^0)(1^(n-z)) + (2^1)(1^(n-z-1)) + . . . . + 2^(n-z)*1^0 sum of this series is (2^(n-z+1)-1)

Now z can range from 0 to n so our next series becomes

(3^0)(2^(n+1)) + (3^1)(2^n) + … (3^n)(2^1) - (3^0) - (3^1) - (3^2) … -(3^n)

sum of this series is (3^(n+2)+1)/2 - 2^(n+2)

Hope this helps !!

1 Like
3

It can be said that it is coefficient of x^n in the series

(1+x+x^2+…inf)(1+2x+2^2x^2+…inf)(1+3x+3^2x^2+…inf)

Which is 1/(1-x)(1-2x)(1-3x)

So write this in form

A/(1-x) + B/(1-2x) + C/(1-3x)

Ans:= A+B * 2^n + C * 3^n