How Can I solve this problem ! https://vjudge.net/problem/UVA-11904 Will be grateful if anyone can help. Thank You.
How Can I solve this problem ! https://vjudge.net/problem/UVA-11904 Will be grateful if anyone can help. Thank You.
# | User | Rating |
---|---|---|
1 | ecnerwala | 3648 |
2 | Benq | 3580 |
3 | orzdevinwang | 3570 |
4 | cnnfls_csy | 3569 |
5 | Geothermal | 3568 |
6 | tourist | 3565 |
7 | maroonrk | 3530 |
8 | Radewoosh | 3520 |
9 | Um_nik | 3481 |
10 | jiangly | 3467 |
# | User | Contrib. |
---|---|---|
1 | maomao90 | 174 |
2 | awoo | 164 |
2 | adamant | 164 |
4 | TheScrasse | 159 |
4 | nor | 159 |
6 | maroonrk | 156 |
7 | -is-this-fft- | 150 |
8 | SecondThread | 147 |
9 | orz | 146 |
10 | pajenegod | 145 |
Name |
---|
You can solve this problem by changing the perspective to solve it from the back, imagine you have $$$k_1+k_2+\cdots+k_n$$$ time slots. Notice that, because every $$$job_i$$$ must be finished before finishing $$$job_{i+1}$$$, then the last time slot must be taken with the last job ($$$job_n$$$). So you must put one $$$job_n$$$ in the last time slot, and then, just fill the remaining time slots with $$$k_n-1$$$ of the last job. So we will have $$$C(k_1+k_2+\cdots+k_n-1,k_n-1)$$$ ways of filling this time slots. You can then just imagine throwing out away the time slots taken by $$$job_n$$$, then this problem goes out the same for the second last job, and then for the third last job and so on.
You can solve this problem by using a simple $$$\text{prefix sum}$$$ ($$$pre[x]=\sum_{i=1}^{x}k_i$$$), and also $$$\text{precompute factorials}$$$ and $$$\text{inverse modulo factorials}$$$ to easily compute $$$\text{combinations}$$$. With all that in place, we will have the final answer, which is:
For reference, you can see my $$$\text{Accepted}$$$ code for this problem.