You are not logged in. Please login at www.codechef.com to post your questions!

×

codeforces contest problem

0
1

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

asked 24 Oct '16, 20:05

mahipalsaran's gravatar image

3★mahipalsaran
2389
accept rate: 8%


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.

link

answered 24 Oct '16, 21:05

hemanth_1's gravatar image

6★hemanth_1
1.4k12
accept rate: 28%

edited 24 Oct '16, 21:07

good explanation thanks @hemanth_1

(24 Oct '16, 21:19) mahipalsaran3★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×1,056
×690
×686

question asked: 24 Oct '16, 20:05

question was seen: 854 times

last updated: 24 Oct '16, 21:19