Codeforces round#481(Div.3) Tutorial

Revision en5, by aMitkvikram, 2018-05-13 22:18:04

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).

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

  3. 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 ≤ 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 ith 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 ci days which are free for preparation. Hence our solution is optimal.

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

Tags greedy, #sorting

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en7 English aMitkvikram 2018-05-13 22:21:37 5
en6 English aMitkvikram 2018-05-13 22:18:21 0 (published)
en5 English aMitkvikram 2018-05-13 22:18:04 6
en4 English aMitkvikram 2018-05-13 22:16:24 6
en3 English aMitkvikram 2018-05-13 22:15:02 49
en2 English aMitkvikram 2018-05-13 22:14:13 4
en1 English aMitkvikram 2018-05-13 22:13:29 1286 Initial revision (saved to drafts)