Igor_Kudryashov's blog

By Igor_Kudryashov, 10 years ago, translation, In English

Analysis of problem "E. Helper"

To solve the problem, firstly, it was necessary to carefully read the input data and convert all the time specified in the format day, hour, minute in a minute since the beginning of the session for convenience. This could be done by using formula newTime = (day - 1) * 24 * 60 + hour * 60 + minute.

Secondly, it is necessary to count the number of free minutes for solving the problems, which Valera has throughout the session. In addition, for every free minute j it is needed to determine tj --- number of this minute since the beginning of the session.

Next, it is needed calculate the value of deadlinei for each student --- the latest free minute since the beginning of the session that if Valerie has finished to perform the task at that moment, he will receive the promised sum from the respective student. Obviously, if Valerie will not be sleeping or eating at the moment of i-th student begin to pass the exam, then deadlinei will be equal to a minute prior to the beginning of the exam, else deadlinei will correspond to the latest free minute prior to sleeping or a meal. In addition, if the free minute from the beginning of the session doesn't exist or Valera can not help i-th student, than we define deadlinei = -1 in this case. 

Then we will sort all the students in non-decreasing value of deadline and use the method of dynamic programming. The two parameters i --- amount of viewed students (i.e. those for which the problems is already solved) and j --- the number of free minute, from which Valera can begin to perform tasks for the next student will be the states of "dynamics". The value of the "dynamics" will be the maximum profit that Valerie can get when he will reach the respective state.

Obviously, there are two possible transition from state i, j:

  1. in the state i + 1, j --- Valera will not solve the problems for the i-th student in this case
  2. in the state i + 1, j + time[i] (where time[i] is the time required for solving problems of i-th student) --- Valera will solve the problem for i-th student in this case, and he will get sum of money this student is ready to pay. However, such a transition is possible only if t(j + time[i]) does not exceed deadlinei.

Once the value of dynamics for all possible values of i, j will be counted, the answer to the problem will be a maximum of n-th row of the array (where n --- the total number of students).

In addition, you should use an additional array of ancestors and accurately convert the time back to the desired form to restore the answer.

  • Vote: I like it
  • +13
  • Vote: I do not like it