МИШЕНЬКА УЧАСТВОВАЛ В ПОЛУФИНАЛЕ ICPC! РАЗБОР КРАСИВЫХ ЗАДАЧ ОТ ГРОССМЕЙСТЕРА ПРОГРАММИРОВАНИЯ!

Автор обложки - Михаил Абрамович из Поступашек!!
Спасибо ему огромное !!!!
🎯 Поддержать популяризацию математики на Бусти:
boosty.to/savvateev
Наши ресурсы:
Телеграм-канал о проблемах образования: t.me/alexei_savvateev
Для добровольцев спасения школы: [e-mail]
Сайт: роднаяшкола.рф/, тег: #роднаяшкола
alexei_savvateev
/ aleksey_savvateev / savvatan
savvateev.livejournal.com
savvateev.xyz
t.me/savvateev_xyz

[@user-jd6uz5si2f]

Красавчики! Ниче не понятно в основном, но смотреть прикольно! Оч хорошо, что у нас есть такие хорошие люди!!)

[@zolotistbly1192]

Спасибо за видео!

[@user-tb4un1ou9y]

Очень рады за вас,

[@djaff9]

Отличное видео, много полезной информации👍🏻

[@user-qe6cf1ob8l]

Спасибо за видео, очень сильно мотивирует.

[@slavus54]

Спасибо за интересный разбор данных задач, Мише отдельный респект!

[@user-lk6ly4qt3q]

Ждём больше разборов интересных задач по программированию от Миши!

[@Rigik]

Поздравляем! Молодец! 👍👍👍

[@ritagafurova912]

Мало,что поняла,но было интересно)Восторгаюсь!

[@user-vy5rj4br8t]

Вы такие волшебные! Одно удовольствие смотреть,но много чего не понятно 😁

[@Lida_Kuytunen]

Прздравляем. Удачи!!!

[@ElenaOgorodnikova]

Веселые и умные ребята, приятно посмотреть и послушать 👏

[@Sergei_Goncharov]

Веселье зашкаливает!

[@user-pr4py5oo8n]

Молодцы!!!

[@user-ci6wo9in6k]

Поздравляю Мишу. Продолжай грызть гранит науки и отстаивай честь нашего образования

[@user-he3tt6ly5x]

Поздравляю.

[@user-tb4un1ou9y]

Поздравляем

[@zaipoprygai550]

"Кумир одиннадцатиклассниц" !! Браво! Так держать!) 🙂

[@Pravdorub1201]

Увлечённые люди своим делом. Приемственность поколений. Мечта...

[@pavelmikhailyuk9071]

В разминочной задаче надо ввести ограничение n > 1 или разобрать случай n=1 отдельно :) В задаче с городами и дорогами можно удалять ребра: сначала ребро между вершинами со степенью n-1 и n-2(-1 от максимального K), потом ребра между n-1 и n-2, n-2(-2) и т.д.

[@nikolayplatnov5148]

Молодец. Весь в папу!

[@Tamara-zg4ws]

Здорово! Молодец!

[@user-si8bi6ns3o]

Супер, уважуха !!!

[@zerdturov62]

Маткультспасибо!

[@valk8738]

Мои поздравления!!! Просто зависла на вашем видео! Такое единение папы и сына! Столько эмоций! Если бы все «ботаники» были такие же чудесные как вы, мир бы стал намного веселее и добрее 😊

[@---658]

#3. Приятно видеть. Как Миша в плане напряжённости? Слышал,что бывает плохо первокурсникам, в смысле большой нагрузки

[@sashabelyy7528]

по поводу H. На контесте была идея тыкать в нижний левый угол r1, верхний левый угол r2, верхний правый угол r3. Тогда мы можем с помощью ответов ближе дальше установить в какой четверти квадрата лежит точка. Ну например r1,r2 -> ближе (значит точка находится в верхней половине квадрата), r3-> дальше значит искомая точка находится в верхней левой половине. Таким образом можно и дальше "сужать" поиска.

[@Irades]

Класс!)

[@user-ng8rg7mt3z]

Бородатые Савватеевы прекрасны

[@yurifromspb]

А я бы с деревьями сверху вниз шёл: найти число, разбивающее список на два всегда одинакового состава, и далее рекурсивно. О, так и в разборе 43:55 :) (а за кукуареку надо добавлять метку not safe for work)

[@urs2598]

Мишенька, молодец

[@igorlobachev2964]

Миша молодец. ...Удивительное несовпадение фамилии и внешности....

[@rib_ka]

Мишенька очень похож на актера из Зюд Тироля Тобиас Моретти. Офигеть. Прям один в один. Удачи вам.

[@Sergei_Goncharov]

Мне пришёл в голову такой вариант решения задачи с обходом дерева. Наблюдение: во всех рандомных обходах первый и последний элементы - ВСЕГДА листья дерева, причём, заведомо находящиеся по разную сторону от корня дерева. Шаг 0. Создаём список всех узлов - кандидатов на корневую точку. Просто инициализация. Цикл 1. По всем обходам создаём список всех пар краевых листьев. Цикл 2. Вычёркиваем из списка кандидатов все элементы, входящие в эти пары - они заведомо не могут быть корневыми узлами. Цикл 3. По всем обходам... Цикл 3а (вложенный) по всем парам из цикла 1 вычёркиваем из списка все узлы, находящиеся в очередном обходе за пределами, ограничиваемыми текущей парой. Если на очередном шаге после вычёркивания остался только один узел, то цикл можно остановить досрочно - это и есть корневой узел. По окончании у нас либо останется единственный узел - корневой, либо задача имеет более одного решения (недостаточное количество обходов). Найденный корневой узел делит каждый обход ровно на две части, причём одна часть соответствует обходу одной ветви дерева под корнем, другая другой. Таким образом, полученные 2N новых обходов объединяются в две непересекающиеся друг с другом группы из N обходов каждая, которые в свою очередь решаются рекурсивно.

[@strausstraus5147]

Что?))

[@user-ul4uu2mu7k]

Отлично, когда профи рассказывает о том, в чем разбирается. И не лезет туда, где он не силен)))

[@yutatutukyta7190]

Какие же они классные 😂😂😂

[@andreytkachenko2085]

4 утра. А я вспоминаю про графы)

[@IamMelissaRauch]

Давно не виделись

[@wergit-pv2wy]

Где можно найти официальные разборы? уж очень задача про дерево понравилась

[@memedaddyz]

Ржачные ботаники) будущее

[@ubermensch9590]

Всё конечно круто, но вам надо бы пофиксить свет

[@user-sn3hi7yt8m]

прекрасные

[@user-fp2dd9br3z]

Миша просто монстр!!!

[@Valensio]

Миша полу- Савва финал теев ICPC )))))

[@user-ni9tf5yr6m]

Финалтеев - это правда

[@SegantChe]

Я задачу про бинарное дерево решил через поиск корневой вершины. Вероятная сложность получается O(n^2) по Мастер теореме.

[@alexeyshnaider9290]

Не Мишенька, а настоящий Медведь😅

[@egoregor3529]

Расскажите пожалуйста про многомерные матрицы, как вычислить их определитель, ранг, транспонировать.

[@Wddd_off]

Почитай пару книжек о линейной алгебре просто, так гораздо проще будет

[@Sergey-Primak]

58:00 проблемы двоичного поиска НЕТ - если ответ от предыдущего запроса совпадает с текущим, то направление не меняем, если ответы не совпадают, то на следующем шаге меняем направление

[@user-jk1qe6hq7f]

мне сразу пришла идея искать корень и разбивать на два поддерева - разделяй и властвуй. Вероятно возможен код с рекурсией только надо придумать как выводить результат. А корень во всех обходах стоит между двумя поддеревьями только от обхода к обходу поддеревья могут меняться местами. Для поиска корня надо просмотром всех обходов надо найти такую вершину позиция которой во всех обходах находится на постоянном удалении от краев.

[@user-ni9tf5yr6m]

Кратко про задачу "К" 23:11 23:21

[@sevakh777]

👍🏻👍🏻👍🏻

[@user-bj5ln3ee4f]

Последняя задача подобие морского боя с. Однопалатным

[@Star-pv6po]

Можно с Мишей как-то задачи разбирать по ACM ICPC прошлых лет? Куда писать? Думаю, разбор всем интересен был

[@maksimkardash6402]

Обычно стримера за заказанный стрим денег вносят, готова?

[@TeLePeReDoZiK]

Я задачу с деревом решил так, при любом обходе сумма чисел слева и справа от коренного элемента всегда одни и те же. То есть до тройки и после тройки одинаковые суммы. Дальше рекурсия по поиску корня, потом в оставшейся части снова поиск корна, и так далее

[@TeLePeReDoZiK]

Я же не ошибаюсь?

[@alexeyvorobyov9160]

​@@TeLePeReDoZiK Ноемножно неясно из вашего объяснения, что вы называете равными суммами. Сумма левого и сумма правого дерева не равны, но пара сумм чисел слева и справа должны повторяться от одного обхода дерева к другому. Можно даже немножко попроще - посчитать количество чисел слева и справа (размер дочерних деревьев). Эти пары тоже должны повторяться во всех обходах. Если сложить наши два критерия, то очень хорошо можно выделить корень с большой вероятностью. А потом просто спускаться по под-деревьям с теми же критерями. Решение будет O(N logN) в среднем и O(N^2) в худшем случае, когда дерево полностью перекошено в одну сторону.

[@TeLePeReDoZiK]

@@alexeyvorobyov9160 у дерева есть корневой элемент. Верхний, если ориентироваться на пример из видео. Так вот, при случайном проходе попав в одну из веток корневого элемента неизбежно будут посчитаны всё его элементы, а потом уже переход в другую ветку. И обход левой ветки и правой разделяет корневой. А это значит, что в числовой последовательности любого случайного прохода сумма чисел слева и справа от корневого элемента всегда одинаковая. При восстановлении не обязательно будет исследовать все 50 последовательностей, достаточно найти одинаковые суммы в двух элементах и проверить, что с другим элементом суммы не совпадают. Если совпали добавляем третью последовательность. Снова смотрим, если и всё однозначно можно искать глубже, если нет берём ещё один числовой ряд.

[@user-jk1qe6hq7f]

@@TeLePeReDoZiK суммы слева от тройки иногда могут быть такими же как сумма справа от тройки, т.е. тройка(типа корень) случайно разбила дерево на два поддерева с одинаковай суммой. с этим надо что- то делать.

[@TeLePeReDoZiK]

@@user-jk1qe6hq7f это не важно. Главное, что корень найден. А то, что суммы одинаковые лечится одной проверкой, просто взять любое число в одном из деревьев и найти по нему нужное дерево в другом проходе

[@user-im9hb5zc6n]

Лëгонькие задачки, но было интересно)

[@pandalove6795]

1:04:57 я вообще не понял объяснений до этого момента), но радует одно, что я самостоятельно сразу догадался до этого варианта и он наверно самый лучший. Допишу полностью алгоритм решения. Мы ставим точку в (0, 0), потом в (1, 1) получаем ТАКЖЕ или БЛИЖЕ. Дальше опять ставим на (0, 0) и получим или ТАКЖЕ или ДАЛЬШЕ. Если варианты ответа совпали и мы в предыдущий раз получили ТАКЖЕ и сейчас ТАКЖЕ, то точка находится или в (0, 1) или в (1, 0). А если разные, то мы знаем, что последний ответ это 100% ДАЛЬШЕ, а предпоследний 100% БЛИЖЕ. Получается за 3 запроса мы расшифруем язык.

[@user-si6os5sm8m]

Харош!

[@g0nzalezTV]

В задаче с двоичным деревом тоже сразу же пришло в голову более простое решение с поиском корня. И оно основывается на одном максимально элементарном соображении: при любом рандомном обходе корень дерева всегда будет располагаться на одной и той же позиции. Дальше уже дело техники: просто ищем, какое число во всех обходах расположено на одной и той же позиции - это корень. Слева и справа от него свои поддеревья, и в них уже ищем корень рекурсивно при помощи такой же процедуры. Единственное что: левые и правые части в списках могут быть перепутаны местами (в зависимости от того, куда мы сначала пошли в конкретном обходе), поэтому перед следующим шагом рекурсии нужно сперва их перекинуть в нужные корзины. Но, благо, это делается легко, т.к. эти списки будут отличаться только порядком чисел, но не их составом, т.е. легко идентифицируется. Тут, кстати, становится понятно, что деревьев, удовлетворяющих условиям, может быть много: достаточно просто "отразить" какую-нибудь часть дерева относительно её вершины. Обходы останутся такими же) Прикольная задача. Это из той серии, когда само по себе условие кажется каким-то совсем диким и невыполнимым, но стоит додуматься до одной простой мысли - так задача превращается в элементарную. Люблю такое)

[@user-fk3dk6xp7h]

"при любом рандомном обходе корень дерева всегда будет располагаться на одной и той же позиции" Это неверно. Если от корня идут два поддерева размерами например 4 и 8, то мыможем пойти сначала в левую, и корень будет на 5-й позиции, а можем во вторую, и корень будет на 9-й. Это из-за того что обход не классический, а специфический. Но можно заметить что корень будет 5-м либо с начала, либо с конца, и да, тогда можно склепать решение, правда оно будет чуть сложнее.

[@ilyavoznesensky9698]

41:33 🐥

[@olegficsher9534]

В этом видео звучит "чувствую", что сродни интуиции. Есть у уважаемого Савватеева старшего где-нибудь в видео объяснение этого понятия? Кто подскажет?

[@1llaya30]

В Н задаче можно не искать язык Можно пройтись по прямой двоичным поиском чтобы найти конкретную точку откуда исходит перпендикуляр к диагонали на котором лежит ответ Далее пройтись поиском по этому перпендикуляру пока не получим ! Поиск реализуем так: Берем центр стороны Потом центр прямой Потом середину противоположной стороны По изменениям ответа находим конкретную сторону в которую надо двигаться Повторяем пока интервал поиска не сузится до 1

[@slxxxr]

как-то плохо с освещением

[@user-xt6mk9jw2p]

Ничего не понятно , но очень интересно

[@abylayamanbayev8403]

Разминочную удалось решить довольно быстро, в кое-то веки решил задачу быстрее Савватеева: def min_draws(n, a, b): return max(0, n-a-b)

[@vanjka39]

@@DEDUS.ARASAKA в твоём случае, если n=12, a=6, b=6, ничьих 12. Хотя может быть 6 побед 1:0 и 6 поражений 0:1

[@AxanX]

@@vanjka39 почему??? 12-6-6=0. Алгоритм ещё лучше чем у Миши. Они условие проверяли, А у Абылай эффективнее

[@MyName-zm3hr]

n=1, a=5, b=5 - не подходит =) выше в комментария писали, что n=1 надо рассматривать отдельно

[@mishapko9333]

Свет)

[@user-kv6pv3eg5c]

Случайно попал на видеоролик, и , вроде бы, на русском разговаривают, но ни слово понять не могу😅

[@user-fk9xv1qb7r]

Я, видимо, не правильно понял условия первой задачи. Но если правильно, то ответ мне кажется будет ничьи = A+B-N. То есть считаем можем ли в каждом матче уместить хотя бы 1 гол. Если можем, то N/2 в первой половине распределяем А любым способом. Во второй половине B так же распределяем. И получится куча матчей 5:0, и куча 0:5, образно. И ничих минимум, то есть либо 0, либо A+B-N

[@user-wh3yr9wr5q]

Наша элита

[@user-yj3qs3nl9m]

Есть ссылки на задания?

[@_ahsiA]

57:10 Но почему мы не можем извлечь больше информации? После проверки точек 0;0 и 10^6;0, мы отсекаем половину точек вертикальной чертой посередине, после чего можем из получившегося прямоугольника сделать квадрат, отсёкши половину точек горизонтальной чертой через середину, проверив точку 10^6;10^6

[@forever_svin]

Потому надо снова возвращаться к первой точке и заново начинать спрашивать, таких вариантов 40, а надо меньше

[@_ahsiA]

@@forever_svin Я не против, что это не оптимально, но в видео, как мне помнится, сказали, что это нам вообще ничего не даст

[@emperror-il5zq]

Задача про поиск точки очень классная, но у меня решение проще) Тыкаем изначально в 4 точки: (0;0), (1;1), (1;0) и (0;1) Тогда сразу узнаем язык, и количество запросов будет максимум 44 Пока я писал это, Миша рассказал про примерно то же решение

[@user-rq4hi5ez4x]

Ещё не смотрел. Участвовал в четвертьфинал 2019. Интересно что там на более сложной уровне. P. S. Когда смотрел разбор математики кипел иногда, а тут всё понятно. Имхо информатика легче математики. P. S. S. Слух резануло двоичное вместо бинарного, ребёнок вместо потомка. P. S. S. S. Задача b корневой элемент может ли быть записан не на чётном месте. У меня выходит что нет. P. S. S. S. S. Ну мне не нравится что вы в самом начале не тыкнули в одну и туже точку сразу. Конечно из ответов вариант на таком же растояние будет понятен, но так после второго запаса мы можем записать в переменную строго как выглядит ответ равно, а если мы получим ответ равно то у нас тока искомая строго на одной оси находится. Конечно врятли такой случай будет стабильно выходить но он наиболее быстрый. Часть 2. Проверьте логику. Первая точка 0 0. Второй вопрос туда же, получаемая как выглядит ответ равно. Так как точка на целых координатах вопрос3 1.1 тут две ситуации ответ равно который мы знаем или строго ближе. Ну а дальше поиск по квадратам. А точнее даже не на квадраты А сначала по одной оси ищем, в идеале словить ответ равно и тогда точка на срединном Пенпедикуляре, а на линии это простой бинарный поиск.

[@slare5252]

Великолепно! Кстати. Вчера писал первый тур региона по информатике 9-11 класс. Помню раньше вы разбирали ВсОШ (когда участвовал Михаил). Если сможете, пожалуйста разберите регион 2023 года. По моему мнению он был более интересный чем регион 2022 года.

[@PLEER11K]

согл, ждем разбор 4 геомы

[@666satanaaa]

как написал?

[@slare5252]

@@666satanaaa даже 200 баллов не набрал

[@666satanaaa]

@@slare5252 ничего страшного, я в первый раз набрал 140

[@nomfli]

Во второй задаче можно n дольные графы строить. И это победа.

[@nomfli]

Но только в каждой из долей должно быть разное количество вершин. Тогда мы автоматом разобрали все случаи при k меньшем чем количество чисел образующих сумму 1+2+3+4...=n. В любом связном нетривиальном графе количество различных степеней находится в промежутке от 1 до n-1. И в любом случае существуют две вершины с одинаковой степенью k меньше либо равно, чем n-1.

[@nomfli]

Если задать граф следующим образом пусть вершины про нуммерованы числами от 1 до n. И сменжны мёджду собой, когда выполняется условие i+j больше либо равно чем n+l, где l находится в промежутке от 1,...,n-1. При l=1 мы получим граф представленный мишой. А при увеличении l будет образовываться аналогичный граф, но как будто бы без одной вершины (да не очень понятно просто ручками почертите поймёте о чем я) у которой степень будет 0. Но тогда соеденим всеми возможными рёбрами эту вершину и получим верные семейства графов

[@exoticface]

Нечего не понимаю но смотрю

[@purity_one]

А что за Игры Эрнс Хойфа? Что-то не гуглится(

[@Dart-Xeyter]

На самом деле Эренфойхта :)

[@alexzdorovennov4035]

13:02 15:35

[@user-um1hs9mv5i]

Освещение бы грамотно настроить

[@Sergey-Primak]

44:22 - решение не понравилось! поиск корня дерева необходим в решении задачи! статистический подход - настолько слабый, насколько случайна рандомность. поиск корня интересная задача, но пока не дошел, по обходу дерева можно построить минимум два различных дерева

[@High-Yield]

Нихера не понятно,но очень интересно

[@Virviil]

40:00 - 11 6 4 быть не может и НА ДОСКЕ ЗАПИСАНО 11 6 4 😂

[@konstantink8045]

Что со светом?

[@user-jt1yy8rx9v]

Испания в 2010 была чемпионом мира)

[@Alex51191]

Только теперь понял, почему я не математик. Я никогда не интересовался футболом.

[@bula312kingdoms]

Помнится задача а была простой. Почему футбол в полуфинале? Там же сплошные гробы. И как же нас крепили по времени О. Двоичный поиск за 40 запросов из 60 звучит вполне реально. Решение через тервер - тот инструмент которого мне не хватало в юности. Теперь начинаю понимать как решались некоторые гробы. К сожалению у нас практически не было математической базы

[@user-ez4tl9uz5z]

так если у нас 13 забитых и 13 пропущенных то они могут выиграть 13 раз со счетом 1 0 и проинрать олин раз со счетом 0 13

[@user-tf5jt3sj7t]

Ребята кто-то оммо пишет 5того ?

[@user-oj9xz7os6t]

Я таки не понял, а когда Мишенька поедет на войну?

[@user-ox5xl9vg8n]

Зачем?

[@user-oj9xz7os6t]

@@user-ox5xl9vg8n как зачем? Собирать русские земли. Сам Алексей эту идею всеми силами поддерживает.

[@user-ox5xl9vg8n]

@@user-oj9xz7os6t ты не ответил на вопрос

[@user-yp5js6eg1v]

А схуяли он должен поехать? Он не боец, он математик. Я за него поехал. Еще вопросы есть?

[@user-oj6di6tf5l]

Решите задачу. Росстат сообщает, что автомобили в среднем подорожали за год на 24%. При этом иномарки на 40%. На сколько подорожали отечественные автомобили, если принять, что их доля составляет 50%?

[@user-ni9tf5yr6m]

8% или нерешаемо, раз мы не знаем долю общей стоимости

[@user-oj6di6tf5l]

@@user-ni9tf5yr6m Ну 8 так 8, Росстат же врать не станет😁

[@chilokolich3971]

Хорошую религию придумали "евреи": кто не с нами - того не существует. Ха-Ха-Ха * У Трушина - БОМБА! А Мишеньки-Монстра нет в обсуждении задачи про минимизацию. Не знаю, в какую сторону смотрит Ломоносов, на физфак или на химфак, но к мехмату он повернулся задом! *

[@sejum_4421]

Дефолт з дескретки...

[@ivanfuture8873]

Помнится Савка кричал пару лет назад. "Царь собирай земли!". Почему Мишенька на ICPC, а не на СВО земли собирает? Раз Саватеев так хотел крови и империю, надо чтобы семья поучаствовала лично.

[@animehighlights4217]

Студентов никто не призывал

[@ivanfuture8873]

@@animehighlights4217 Добровольцем. А то папка кровь чужими руками загребает.

[@AxanX]

Дааа, как то не красиво. Научные люди не должны влезать в политику, особенно кровавую. Сами запросто могут попасть

[@vit3060]

Эксперименты со светом с целью создать атмосферу фильма ужасов или просто осветитель сломался? У вас больше платных 200 подписчиков, уж наскребите на софтбокс и пару микрофонов с петличкой.

[@urioxon6889]

в задаче Н 54:17 вердикт изменился, но не стал понятен!!! мы не узнали какое слово на тарабарском ДАЛЬШЕ, а какое БЛИЖЕ!!! Если в условии сказано что поле клеточное, а х и у целые - то первой точку надо брать (1:1), а второй точку (0:0) - вердикт после точки (0:0) будет ДАЛЬШЕ, а потом уже горячо-холодно, причём очень легко если ДАЛЬШЕ мы уже знаем при варианте когда жюри выбрали (1:0) или (0:1) мы получим два одинаковых вердикта после моих первых действий, но при поле 10^6 такая вероятность крайне мала

[@andreadipre7384]

Миша как тебе зовут в инстаграме?

[@djaff9]

Вы еврей?

[@user-rb8ux1no6j]

таки есть немного

[@artemglass]

@@user-rb8ux1no6j Бокер тов

[@user-jt3rl9wg1x]

Не знаю сколько курить надо, чтоб это решать