# CSES Coding Company

Hi there,

I was trying to solving the CSES problem “Coding Company” and stuck on this problem a few days.
Although USACO provides an internal solution here https://usaco.guide/solutions/cses-1665,
I’m unable to understand it.
It will be appreciated if anyone can explain the code or provide the dp definition.
Thank you.

First, sort the people. This allows us to express the contribution of each team as (\text{Skill of last person}) - (\text{Skill of first person}). Let s_i denote the skill of the i-th person.

dp[i][j][k] = The number of ways we can form teams from the first i people such that there are j “unfinished” teams and the total penalty so far is k.

There are 4 cases when we transition from i - 1 to i:

• We make a team consisting of only person i.
• The number of ways to do this is dp[i - 1][j][k], since the penalty from this team is 0.
• We append person i to an unfinished team.
• The number of ways to do this is j \cdot dp[i - 1][j][k], since there are j teams we can choose from and the penalties don’t change.
• We use person i to “finish” an unfinished team.
• The number of ways to do this is j \cdot dp[i - 1][j + 1][k - s_i], since person i contributes s_i to the cost and there were j + 1 teams to choose from.
• We start a new unfinished team with person i.
• The number of ways to do this is dp[i - 1][j - 1][k + s_i], since person i contributes -s_i to the cost.

Two more things:

• k in our DP array can be negative, so just add 5000 to each k.
• dp[i] depends only on dp[i - 1], so we can drop the first dimension that we store (to save memory).
1 Like

I believe that this is called “open and close interval trick”. See zscoder’s blog post for more information and problems.

2 Likes

Case #3. since it has j + 1 options to choose from and lead to j unfinished teams, shouldn’t the dp be (j + 1) * dp[i - 1][j + 1][k + si] ?
Case #4. since the person starts a new team, the dp should be dp[i][j][k - si] += dp[i - 1][j - 1][k] ?