Help With "Coding Company" (CSES)

general
, ,
#1

Problem: CSES - Coding Company
Editorial: https://usaco.guide/solutions/cses-1665?lang=cpp

I have gone through the above editorial for this problem. The first two transitions make perfect sense, but I don’t understand the last two transitions which are:

  1. Using i th person to finish an unfinished team.
  2. Using i to start a new unfinished team.

The problem is with the way the penalties are handled in these two transitions, I don’t understand why it is done that way.

Can anybody please explain these transitions?

[Note: I have gone through the Codeforces blog on Non-Trivial DP tricks (“Open And Close Interval”) but that didn’t help.]

@cubefreak777 @taran_1407 @akshitm16

1 Like
#2

For transition “Using i th person to finish an unfinished team”, since we are computing DP_{i, j, k} and one team is being finished, there must be j+1 unfinished teams before this person. We can choose any of those teams, so we have (j+1)*DP_{i-1, j+1, k-s_i} ways. k-s_i happens because the current person contributes s_i to skill, and we want the total skill after the current person to be k.

The fourth transition is also based on the same ideology.

2 Likes
#3

@taran_1407 Thanks for your response. But it is the line "k-s_i happens because i^{th} person contributes s_i to the skill" which I can’t understand. For example, if I have made a few teams like (1,3), (4,5,8) [the numbers are the skill level], and I am currently wanting to finish the team (1,3) by adding the person with skill level 10 then the increase in the total penalty will only be 10-1 = 9 [assuming that initially both the teams were open, so the initial total penalty was 0], the increase will not be the equal to the skill level in this case. Can you please explain this? How does the i^{th} person contribute s_i to the penalty, when penalty is defined as the difference between the maximum and the minimum skill level in a team?

#4

We are listing all transitions, as they would affect DP_{i, j, k} which means after considering first i people, we have j unfinished teams and sum of skill difference is k.

So only DP_{i-1, j+1, k-s_i} shall affect, since after closing one team (in (j+1)*DP{i-1, j+1, k-s_i}, the sum of skills would become (k-s_i) + s_i = k.

The example you referred, say you have two unfinished teams (1, 3), (4,5,8), so current skill level is -1-4 = -5, Since whenever we start an interval, we subtract the skill value of lowest skilled. So this way is included in DP_{5, 2, -5} meaning after first 5 people, 2 unfinished teams and skill level -5.

Hope this clarifies.

1 Like
#5

@taran_1407 Thank you so much :smile:

1 Like