Бинарный поиск по ответу: задачи «Дипломы» и «Коровы - в стойла»

[@op_ulstu]

На 5:53, к сожалению, ошибка: в качестве начального значения для r следует брать diplomaCount * max(diplomaHeight, diplomaWidth), иначе решение будет выдавать неверный ответ на тестах вида «diplomaCount = 5, diplomaHeight = 1, diplomaWidth = 100». Спасибо зрителю @zero_klou, обратившему внимание на этот недочёт. Когда ограничения на количество и размер дипломов велики, такая инициализация r, как было замечено, может повлечь переполнения при промежуточных вычислениях в функции can(). Попробуйте решить соответствующую задачу на ACMP: acmp.ru/index.asp?main=task&id_task=712, чтобы получить более полное представление об этом (обратите внимание, что будет происходить на тестах вида «diplomaCount = 10^9, diplomaHeight = 1, diplomaWidth = 10^9»). Существует более общий и надёжный способ подбирать верхнюю границу в задачах, где есть риск получить переполнение или неверный ответ из-за неправильно выбранной константы: int l = 0, r = 1; while (!can(diplomaCount, diplomaHeight, diplomaWidth, r)) r *= 2; Такой подбор верхней границы потребует не более logN итераций (то есть столько же, сколько и последующий бинпоиск), поэтому не скажется на общей сложности программы.

[@DauletKelimberdin]

когда я пишу 2 3 10 выводит 10. А ответ 9

[@ДенДенев-в1л]

Как же автор все круто объяснил. Я физически ощутил как поумнел и вспомнил множество задач где можно было бы использовать бинарный поиск предварительно отсортировав коллекцию любой сортировкой с той же логарифмической сложностью.

[@miron5733]

Офигенное объяснение 10 / 10, спасибо!

[@БибарысК-о2я]

Здраствуйте! Очень хотелось бы видео про ДП и рюкзаки и тд! СПАСИБО!!!

[@beworld_pasha]

Попалась задача данного типа в Я.Контесте, отличное видео, спасибо!)

[@Лев-й7я]

А случаем не в нлогн

[@Лев-й7я]

Кружок такой есть

[@updornespit]

@@Лев-й7я ты в какой группе?

[@Лев-й7я]

@@updornespit был в прошлом году в a это пред последния он в тинсы не смог поступить):

[@Лев-й7я]

@updornespit я в прошлом году был в групе а но в этом году не поступил в тинсы ): група а это пред послединия група

[@starosta8498]

У вас отличные уроки с актуальными темами. Очень жаль, что видео выходят весьма редко

[@HopeOfMankind_]

Большое спасибо!

[@ДаниилСинцов-б9в]

Отличное объяснение!

[@ГлебКрасавчик-н7о]

Шикарное объяснение, спасибо. Только в видео (если я не прав поправьте) на 5:34, где показан альтернативный код проверки возможного вхождения/невхождения числа в промежуток написано rows>=(diplomCount+colums-1) / colums, разве не должно быть просто rows>=diplomCount /colums?

[@op_ulstu]

Обычное деление происходит с округлением вниз, нам же нужно округление вверх. Если нужно разместить 10 дипломов и было 4 столбца, то понадобится не менее 3 строк.

[@ГлебКрасавчик-н7о]

А зачем мы к кол-ву дипломов прибавляем кол-во столбцов, вычетаем 1, а потом делим на кол-во столбцов?

[@op_ulstu]

@@ГлебКрасавчик-н7о Это стандартный способ записи деления с округлением вверх: (a + b - 1) / b. Если a уже делилось нацело на b, то от добавления (b - 1) результат деления не изменится. А вот если a не делилось нацело на b (то есть была хотя бы "лишняя" единица в остатке), то добавления (b - 1) будет достаточно, чтобы результат деления стал на единицу больше.

[@zero_klou]

По поводу кода для задачи с дипломами: не совсем понятно, зачем при расчете mid нам требуется вычислять right - 1. Мы же тут рассматриваем не границы массива чисел, а сами числа. Также при расчете правой границы целесообразно высчитывать её не на основе высоты, а на основе большей стороны диплома. А так спасибо, всё очень понятно объяснено.

[@op_ulstu]

Возможно, вы перепутали единицу и строчную L - в коде написано «int mid = left + (right - left) / 2». Это достаточно традиционный способ поиска середины с защитой от переполнений, когда left и right становятся достаточно большими по модулю (распростанённое «int mid = (left + right) / 2» в этом случае будет переполняться). Такое выражение тоже может переполниться, но только когда left большое и отрицательное, а right большое и положительное; это может случиться только в самом начале, и, как правило, такую проблему сравнительно просто заметить. По поводу начального значения правой границы - да, верно, в видео, к сожалению, здесь досадная ошибка, подразумевалось «r = diplomaCount * max(diplomaHeight, diplomaWidth)», иначе это решение будет работать неверно на примерах вида «diplomaCount = 5, diplomaHeight = 1, diplomaWidth = 100». Спасибо, что обратили на это внимание.