aMitkvikram's blog

By aMitkvikram, history, 18 months ago, In English,

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

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

By aMitkvikram, history, 18 months ago, In English,

977D — Divide by three, multiply by two

  1. We can see that all numbers in given sequence are distinct. since all numbers in sequence are of the form . Hence if ai = aj then = = 2x - m = 3y - n which is not possible because any power of 2 will be an even number and any power of 3 will be an odd number.

  2. if there exists in sequence then 2 * ai can not be in sequence and vice versa. We can prove it using contradiction. Suppose there is a number ai such that both and 2 * ai exists in sequence. by little bit of tricks this = , this again is not possible by same argument as above, we just have to change the order of exponents.

  3. Hence for each ai in sequence we see if or 2 * ai is present(remember that only one of them can be present). Now if there is any ai such that both and 2 * ai is not in sequence then this should be an. if there is any such ai that for all 0 ≤  j ≤ n:   ≠  ai AND 2 * ai  ≠  ai, then this is a1.

  4. Once you have got a1, you keep on producing sequence just by doing binary search for and 2 * ai (remember only one of them is present so once you find it you print it).

Read more »

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