Editorial for COCI '10 Contest 5 #4 Honi

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Let $A_1, A_2, \dots, A_N$ $A_{1}, A_{2}, \dots, A_{N}$ denote the sets of tasks with weights $1, 2, \dots, N$ $1, 2, \dots, N$ , respectively. Additionally, let $B_2, B_3, \dots, B_N$ $B_{2}, B_{3}, \dots, B_{N}$ denote the sets of tasks with weights $1$ $1$ or $2$ $2$ , $2$ $2$ or $3$ $3$ , …, $N-1$ $N - 1$ or $N$ $N$ , respectively. Finally, let $B_1 = 0$ $B_{1} = 0$ .

The problem can now be solved using a dynamic programming approach; starting from the first weight (the least one) we choose a task for each weight. When choosing a task with the weight equal to $T$ $T$ , we need to check whether another task from the set $B_T$ $B_{T}$ has already been taken. Therefore, it is sufficient to have a table of the form $dp[t][b]$ $d p [t] [b]$ .

This yields the following relations:

$\displaystyle \begin{align*} dp[0][0] &= 1 \\ dp[0][1] &= 0 \\ dp[i][0] &= dp[i-1][0] \times (A_i+B_i) + dp[i-1][1] \times (A_i+B_i-1) \\ dp[i][1] &= dp[i-1][0] \times B_i + dp[i-1][1] \times B_{i+1} \end{align*}$ $\begin{aligned} d p [0] [0] & = 1 \\ d p [0] [1] & = 0 \\ d p [i] [0] & = d p [i - 1] [0] \times (A_{i} + B_{i}) + d p [i - 1] [1] \times (A_{i} + B_{i} - 1) \\ d p [i] [1] & = d p [i - 1] [0] \times B_{i} + d p [i - 1] [1] \times B_{i + 1} \end{aligned}$

Comments

0

Anshv2 commented on Oct. 17, 2024, 12:17 a.m.

For dp[i][1] the Bi term should be Bi+1 for the first term: dp[i][1] = dp[i-1][0] Bi+1 + dp[i-1][1] Bi+1.