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

# | User | Rating |
---|---|---|

1 | MiFaFaOvO | 3681 |

2 | Um_nik | 3553 |

3 | tourist | 3515 |

4 | Benq | 3508 |

5 | ecnerwala | 3390 |

6 | TLE | 3223 |

7 | scott_wu | 3209 |

8 | Petr | 3205 |

9 | ksun48 | 3197 |

10 | Radewoosh | 3188 |

# | User | Contrib. |
---|---|---|

1 | Errichto | 204 |

2 | antontrygubO_o | 189 |

2 | pikmike | 189 |

4 | Monogon | 186 |

5 | vovuh | 184 |

6 | Ashishgup | 182 |

7 | Um_nik | 180 |

8 | SecondThread | 174 |

9 | Radewoosh | 172 |

10 | ko_osaga | 161 |

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

↑

↓

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Aug/14/2020 23:37:13 (f3).

Desktop version, switch to mobile version.

Supported by

User lists

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.

thank you so much.