AqaAsadiTrains
SRM 787 · 2020-06-17 · by a.poorakhavan
Problem Statement
There are K football posts (e. g. goalkeeper, defender, left-wing forward). Aqa Asadi has N students to train. All students are arranged in a line. At any moment, each student is trained to exactly one of the K posts. The posts are numbered from 0 to K-1 and the students are numbered from 0 to N-1 in the order in which they initially stand in the line.
The training is performed as a sequence of steps. In each step Aqa Asadi performs one of the following operations:
-
Call a manager of a team and have them hire one of the students. The student leaves the line and goes away with the manager.
Aqa Asadi receives a commission from the manager for this action. The commission depends on the post for which the player is trained: if the post is x, Aqa Asadi gains C[x] dollars. - Select one student in the line and convert them from a player to a coach. Then, select one of the students adjacent to the new coach and have the coach train that player. Once that is done, the coach will leave the line and go home. The other student will remain in the line but they will now be trained to a possibly different post. The new post of this student is t[x][y], where x is the post of the coach and y is the old post of this student.
Notes:
- Some positions may currently be so undesirable that the commission for them is negative. E.g., if C[7] = -3 and Aqa Asadi has a student trained to post 7, if he wants a manager to hire that student, he has to pay the manager 3 dollars.
- During the training process Aqa Asadi's bilance may be negative. E.g., the example action described in the previous line can be the very first action of the training process, and after this action Aqa's bilance will be -3 dollars.
- In the end there can be some students left unhired by any manager, and for those you will get no money at all, but you also don't have to pay the manager to hire them. However, you cannot just send a student away from the line during the training process without having them hired.
- Due to Aqa Asadi's unique training process, the new post t[x][y] may be different from both x and y.
- The training process is not necessarily symmetric: in general, t[x][y] may be different from t[y][x].
- Please remember that at each moment each student is only trained to one post. When they are coached, they learn the new post but forget the old one.
- Whenever a student leaves the line for any reason, his neighbors now become adjacent in the new line.
The input you are given are the
- The array C has K elements. C[x] is the commission Aqa Asadi receives from a manager each time they sign a player with post x.
- The array A has N elements. A[y] is the original post to which student y is trained.
- The array T has K*K elements. The value t[i][j] is equal to T[i * K + j].
Aqa Asadi would like to make as much money as possible on the commissions. Calculate and return his largest possible total profit.
Constraints
- K and N will each be between 1 and 50, inclusive.
- C will have K elements.
- Elements of C will be between -1000000 and 1000000 (-10^6 to 10^6), inclusive.
- A will have N elements.
- Elements of A will be between 0 and K-1, inclusive.
- T will have K*K elements.
- Elements of T will be between 0 and K-1, inclusive.
{3, 0, -5}
{0, 0}
{2, 0, 0, 2, 1, 1, 1, 2, 2}
Returns: 6
There are three posts. For each student trained to post 0 Aqa Asadi can get a commission of 3 dollars. As he already has two such students, the best solution is to have a manager sign both of them to get 3 + 3 dollars.
{40, -10, -30, 10, 50}
{3, 2}
{0, 1, 2, 2, 4, 4, 3, 2, 3, 1, 3, 0, 0, 2, 3, 2, 0, 3, 1, 3, 4, 2, 4, 4, 3}
Returns: 10
Aqa Asadi has two students. If he has a manager sign both of them, he will get the provisions C[3] + C[2] = 10 + (-30) = (-20). That's worse than doing nothing. A better solution would be to have a manager sign student 0 and then to just send student 1 away. The commission for doing this is C[3] = 10. Coaching does not help us here, either.
{40, -10, -30, 10, 50}
{3, 2}
{0, 1, 2, 2, 4, 4, 3, 2, 3, 1, 3, 0, 0, 0, 3, 2, 0, 4, 1, 3, 4, 2, 4, 4, 3}
Returns: 50
The provisions and players are the same as in Example #1 but coaching now works in a different way. If we convert student 1 to a coach and have them re-train student 0, we will get a single student who will now be trained to the post t[2][3] = 0 and we can get the commission C[0] = 40 for signing him up with a team. An even better solution is to convert student 0 to a coach and have them re-train student 1 to the new post t[3][2] = 4. We will then get the commission C[4] = 50.
{140114, -508750, -892852, 577062, 835009, -899238, 594078, 390980, -467211, -263500, 46170, -130916, -292415, -969933, -936753, 580304, 273585, -115129, 52187, 154817, -388101, 970407, 803750, 662151, 467150, -755106, 518466, -282866, 359144, -659120}
{3, 5, 27, 11, 6, 21, 27, 8, 0, 18, 0, 13, 5, 1, 27, 12, 29, 14, 0, 17, 20, 9, 22, 10, 19, 5, 5, 5, 20, 24}
{23, 24, 8, 2, 6, 4, 22, 12, 6, 28, 19, 10, 28, 9, 26, 3, 11, 7, 14, 11, 29, 1, 5, 24, 3, 9, 9, 1, 2, 23, 29, 24, 18, 7, 26, 5, 7, 12, 2, 20, 10, 2, 25, 23, 1, 13, 7, 22, 14, 20, 26, 15, 5, 25, 27, 2, 20, 27, 14, 18, 10, 25, 4, 1, 10, 16, 13, 19, 3, 21, 20, 14, 25, 20, 2, 0, 2, 4, 12, 15, 9, 11, 14, 13, 25, 4, 12, 25, 20, 28, 21, 11, 23, 25, 23, 25, 13, 20, 29, 22, 11, 6, 12, 29, 24, 18, 7, 26, 25, 20, 4, 3, 21, 26, 18, 10, 26, 20, 29, 24, 15, 3, 9, 18, 21, 21, 4, 13, 22, 16, 24, 6, 29, 16, 27, 4, 10, 27, 9, 9, 8, 26, 2, 22, 0, 16, 23, 6, 29, 3, 22, 26, 24, 14, 25, 9, 17, 2, 28, 6, 12, 1, 23, 6, 20, 8, 12, 23, 27, 28, 2, 6, 22, 5, 25, 20, 2, 5, 22, 9, 20, 24, 11, 1, 25, 7, 7, 15, 28, 11, 11, 0, 13, 14, 21, 7, 26, 3, 9, 6, 13, 1, 14, 21, 4, 27, 6, 4, 16, 17, 6, 8, 11, 4, 12, 12, 18, 0, 16, 3, 28, 0, 26, 19, 19, 28, 0, 21, 19, 22, 22, 18, 1, 25, 13, 2, 19, 16, 8, 29, 27, 19, 4, 11, 21, 17, 9, 5, 0, 23, 20, 25, 21, 27, 26, 21, 20, 14, 27, 21, 18, 11, 20, 25, 18, 12, 24, 11, 17, 25, 6, 3, 15, 24, 7, 20, 6, 13, 28, 10, 28, 4, 15, 15, 6, 18, 21, 19, 5, 2, 28, 7, 20, 17, 14, 0, 18, 20, 6, 10, 22, 16, 6, 2, 0, 22, 14, 29, 21, 5, 26, 13, 3, 14, 2, 8, 27, 25, 11, 18, 3, 24, 7, 25, 11, 18, 14, 22, 15, 20, 26, 15, 14, 29, 7, 15, 15, 0, 19, 28, 9, 12, 21, 20, 5, 9, 26, 4, 3, 24, 11, 0, 26, 21, 0, 4, 3, 29, 28, 23, 15, 11, 24, 29, 28, 6, 9, 29, 19, 2, 0, 19, 2, 22, 16, 15, 18, 28, 9, 2, 13, 24, 5, 20, 25, 6, 19, 29, 15, 26, 21, 9, 23, 19, 22, 14, 25, 27, 0, 22, 24, 24, 2, 25, 20, 11, 27, 23, 26, 20, 3, 19, 5, 1, 23, 25, 27, 3, 24, 16, 0, 7, 8, 23, 6, 14, 5, 5, 15, 10, 17, 12, 8, 14, 28, 2, 19, 10, 18, 0, 8, 5, 17, 5, 19, 17, 5, 19, 8, 16, 22, 17, 2, 4, 13, 2, 29, 5, 27, 24, 25, 10, 5, 16, 14, 0, 24, 17, 18, 7, 7, 12, 17, 25, 14, 12, 2, 15, 23, 12, 24, 10, 9, 29, 18, 5, 20, 0, 26, 13, 19, 15, 10, 17, 20, 29, 1, 14, 8, 17, 16, 5, 8, 12, 15, 18, 4, 3, 13, 22, 29, 16, 27, 21, 1, 11, 6, 4, 18, 17, 7, 8, 5, 25, 8, 2, 9, 13, 25, 17, 13, 28, 16, 23, 1, 7, 12, 11, 9, 3, 25, 16, 6, 6, 14, 20, 27, 23, 6, 18, 4, 6, 23, 26, 8, 25, 29, 16, 0, 4, 15, 9, 21, 24, 20, 21, 11, 21, 29, 29, 22, 6, 7, 21, 9, 25, 10, 4, 4, 5, 3, 3, 2, 27, 9, 2, 23, 28, 17, 15, 9, 3, 5, 14, 15, 16, 8, 9, 2, 14, 29, 6, 12, 26, 4, 6, 6, 27, 29, 21, 6, 1, 8, 10, 2, 16, 25, 15, 25, 28, 23, 15, 3, 25, 29, 25, 26, 12, 21, 2, 19, 3, 6, 9, 7, 16, 17, 14, 15, 19, 22, 19, 28, 3, 25, 17, 17, 13, 13, 9, 19, 21, 12, 11, 27, 8, 18, 13, 26, 28, 11, 9, 8, 3, 3, 3, 27, 21, 20, 29, 9, 8, 18, 1, 26, 25, 22, 22, 10, 12, 20, 8, 26, 1, 0, 17, 3, 20, 23, 12, 21, 0, 9, 0, 21, 6, 16, 14, 11, 21, 27, 24, 16, 8, 23, 22, 22, 18, 11, 1, 19, 29, 16, 3, 10, 19, 10, 22, 15, 20, 18, 17, 22, 0, 14, 25, 4, 21, 25, 8, 24, 6, 7, 9, 13, 1, 27, 10, 14, 28, 12, 28, 6, 9, 8, 27, 12, 26, 20, 7, 23, 19, 13, 16, 24, 16, 0, 23, 7, 20, 14, 16, 0, 17, 3, 26, 11, 29, 7, 19, 12, 25, 29, 3, 8, 13, 17, 4, 5, 18, 6, 29, 21, 19, 5, 27, 19, 17, 1, 15, 4, 7, 5, 0, 16, 11, 21, 2, 26, 13, 19, 26, 10, 6, 11, 23, 14, 11, 13, 22, 5, 20, 22, 21, 1, 6, 23, 26, 29, 25, 21, 0, 6, 20, 4, 28, 16, 4, 13, 20, 28, 24, 21, 21, 27, 6, 4, 12, 6, 7, 0, 20, 26, 8, 0, 18, 28, 27, 23, 15, 5, 19, 3, 1, 1, 3, 26, 10, 16, 22, 4, 0, 6, 2, 5, 21, 3, 21, 0, 5, 2, 18, 27, 21, 15, 22, 28, 11, 4, 21, 11, 6, 28, 18, 2, 1, 14, 10, 15, 4, 5, 26, 17, 14, 22, 18, 27, 7, 17, 7}
Returns: 12881701
{608494, 258820, -788494, 633176, 402458, -255192, -875252, 135393, 486360, -906752, -575027, -72877, -393471, -325731, -864287, 163468, -943323, -666245, -43944, 10360, 893737, 812552, 370656, -996644, 469656, 410737, -25261, 450709, -995415, -941851}
{24, 19, 1, 17, 27, 3, 7, 4, 4, 28, 3, 4, 27, 5, 2, 8, 8, 20, 1, 20, 22, 29, 0, 21, 3, 0, 6, 19, 1, 12}
{26, 3, 23, 7, 10, 19, 11, 9, 2, 23, 16, 17, 10, 29, 29, 4, 24, 25, 13, 0, 27, 0, 18, 6, 18, 15, 23, 11, 15, 11, 23, 9, 19, 29, 13, 11, 15, 11, 17, 11, 21, 20, 1, 0, 23, 5, 22, 1, 28, 13, 9, 24, 24, 4, 15, 20, 25, 5, 8, 5, 27, 16, 19, 1, 16, 5, 11, 11, 6, 22, 19, 1, 17, 27, 24, 15, 2, 28, 18, 28, 27, 9, 26, 6, 18, 21, 2, 14, 8, 19, 23, 16, 17, 17, 28, 4, 6, 8, 3, 8, 25, 7, 27, 17, 24, 14, 8, 12, 3, 26, 12, 9, 23, 21, 16, 4, 26, 21, 6, 26, 9, 23, 15, 21, 4, 13, 26, 15, 14, 4, 24, 27, 23, 3, 7, 7, 12, 4, 5, 2, 20, 21, 1, 25, 27, 23, 1, 13, 14, 26, 15, 27, 12, 1, 3, 19, 14, 18, 16, 22, 29, 14, 4, 27, 17, 19, 27, 7, 14, 3, 26, 8, 23, 8, 11, 10, 0, 2, 22, 21, 6, 15, 22, 13, 12, 0, 0, 4, 13, 2, 6, 19, 6, 1, 11, 17, 23, 8, 2, 25, 22, 26, 21, 11, 23, 2, 14, 21, 0, 1, 28, 8, 24, 0, 9, 0, 16, 24, 15, 28, 16, 8, 10, 11, 27, 23, 18, 4, 11, 11, 17, 18, 0, 14, 28, 2, 18, 11, 7, 3, 27, 24, 22, 3, 12, 25, 16, 27, 26, 27, 2, 28, 9, 13, 12, 1, 1, 10, 24, 23, 6, 16, 24, 8, 16, 5, 15, 24, 8, 18, 29, 18, 8, 23, 16, 7, 28, 2, 8, 17, 22, 20, 1, 0, 4, 1, 12, 4, 6, 6, 15, 10, 17, 16, 11, 20, 8, 1, 12, 20, 20, 0, 20, 20, 28, 21, 2, 0, 17, 23, 0, 20, 29, 20, 27, 6, 1, 10, 8, 21, 26, 6, 19, 17, 6, 29, 1, 24, 20, 7, 13, 14, 19, 17, 2, 4, 13, 7, 11, 25, 23, 18, 8, 14, 26, 1, 29, 16, 26, 21, 29, 17, 26, 11, 27, 19, 15, 1, 6, 6, 9, 26, 19, 3, 3, 7, 2, 24, 25, 21, 5, 3, 17, 2, 24, 24, 3, 14, 21, 16, 9, 27, 29, 23, 7, 11, 22, 13, 13, 21, 7, 14, 1, 12, 0, 27, 12, 22, 1, 5, 9, 15, 15, 10, 23, 20, 6, 13, 22, 17, 29, 14, 7, 22, 19, 9, 11, 9, 10, 13, 7, 18, 21, 4, 19, 9, 14, 18, 23, 21, 15, 10, 3, 24, 9, 22, 1, 22, 20, 3, 24, 28, 22, 13, 26, 10, 13, 12, 17, 14, 9, 3, 23, 2, 26, 10, 3, 16, 26, 17, 13, 25, 4, 24, 17, 1, 21, 21, 28, 22, 22, 10, 22, 17, 8, 29, 21, 12, 19, 26, 1, 0, 10, 24, 7, 25, 0, 19, 11, 25, 23, 27, 20, 28, 15, 10, 1, 15, 25, 14, 9, 13, 7, 5, 26, 26, 26, 29, 3, 29, 17, 5, 9, 27, 2, 9, 22, 26, 22, 9, 9, 0, 3, 26, 13, 27, 19, 3, 11, 7, 9, 10, 29, 1, 27, 29, 0, 19, 23, 24, 0, 17, 27, 2, 5, 10, 21, 20, 9, 2, 0, 9, 15, 3, 27, 24, 10, 18, 6, 6, 13, 24, 15, 23, 20, 17, 0, 2, 23, 5, 15, 16, 18, 4, 21, 16, 17, 3, 27, 7, 22, 9, 2, 21, 21, 14, 17, 22, 5, 19, 28, 27, 18, 19, 10, 16, 14, 24, 11, 14, 14, 18, 6, 29, 22, 1, 24, 9, 25, 24, 9, 19, 5, 10, 24, 5, 4, 23, 23, 3, 5, 8, 20, 2, 15, 6, 4, 15, 25, 14, 13, 12, 11, 8, 7, 18, 22, 5, 16, 18, 16, 21, 24, 2, 23, 13, 14, 3, 18, 23, 11, 25, 9, 3, 29, 16, 4, 29, 12, 4, 24, 7, 6, 17, 16, 10, 1, 9, 2, 22, 10, 7, 24, 8, 24, 7, 26, 22, 2, 1, 24, 11, 7, 16, 3, 0, 27, 11, 3, 7, 25, 7, 20, 15, 9, 21, 8, 21, 24, 12, 14, 28, 14, 16, 17, 13, 28, 17, 15, 14, 1, 25, 11, 9, 15, 3, 29, 22, 28, 26, 29, 13, 13, 28, 5, 23, 6, 4, 8, 3, 4, 13, 24, 2, 0, 12, 10, 5, 26, 0, 7, 0, 5, 12, 11, 5, 0, 15, 2, 23, 1, 14, 10, 9, 10, 9, 16, 26, 9, 5, 26, 13, 18, 18, 26, 8, 26, 16, 26, 12, 16, 4, 10, 17, 1, 16, 0, 22, 14, 2, 11, 2, 9, 9, 13, 8, 21, 21, 10, 9, 27, 23, 12, 19, 17, 13, 15, 29, 14, 13, 3, 13, 1, 28, 18, 4, 22, 10, 26, 8, 5, 19, 19, 19, 0, 29, 29, 10, 14, 22, 7, 20, 19, 0, 18, 15, 13, 9, 27, 10, 4, 17, 6, 13, 28, 19, 26, 20, 10, 1, 12, 4, 8, 18, 9, 16, 8, 1, 18, 1, 9, 6, 19, 7, 21, 20, 8, 19, 14, 8, 5, 17, 13, 10, 23, 20, 19, 19, 17, 6, 3, 17, 25, 25, 10, 21, 6, 13, 20, 4, 8, 26, 8, 12, 10, 29, 25, 8, 20, 1, 5, 5, 22, 24, 13, 24, 22, 16, 6, 28}
Returns: 13399561
{10, -47}
{1, 0, 1}
{1, 1, 1, 0}
Returns: 20
There are two player types: type 0 is a good player (worth 10) and type 1 is a bad player (worth -47). The optimal solution for Aqa Asadi is to first sell the middle player, which leaves two bad players who are now adjacent. Now he can have one of them train the other one, producing a second good player.
{10, -47}
{1, 1, 1, 1, 1, 1, 1}
{1, 1, 1, 0}
Returns: 30
The optimal solution is to create three pairs of students. In each pair one of the students will coach the other one. In this way we can produce three good players. One bad player will be left over.
{-30, 10, -10, -40, -30}
{1, 1, 3, 1, 3}
{4, 4, 1, 2, 1, 2, 1, 0, 3, 0, 2, 0, 0, 0, 4, 1, 3, 3, 2, 0, 0, 0, 2, 0, 2}
Returns: 30
The optimal solution is to have a manager hire students 0, 1, 3, and to leave the other two students unhired.
{10, -47, -1}
{1, 2, 1}
{1, 1, 2, 1, 0, 2, 2, 2, 2}
Returns: 9
The optimal solution is to have a manager hire the middle student, even though the provision is negative, and then to have one of the remaining students train the other one.
Submissions are judged against all 70 archived test cases, of which 9 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class AqaAsadiTrains with a public method int getMax(vector<int> C, vector<int> A, vector<int> T) · 70 test cases · 2 s / 256 MB per case