Codeforces round#481(Div.3) Tutorial

Правка en2, от aMitkvikram, 2018-05-13 22:14:13

978G-Petya's Exam

1.This is a greedy problem. First thing to notice is that exam which is occurring earlier compared to others should be prepared first, i.e. exam which is having less di should be prepared earlier(if value of s allows to do so).

  1. Sort the exams in the increasing order of di. If we go through solution we can see that it gives optimum solution.

  2. Let us take an exam from the sorted order = {si , di, ci}. Since we have sorted exams , 1 ≤ j ≤ n AND j ≠ i; either di%\leq$dj or jth exam is completed(We are processing in increasing order of di). Now we have to prepare ci days for exam i in the interval si and di(and obviously we are forced to do so, so that's an optimal step). Now since all other exams(for which preparation is not done yet) are after i^{th} exam, what is the best way to choose ci days in the interval [si, di] such that we leave better opportunities for the preparation of other exams?If we iterate from si to di and choose first $c_i% days which are free for preparation. Hence our solution is optimal.

Worst case time complexity is : O(m*n).

Теги greedy, #sorting

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en7 Английский aMitkvikram 2018-05-13 22:21:37 5
en6 Английский aMitkvikram 2018-05-13 22:18:21 0 (published)
en5 Английский aMitkvikram 2018-05-13 22:18:04 6
en4 Английский aMitkvikram 2018-05-13 22:16:24 6
en3 Английский aMitkvikram 2018-05-13 22:15:02 49
en2 Английский aMitkvikram 2018-05-13 22:14:13 4
en1 Английский aMitkvikram 2018-05-13 22:13:29 1286 Initial revision (saved to drafts)