Блог пользователя coder__12345

Help needed in Packing Rectangles (Binary Search)
Автор coder__12345, история, 11 месяцев назад, По-английски

Problem Link: https://codeforces.net/edu/course/2/lesson/6/2/practice/contest/283932/problem/A

Accepted Code
Not Accepted Code

The only change in the two code is the value being assigned to l, when i normally implement binary search i use it like in the not accepted one but why in this problem its giving wrong answer?

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
11 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by coder__12345 (previous revision, new revision, compare).

→ Ответить
»
11 месяцев назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Lets have this set were — is not fit and + is fit - — — — + + + l = -1 and r = 7 int the first time in while loop: m =3 and l became 4 you notice that l is in a fit position and r in a fit position and that is not acceptable , we need only r to be in + positions and l to be in — position. Then , the while loop continue working and your code retrun 5 not 4 because of that we set l to m not to m+1

→ Ответить
»
11 месяцев назад, # |
← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

While implementing the BS the way you have done you need to use: if(isfit(l)) cout<<l<<endl; else cout<<r<<endl; because you are storing the ans in r, when r = mid and l = mid + 1 and l satisfies the condition it will not get updated into r because of the condition "while(r-l>1)" so at the end you have to put an extra check.

This will get AC: https://ide.geeksforgeeks.org/online-cpp-compiler/c8c64c48-58eb-424c-9bf5-5eb5752e69a0

The way BS is implemented in this code is better because you have to print only that variable which is storing the ans: https://ide.geeksforgeeks.org/online-cpp-compiler/fce3d222-6532-49d1-8fcb-67c65c2fa39a

→ Ответить
»
11 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

First code finds point where isfit changes 'sign', if isfit(l) before running BS was = false you don't need to check it anymore, answer is always r. Second code is kind of mix with no clear idea behind it. It should work after changing to while r>l, but 1st is just a lot better concept.

btw mid = (l+r)/2 saves some keystrokes.

→ Ответить