Author: Ryan Leonel Somali
Abridged problem statement: There are N types of items and you can get one random item for one gold. Given G gold and several needed items, what is the probability of getting all needed items?
This problem can be solved by dynamic programming.
Let Ai be the number of needed item for type i and f( g, x ) be the probability of getting needed items from type x to N with g gold.
Then we can calculate f( g, x ) using this formula:
The recursion will terminate when x > N, if g = 0 then return 100.0 otherwise return 0.0.
Here’s a bit explanation about the recursive formula: To solve f( g, x ), we should calculate what is the probability to get all needed items if you have i items of type x for all i from Ax to g (at least Ax and at most all g golds go to item of type x). Since item order matters, we should multiply this with nck( g, i ): choose i from g gold (decide which gold will be spent for item of type x), and divided by Ni: the number of all possibilities.
This problem was solved by 6 teams. The first team to solve this problem: SYSU_Blover from Zhongsan (Sun Yat-sen) University, minute 134.