XX86's blog

By XX86, history, 6 weeks ago, In English,

How Can I solve this problem ! https://vjudge.net/problem/UVA-11904 Will be grateful if anyone can help. Thank You.

  • Vote: I like it
  • +9
  • Vote: I do not like it

6 weeks ago, # |
Rev. 4   Vote: I like it +9 Vote: I do not like it

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:

$$$ \left(\sum_{i=1}^{n}C(pre[i]-1, k_i-1)\right) \mod (10^9+7) $$$

For reference, you can see my $$$\text{Accepted}$$$ code for this problem.