Я сижу такой уверенный, что уж я то точно смогу изи написать бинарный поиск. Дошел до задачки про совет школы. Написал за 15 минут на бумажке решение через бинарный поиск. Думаю дай ка напишу реализацию на джаве. И 4 гребаных часа промучался ))) теперь я сижу уже не такой уверенный, но довольный собой)
вообще огонь. Я до этого бин поиск представляла себе исключительно в форме поиска одного того самого элемента в массиве, а вот такая подача про хороший-плохой, левый и правый -- это вообще огонь, начала реально понимать задачки (как минимум те, которые в видео). Спасибо!
Я стараюсь сначала делать задачи, а затем смотреть ответ. Так вот в третьей задаче, я написал чек следующим образом: def checksize(m, params): w, h, n = params return np.sqrt((w*h) // n) >= m И мне кажется это более правильный ответ, так как при пробных данных W=20, H=10, N=5, максимальная длина одной стороны получается 6.3 при проверке и моя функция выдает 6, что логично. А функция, что ответе дана выдает 5. Think about it (или скажите в чем я могу быть неправ).
Попробуйте на бумаге начертить 10 на 20 и разместить 5 квадратов стороной 6. Там 3 получается только. H = 10, а значит по высоте только 1 квадрат вмещается. По ширине соответсвенно 3 только
Чет не то в задаче с велосипедистами - скорость велосипедистов не изменяется, на 49:45 говорят неверно. 2 - нет никаких убывающих и возрастающих функций на 50:23. Обе функции положения велосипедистов возрастающие - для более быстрого велосипедиста функция растет быстрее, для медленного медленнее 3 - непонятно, какая правая граница для времени
15:55 Задача 1 ну, тут легкое решение (наверное это и есть эффективное математическое решение) 1) найдем треть (минимальное кол-во родителей) для этого (N-K+1)//2 2) если найденная треть больше или равна K, то родителей уже хватает 3) если родителей не хватает: вычтим из трети текущее кол-во родителей и получим ответ решается наверное за O(1)
Согласен с этим решением. Только наверное 2) если найденная треть меньше или равна K, то родителей уже хватает. И ещё наверное в случае K > (N-K+1)//2 мы должны прибавить к общему числу человек (K - ((N - K + 1) // 2 )) * 2 не родителей.
Немного за лектором успеваю, но многое непонятно. Было бы лучше, если б был запуск кода с инпутом или курс на степике с задачами, т.к. контест не открыт.
39:44, разве >= в левом поиске изменить картину? Чтобы выйти не на первый x, а на последний нужно при seq[m] двигать левую границу ( что происходит при правом поиске), при >= как и при > двигается правая граница. Т.е. seq[m] попал на x (впереди есть еще x), но check дает True и левый поиск идет по первому условию и двигается правая граница - соотв. до последнего x уже не добраться.
Да, тоже сначала подумал. Но тут косяк. Если N = 2, size = 5 , H = 5 и W = 10, то тут же сможем оно (на бумаге если начертить, то будет 2 квадрата по горизонтали), а по этому условию не подойдёт. Так что не подходит оно
`check` это параметр функции, так называемый callable - то есть метод, который будет вызван для проверки условия. checkendowement - это пример функци для этого параметра. Т. е. Пример вызова может быть ``` lbinsearch(0, 25, 'checkendowement', [15, 3]) ``` Я бы сказал, что в лекции не хватает слайдов с примерами применения описанных функций - так было бы более наглядно
на 33.02 зачем нам вообще возвращать длину массива, если сама l нам будет выдавать правильный ответ? если нет числа в массиве, то l дойдёт до конца и её индекс будет равен длине массива.
Так себе примеры применения бинарного поиска: 1. Не пишите свои парсеры логов, используйте готовые решения. Своё нужно писать только если вас, по каким-то причинам, не устраивает готовые. И эти причины должны быть достаточно весомые. 2. Не пишите свои калькуляторы кредитов, вы можете ошибиться в каких-то коэфецианетах или что-то не учесть и попасть на деньги. И НИКОГДА не бирети ипотеки под будущие доходы. НИКОГДА, слышите. Автор, чему ты учишь молодежь.
@@WhiteBriar А почему вы не хотите подумать, что таких городов может быть несколько? Города растут, укрупняются. То что сейчас районы - когда то давно были независимые пункты на расстоянии N км. И улицы именовали без оглядки друг на друга.
![CHILE vs. BRASIL [1-2] | RESUMEN | ELIMINATORIAS SUDAMERICANAS | FECHA 9](http://i.ytimg.com/vi/5ObJt_71AYc/mqdefault.jpg)
Это не лекция, а произведение искусства. Лектор - душевный. Спасибо 👏
Душный. Т9
Я сижу такой уверенный, что уж я то точно смогу изи написать бинарный поиск. Дошел до задачки про совет школы. Написал за 15 минут на бумажке решение через бинарный поиск. Думаю дай ка напишу реализацию на джаве. И 4 гребаных часа промучался ))) теперь я сижу уже не такой уверенный, но довольный собой)
0:06 Интро
1:05 Теория
4:08 Реализация бинпоиска
8:55 Как проверить реализацию?
15:55 Задача 1
18:00 Решение 1
22:28 Задача 2
23:42 Решение 2
27:24 Задача 3
29:02 Решение 3
29:56 Задача 4
32:02 Решение 4
35:10 Задача 5
35:15 Решение 5
40:00 Задача 6 (из жизни!)
41:58 Решение 6 + поиск по вещественными числам
47:58 Задача 7
48:42 Решение 7
54:58 Q&A
вообще огонь. Я до этого бин поиск представляла себе исключительно в форме поиска одного того самого элемента в массиве, а вот такая подача про хороший-плохой, левый и правый -- это вообще огонь, начала реально понимать задачки (как минимум те, которые в видео). Спасибо!
Спасибо за курс видео по алгоритмам! Узнал много нового и закрепил то, что уже знал
Спасибо большое за полезную и информативную лекцию !!!
Ура, это Густокашин. Я уже успел полюбить его объяснения на курсе по введению в cpp.
Желательно для таких видео делать оглавление с закладками, например на каждую задачу.
Я стараюсь сначала делать задачи, а затем смотреть ответ. Так вот в третьей задаче, я написал чек следующим образом:
def checksize(m, params):
w, h, n = params
return np.sqrt((w*h) // n) >= m
И мне кажется это более правильный ответ, так как при пробных данных W=20, H=10, N=5, максимальная длина одной стороны получается 6.3 при проверке и моя функция выдает 6, что логично. А функция, что ответе дана выдает 5. Think about it (или скажите в чем я могу быть неправ).
Попробуйте на бумаге начертить 10 на 20 и разместить 5 квадратов стороной 6. Там 3 получается только. H = 10, а значит по высоте только 1 квадрат вмещается. По ширине соответсвенно 3 только
Благодарю за лекцию!
Чет не то в задаче с велосипедистами - скорость велосипедистов не изменяется, на 49:45 говорят неверно.
2 - нет никаких убывающих и возрастающих функций на 50:23. Обе функции положения велосипедистов возрастающие - для более быстрого велосипедиста функция растет быстрее, для медленного медленнее
3 - непонятно, какая правая граница для времени
Лучше чем Павел Марвин, еще никто не объяснил бинпоиск :(
19:07 "обычно в школах не бывает миллиард родителей"
15:55 Задача 1
ну, тут легкое решение (наверное это и есть эффективное математическое решение)
1) найдем треть (минимальное кол-во родителей) для этого (N-K+1)//2
2) если найденная треть больше или равна K, то родителей уже хватает
3) если родителей не хватает: вычтим из трети текущее кол-во родителей и получим ответ
решается наверное за O(1)
Согласен с этим решением. Только наверное 2) если найденная треть меньше или равна K, то родителей уже хватает. И ещё наверное в случае K > (N-K+1)//2 мы должны прибавить к общему числу человек (K - ((N - K + 1) // 2 )) * 2 не родителей.
@user-gh2sq4ps4o Как вы пришли к формуле (N-K+1)//2?
Иногда формулу придумать сложнее, чем написать бинпоиск
29:26 , кто-нибудь, дообъясните, пожалуйста, какие здесь левая и правая границы?
upd: вроде разобралась сама: l = 1; r = min(w, h)
Немного за лектором успеваю, но многое непонятно. Было бы лучше, если б был запуск кода с инпутом или курс на степике с задачами, т.к. контест не открыт.
checkParams мягко говоря не обязательно передавать в функцию, лямбда уже должна сама содержать эти параметры
39:44, разве >= в левом поиске изменить картину? Чтобы выйти не на первый x, а на последний нужно при seq[m] двигать левую границу ( что происходит при правом поиске), при >= как и при > двигается правая граница. Т.е. seq[m] попал на x (впереди есть еще x), но check дает True и левый поиск идет по первому условию и двигается правая граница - соотв. до последнего x уже не добраться.
Подскажите, пожалуйста, в задаче 3 (про стикеры) можно было бы использовать внутри функции check такое соотношение
```
(size * N
Да, тоже сначала подумал. Но тут косяк. Если N = 2, size = 5 , H = 5 и W = 10, то тут же сможем оно (на бумаге если начертить, то будет 2 квадрата по горизонтали), а по этому условию не подойдёт. Так что не подходит оно
А почему в задаче 2 (про Юру и задачи) вы берете l = 0, а не l = 1. Нумерация дней же с 1 должна начинаться. Поясните, пожалуйста @Академия Яндекса
А, ответ уже есть в лекции))
блин тут, что не будет пиццы? эх надо послать младшего брата за ней
тем не менее, какой N выбрал Юра?)
забавно что большинство задач с лекции и контеста на эту тему встречались на рукод фестивале...
Очень непонятно, есть функция check, а мы задаем какую то checkendowement в первой задаче.
`check` это параметр функции, так называемый callable - то есть метод, который будет вызван для проверки условия. checkendowement - это пример функци для этого параметра.
Т. е. Пример вызова может быть
```
lbinsearch(0, 25, 'checkendowement', [15, 3])
```
Я бы сказал, что в лекции не хватает слайдов с примерами применения описанных функций - так было бы более наглядно
В задаче про велосипедистов ни одна функция нигде не убывает.
я пол видео не понимал что такое там params и chechparams, а потом как понял
на 33.02 зачем нам вообще возвращать длину массива, если сама l нам будет выдавать правильный ответ? если нет числа в массиве, то l дойдёт до конца и её индекс будет равен длине массива.
к задаче 4, а если искомое число меньше, чем наименьшее число в последовательности, то вернется индекс 0 !!!
Блин, ничего не понял с хорошими и плохими случаями
00:29:20
Так себе примеры применения бинарного поиска:
1. Не пишите свои парсеры логов, используйте готовые решения. Своё нужно писать только если вас, по каким-то причинам, не устраивает готовые. И эти причины должны быть достаточно весомые.
2. Не пишите свои калькуляторы кредитов, вы можете ошибиться в каких-то коэфецианетах или что-то не учесть и попасть на деньги. И НИКОГДА не бирети ипотеки под будущие доходы. НИКОГДА, слышите.
Автор, чему ты учишь молодежь.
Яндекс в такси две улицы в разных районах города с одним названием добавить не могут.
А еще алгоритмам учат...
+++ и в такси еще деньги берут, могли бы за бесплатно возить. В гугле такси вообще нет, зачем-то свое придумали
Lion King, что за город такой, где две улицы с одинаковым названием в разных районах?
@@WhiteBriar А почему вы не хотите подумать, что таких городов может быть несколько?
Города растут, укрупняются. То что сейчас районы - когда то давно были независимые пункты на расстоянии N км. И улицы именовали без оглядки друг на друга.
Даже на скорости х2 смотреть невозможно:-/ примените уже бинарный поиск для вырезания пауз в речи.
Я тоже меньше чем на х4 алгоритмы не воспринимаю
я х18 смотрю, вообще норм
А мне по обложке сразу всё понятно
по названию видео все понял
я понял