Problem: CSES - Coding Company
Editorial: Solution - Coding Company (CSES)
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:
- Using i th person to finish an unfinished team.
- 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
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.
3 Likes
@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?
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
@taran_1407 Thank you so much 
1 Like