image_2022-02-06_13-38-26.png
46.7 KB
Сегодня слил закл ВП. Очень обидно, так как не успел заслать D (скорее всего на фулл). Ну и не придумал простую идею в Eшке на +17.
В целом задачи вроде норм, но слабоваты тесты.
A) математика
B) бинпоиск + 2 указателя
C) перебор (у меня фактически квадрат, но работает за 0.59)
D) сначала заслал лажу за O(n^2*logn), получил 36, потом пытался сортить строки и от порядка искать ближайших, но wa получал (как оказалось некоторые такое на 100 сдали, так что у меня руки кривые). Далее пытался сортить по префиксу и суффиксы и от них искать ближайших, но чуть чуть не успел отладить. Возможно потерял на этом 64 балла
E) гроб. На 22 - квадрат, на 39 - счетчик элементов в мапе
Жалко конечно, но призера кажется возьму. А это хотя бы бви в питерскую вышку (по словам знакомых норм место, но поизучаю получше, но в крайнем случае можно будет проще перевестить в мск вышку, чем из другого вуза)
В целом задачи вроде норм, но слабоваты тесты.
A) математика
B) бинпоиск + 2 указателя
C) перебор (у меня фактически квадрат, но работает за 0.59)
D) сначала заслал лажу за O(n^2*logn), получил 36, потом пытался сортить строки и от порядка искать ближайших, но wa получал (как оказалось некоторые такое на 100 сдали, так что у меня руки кривые). Далее пытался сортить по префиксу и суффиксы и от них искать ближайших, но чуть чуть не успел отладить. Возможно потерял на этом 64 балла
E) гроб. На 22 - квадрат, на 39 - счетчик элементов в мапе
Жалко конечно, но призера кажется возьму. А это хотя бы бви в питерскую вышку (по словам знакомых норм место, но поизучаю получше, но в крайнем случае можно будет проще перевестить в мск вышку, чем из другого вуза)
Интересный факт:
1) финал спбгу по информатике будет 13 февраля в 10:00-15:00
2) 2-й отбор на иоип будет 13 февраля в 14:00-19:00
Я попробую поучаствовать в обоих (да, закончу спбгу на час раньше)
1) финал спбгу по информатике будет 13 февраля в 10:00-15:00
2) 2-й отбор на иоип будет 13 февраля в 14:00-19:00
Я попробую поучаствовать в обоих (да, закончу спбгу на час раньше)
Forwarded from что (Федор Ромашов)
гениальный раунд от владимира новикова, все пишем ребята https://codeforces.com/blog/entry/99776
Codeforces
Codeforces Global Round 19
Hello, Codeforces! (づ｡ ◕‿‿ ◕｡)づ ❤
Forwarded from Yet another upd
Для тех, кто пишет СПбГУ, хотелось бы напомнить, что по регламенту вы должны пойти тестирование на сайте https://talant.spbu.ru до 10 утра 12 февраля. Логин и пароль нужно использовать с отборочного (такой же, какой вы использовали при входе в тестирующую систему)
Уже через 2 недели будет инд тур по НТИ ИИ (расписание https://ntcontest.ru/participants/schedule/#final-stage-schools), А я как бы хотел выкладывать всякие полезные посты по олпроге. Так как часто хотелось бы видеть посты (на 90% скопированные откуда-нибудь) и контесты на соответствующие темы?
Какие темы важнее? (олпрога)
Anonymous Poll
30%
Простые (бинпоиск, жадники, сканлайны)
57%
Базовые (деревья, графы, другие структуры, примеры динамики)
13%
Относительно продвинутые (комба, геома, строки)
Сегодня я слил СПбГУ по инфе
100+100+100+60+58+0 = 418 / 600
Первые 3 часа жестко тупил, сдал только Ашку и Eшку на 58 (там вообще халявно)
Потом вроде собрался, заметил, что в D надо посчитать просто (n+1)! по простому модулю, написал за линию (оказывается можно было пользоваться справочниками, если они скачаны заранее, но я этого не знал, а так бы скачал себе peltorator book и emaxx, нашел бы код для факториала за sqrt(n) и сдал бы)
Далее стал думать на конструктивом в С. Долго думал, всякую лажу писал. В итоге зашло такое:
если нулей больше чем единиц - заменяем все на ?
если единиц больше (или равно нулям) - первые n/2 единиц заменяем на ?
Далее стал смотреть 3-х страничное условие Bшки.
Тоже долго тупил, но в конечном итоге сдал. Достаточно было заметить, что если идти с конца, то после любого переворота все часы будут в нулевом состоянии - тогда просто переворачиваем, если i+1 раз часы просигналили
Еще пытался в Ешке что то вроде корневой придумать, но так и не придумал.
Жалко конечно что слил (побед спбгу мог бы дать мне бви на ПИ ВШЭ, не ПМИ конечно, но тоже неплохо, но с такими баллами шансов на победителя нет)
100+100+100+60+58+0 = 418 / 600
Первые 3 часа жестко тупил, сдал только Ашку и Eшку на 58 (там вообще халявно)
Потом вроде собрался, заметил, что в D надо посчитать просто (n+1)! по простому модулю, написал за линию (оказывается можно было пользоваться справочниками, если они скачаны заранее, но я этого не знал, а так бы скачал себе peltorator book и emaxx, нашел бы код для факториала за sqrt(n) и сдал бы)
Далее стал думать на конструктивом в С. Долго думал, всякую лажу писал. В итоге зашло такое:
если нулей больше чем единиц - заменяем все на ?
если единиц больше (или равно нулям) - первые n/2 единиц заменяем на ?
Далее стал смотреть 3-х страничное условие Bшки.
Тоже долго тупил, но в конечном итоге сдал. Достаточно было заметить, что если идти с конца, то после любого переворота все часы будут в нулевом состоянии - тогда просто переворачиваем, если i+1 раз часы просигналили
Еще пытался в Ешке что то вроде корневой придумать, но так и не придумал.
Жалко конечно что слил (побед спбгу мог бы дать мне бви на ПИ ВШЭ, не ПМИ конечно, но тоже неплохо, но с такими баллами шансов на победителя нет)
DL летописец
Скоро начнутся финалы перечневых олимпиад, поэтому вот маленький календарик тех, в которых я собираюсь участвовать (фактически это просто напоминалка, но вдруг кому-то поможет не забыть что-нибудь важное) Отборы: ✅МОШ (информатика) - 320/500 проход ✅ ИОИП…
Я кстати возможно не буду писать всесиб 🤡, так как в моем регионе нет площадок (ехать далеко до ближайшей) + там сразу после этого финал НТО ИИ, а мне нужно получше подготовиться.
UPD: я кстати обновил свой календарик (закреп) - добавил ИОИП, добавил даты открытки
UPD: я кстати обновил свой календарик (закреп) - добавил ИОИП, добавил даты открытки
DL летописец
Раз уж большинство проголосовали за домашки, то держите ссылку на группу где я буду писать конспекты и добавлять тематические контесты (не забудьте выбрать роль "участник, если хотите решать задачи"): https://codeforces.com/group/a1W1cUWddJ UPD: прошу строго…
Наконец то мои руки дошли до первого поста и до первого контеста, завтра утром уже можно будет решать)
Я постарался добавить интересных задач, одну даже сам придумал и подготовил))
Разбор будет завтра около полуночи.
Я постарался добавить интересных задач, одну даже сам придумал и подготовил))
Разбор будет завтра около полуночи.
Анонс: далее будет пост про структуры данных, а именно базовое ДО и префсуммы. Потом еще будет немного про графы и, наконец, 1-2 прошлогодних инд тура.
Давно постов не было...
Короче сегодня поговорим о теории вероятности, а также об одном популярном виде задач на теорию вероятности(и геометрию, хехехе)
Сразу замечу, что существует два вида событий(в данном контексте - исходов) относительно друг друга - зависимые и независимые. Зависимые перемножаем, независимые складываем. Выпадение определенного числа на кубике - независимое от других чисел событие, и сумма всех независимых событий равна единице. При броске двух кубиков выпадение одинаковых чисел - совокупность шести независимых событий: на обоих числах выпали одинаковые числа. Каждое такое событие состоит из двух зависимых событий: на первом кубике выпало X и на втором кубике выпало X. Тогда вероятность того, что выпадет две единицы равна (1/6)*(1/6)=1/36, вероятности выпадения двух двоек, троек и т.д., так же равна 1/36 для каждого числа. Тогда вероятность события "выпали одинаковые числа" равна 6*(1/36)=1/6 (Ага, это происходит довольно часто!)
Для начала такая задача: на планете Плюк среди жителей принята цветовая дифференциация штанов, и на один из пиров были приглашены N Плюкчан: двое в желтых штанах и N-2 в фиолетовых штанах. Какова вероятность того, что носители желтых штанов будут сидеть рядом за круглым столом?
Решение:
Посадим одного носителя желтых штанов за стол, теперь осталось __N-1__ позиция, на которую можно усадить второго носителя. Заметим, что существует ровно две позиции, соседних с позицией первого, вероятность того, что он окажется с одной из сторон - 1/(N-1), а поскольку позиций две - вероятность того, что они будут соседями равна 2 x (1/(N-1))=2/(N-1)
Задача два: в модном вузе MGIMO на кафедре политологии, в новой, модной уменьшенной аудитории, находиться ровно один вытянутый стол, за которым сидят N студентов, среди N студентов всегда найдется двое студентов с голубыми волосами, и студентам (как всегда) слишком лень слушать лекцию, и один из студентов решил посчитать вероятность того, что двое голубоволосых студентов сядут рядом. К несчастью он гуманитарий, и у него ничего не вышло. Помогите студенту найти эту вероятность.
Решение:
Заметим, что если убрать из выбора для первого студента два крайних места, то будут работать рассуждения прошлой задачи, поместив на любое из этих N-2 мест первого студента, второй может занять любое из N-1 оставшихся места, среди них только два подходят ему, соответственно вероятность того, что он будет соседом равна 2/(N-1).
Но, так как мы выбрали определенные места для первого студента, эта вероятность правильна только лишь если первый занял эти места, а вероятность такого события составляет (N-2)/N, соответственно вероятность соседства равна {(N-2)/N} x {2/(N-1)}
Рассчитаем вероятность соседства для случаев когда первый занял крайнее место, вероятноcть этого составляет 2/N. Теперь второму можно сесть только с одной стороны, а значит вероятность равна 1/(N-1). Поскольку это последовательные события - перемножим вероятности, получим (2/N) * {1/(N-1)}
Теперь найдем суммарную вероятность наших двух независимых событий: [{(N-2)/N} x {2/(N-1)}] + [(2/N) * {1/(N-1)}]=... (читатели сами могут сократить данное выражение и получить красивую формулу)
Короче сегодня поговорим о теории вероятности, а также об одном популярном виде задач на теорию вероятности(и геометрию, хехехе)
Сразу замечу, что существует два вида событий(в данном контексте - исходов) относительно друг друга - зависимые и независимые. Зависимые перемножаем, независимые складываем. Выпадение определенного числа на кубике - независимое от других чисел событие, и сумма всех независимых событий равна единице. При броске двух кубиков выпадение одинаковых чисел - совокупность шести независимых событий: на обоих числах выпали одинаковые числа. Каждое такое событие состоит из двух зависимых событий: на первом кубике выпало X и на втором кубике выпало X. Тогда вероятность того, что выпадет две единицы равна (1/6)*(1/6)=1/36, вероятности выпадения двух двоек, троек и т.д., так же равна 1/36 для каждого числа. Тогда вероятность события "выпали одинаковые числа" равна 6*(1/36)=1/6 (Ага, это происходит довольно часто!)
Для начала такая задача: на планете Плюк среди жителей принята цветовая дифференциация штанов, и на один из пиров были приглашены N Плюкчан: двое в желтых штанах и N-2 в фиолетовых штанах. Какова вероятность того, что носители желтых штанов будут сидеть рядом за круглым столом?
Решение:
Решение:
Но, так как мы выбрали определенные места для первого студента, эта вероятность правильна только лишь если первый занял эти места, а вероятность такого события составляет (N-2)/N, соответственно вероятность соседства равна {(N-2)/N} x {2/(N-1)}
Рассчитаем вероятность соседства для случаев когда первый занял крайнее место, вероятноcть этого составляет 2/N. Теперь второму можно сесть только с одной стороны, а значит вероятность равна 1/(N-1). Поскольку это последовательные события - перемножим вероятности, получим (2/N) * {1/(N-1)}
Теперь найдем суммарную вероятность наших двух независимых событий: [{(N-2)/N} x {2/(N-1)}] + [(2/N) * {1/(N-1)}]=... (читатели сами могут сократить данное выражение и получить красивую формулу)
👍1
И наконец рассмотрим задачу с геометрией: В тире на стене закреплен квадратный лист со стороной 2 метра, в середине которого нарисована окружность радиусом 1 метр, Вася играет с другом в игру, они один раз стрелают в середину мишени, Васе для победы нужно, что бы пуля попала в круг, а Пете для победы нужно попадание в квадрат, но не в круг. К несчастью пистолет - игрушечный, и место попадания пули СОВЕРШЕННО не зависит от навыков стрелка и цели, которую он определил, однако она всегда попадает в лист. Помогите Васе и Пете найти вероятность выграть в этой игре.
Решение
Заметим, что с нашим случайным пистолетом - вероятность попадания пули внутрь курга равна отношению ВСЕХ возможных точек внутри окружности ко ВСЕМ точкам листа. К счастью, совокупность всех точек можно определить как площадь фигуры (внезапно оказалось, что если взять мельчайшую точку, то их поместиться количество, прямо пропорциональное площади).
Тогда вероятность попасть в круг равна S(круга)/S(листа)=(1м^2 x 3.14159...)/(2м^2)=pi/4
Вероятность же попасть в лист, согласно условию, равна единице, пуля всегда попадает в него. Тогда вероятность победы Васи равна pi/4, а вероятность победы Пети равна 1-pi/4.
Это число можно найти двумя путями, можно заметить, что площадь всего квадрата равна 4, а площадь круга pi, тогда площадь квадрата без круга равна 4-pi, а площадь всего листа 4, соотвественно вероятность равна (4-pi)/4 = 1-(pi/4).
Другой путь - понять, что выигрыш Пети - есть проигрыш Васи и наоборот, соотвественно суммарная вероятность победы Васи и победы Пети равна единице. Теперь просто вычитаем из 1 вероятность победы Васи (pi/4) и получаем вероятность победы Пети 1-(pi/4)
P.S. Существует метод приближенного поиска площади какой-либо фигуры, для которой мы можем для случайной точки (например по расстоянию от центра) определить, попала ли она в искомую фигуру, или нет. Через определенное количество итераций мы можем определить площадь искомой фигуры как отношение попавших точек ко всем использованным, умноженное на площадь фигуры, в которую мы поместили искомую и "бросали" в нее точки. (Метод Монте-Карло)
Решение
Заметим, что с нашим случайным пистолетом - вероятность попадания пули внутрь курга равна отношению ВСЕХ возможных точек внутри окружности ко ВСЕМ точкам листа. К счастью, совокупность всех точек можно определить как площадь фигуры (внезапно оказалось, что если взять мельчайшую точку, то их поместиться количество, прямо пропорциональное площади).
Тогда вероятность попасть в круг равна S(круга)/S(листа)=(1м^2 x 3.14159...)/(2м^2)=pi/4
Вероятность же попасть в лист, согласно условию, равна единице, пуля всегда попадает в него. Тогда вероятность победы Васи равна pi/4, а вероятность победы Пети равна 1-pi/4.
Это число можно найти двумя путями, можно заметить, что площадь всего квадрата равна 4, а площадь круга pi, тогда площадь квадрата без круга равна 4-pi, а площадь всего листа 4, соотвественно вероятность равна (4-pi)/4 = 1-(pi/4).
Другой путь - понять, что выигрыш Пети - есть проигрыш Васи и наоборот, соотвественно суммарная вероятность победы Васи и победы Пети равна единице. Теперь просто вычитаем из 1 вероятность победы Васи (pi/4) и получаем вероятность победы Пети 1-(pi/4)
P.S. Существует метод приближенного поиска площади какой-либо фигуры, для которой мы можем для случайной точки (например по расстоянию от центра) определить, попала ли она в искомую фигуру, или нет. Через определенное количество итераций мы можем определить площадь искомой фигуры как отношение попавших точек ко всем использованным, умноженное на площадь фигуры, в которую мы поместили искомую и "бросали" в нее точки. (Метод Монте-Карло)
DL летописец
Наконец то мои руки дошли до первого поста и до первого контеста, завтра утром уже можно будет решать) Я постарался добавить интересных задач, одну даже сам придумал и подготовил)) Разбор будет завтра около полуночи.
Разбор контеста принял ислам. По двум причинам:
1) особо никто не решает
2) 5/6 задач можно нагуглить
Так что к инд туру я только сделаю контест с задачами прошлого года.
Если будет настроение, разберу интересные применения префиксных/суффиксных структур (не суффмасс, а префиксные суммы и подобные штуки)
1) особо никто не решает
2) 5/6 задач можно нагуглить
Так что к инд туру я только сделаю контест с задачами прошлого года.
Если будет настроение, разберу интересные применения префиксных/суффиксных структур (не суффмасс, а префиксные суммы и подобные штуки)
Forwarded from Календарь олимпиад по информатике
Добавлена последняя задача Е в МОШ 10-11. Больше задачи добавляться не будут. Тур длится до 28 февраля включительно.