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]$ ~dp[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*}$

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.