codeforces contest problem

http://codeforces.com/contest/732/problem/D this problem is a good example of binary search. i don’t know how to use binary search in it. of course m looking for an explanation. plzz explain it.it will help others also for understanding binary searching…thanks

There are multiple days on which the ‘m’ exams can be taken, one small observation is that, if it is not possible to pass all exams within some ‘k1’ days, then obviously, it cannot be done in fewer number of days as well, so, all we need to do is check if it is possible to pass all exams in ‘n’ days first, if yes, then we try to find a better solution, i.e check if it is possible to pass all exams in ‘n/2’ days, if yes, then the minimum is somewhere between 0 and n/2 or else, it is between n/2 and n and so on. Now, given ‘x’, how do we know if its possible to pass all exams within ‘x’ days ?, there might be multiple days on which it is possible to pass a particular exam, and we consider for each exam, the last possible day which falls within ‘x’, for example:
m = 2
n = 10
1 2 2 1 2 2 2 1 1 2
In this case (x=10), the last possible day for exam 1 is day 9, and day 10 for exam 2, if its not possible to pass the exams by taking them on these days, then its obviously impossible to do so within ‘x’ days, you can do this in O(N) (by iterating through the exam days), this process iss repeated Log N times at most.

1 Like

good explanation thanks @hemanth_1