Штош, пришла пора писать математику.
Одна из самых простых идей в олимпиадной математике - идея раскрасок.
Рассмотрим её на примере.
Задача:
Есть поле 8x8 клеток с двумя вырезанными углами, можно ли его полностью замостить плитками домино(2х1 клетку)?
Решение:
Раскрасим таблицу в шахматном порядке (не спроста же 8х8 :) )
Тогда одна плитка домино закрывает клетки двух цветов, одну белую и одну черную, не зависимо от положения на доске.
Посчитаем количество цветов на доске: черных - 32, белых - 30, но тогда у нас после закрытия всех белых клеток у нас останется две непокрытых черных. Доминошка не покрывает их, а значит они останутся пусты.
Ответ: Нет, нельзя.
Домашнее задание: Можно ли покрыть доску 8х8 Г-образными плитками (плитки можно вращать и переворачивать)?
Решения можно писать в комментарии
Одна из самых простых идей в олимпиадной математике - идея раскрасок.
Рассмотрим её на примере.
Задача:
Есть поле 8x8 клеток с двумя вырезанными углами, можно ли его полностью замостить плитками домино(2х1 клетку)?
Решение:
Раскрасим таблицу в шахматном порядке (не спроста же 8х8 :) )
Тогда одна плитка домино закрывает клетки двух цветов, одну белую и одну черную, не зависимо от положения на доске.
Посчитаем количество цветов на доске: черных - 32, белых - 30, но тогда у нас после закрытия всех белых клеток у нас останется две непокрытых черных. Доминошка не покрывает их, а значит они останутся пусты.
Ответ: Нет, нельзя.
Домашнее задание: Можно ли покрыть доску 8х8 Г-образными плитками (плитки можно вращать и переворачивать)?
Решения можно писать в комментарии
Сегодня решил написать финал высшей пробы за 2019 год.
(ссылка https://codeforces.com/group/6Saz5idq0O/contest/314982)
Задачи меня разочаровали, они оказались оч простыми.
А) считаем факториал в лоб, пока (если) он не станет нулем
B) заметим xor-штуку: либо все числа счастливые, либо ни одно число не является счастливым. Это происходит за счет того, что если xor массива без одного числа равен этому числу, то xor массива равен 0 (a xor a = 0) . Просто поддерживаем xor и размер массива
C) Я сначала прошелся dfs'ом и посчитал кол-во интересных вершин в поддереве, а потом жадно обошел это дерево только до интересных вершин. Ответ - кол-во посещенных таким образом вершин
D) Тут пришлось чуть-чуть подумать. Заметим, что сумма с i=1 по i=n-1 abs(a[i] - a[i-1]) равна a[n-1] -a[0] (если массив отсортирован). Сначала пробовал жадно через указатели искать оптимальную последовательность, не заходило, решил добавить еще пару случаев, не заходило. Потом до меня дошло, что я рассматриваю только случай, когда наименьший элемент из 1-го массива. Взял все элементы в отдельный массив и прошелся по нему двумя указателями, поддерживая кол-во уникальных чисел на отрезке - зашло.
E) Безыдейное ДО (можно наверно еще корнячку но в я в нее не умею). Просто аккуратно инвертируем элементы на отрезке и поддерживаем кол-во единиц на четных и нечетных позициях. Но так как набагал, зашло только с 5-й попытки.
P.S. В связи с тем, что уже в эту субботу финал ВП по информатике, буду каждый день выкладывать какой-нибудь пост (в первую очередь про финалы вп, но нерешенных у меня только 2 осталось, далее будут заклы олимпиады спбгу по информатике) с разбором задач
(ссылка https://codeforces.com/group/6Saz5idq0O/contest/314982)
Задачи меня разочаровали, они оказались оч простыми.
А) считаем факториал в лоб, пока (если) он не станет нулем
B) заметим xor-штуку: либо все числа счастливые, либо ни одно число не является счастливым. Это происходит за счет того, что если xor массива без одного числа равен этому числу, то xor массива равен 0 (a xor a = 0) . Просто поддерживаем xor и размер массива
C) Я сначала прошелся dfs'ом и посчитал кол-во интересных вершин в поддереве, а потом жадно обошел это дерево только до интересных вершин. Ответ - кол-во посещенных таким образом вершин
D) Тут пришлось чуть-чуть подумать. Заметим, что сумма с i=1 по i=n-1 abs(a[i] - a[i-1]) равна a[n-1] -a[0] (если массив отсортирован). Сначала пробовал жадно через указатели искать оптимальную последовательность, не заходило, решил добавить еще пару случаев, не заходило. Потом до меня дошло, что я рассматриваю только случай, когда наименьший элемент из 1-го массива. Взял все элементы в отдельный массив и прошелся по нему двумя указателями, поддерживая кол-во уникальных чисел на отрезке - зашло.
E) Безыдейное ДО (можно наверно еще корнячку но в я в нее не умею). Просто аккуратно инвертируем элементы на отрезке и поддерживаем кол-во единиц на четных и нечетных позициях. Но так как набагал, зашло только с 5-й попытки.
P.S. В связи с тем, что уже в эту субботу финал ВП по информатике, буду каждый день выкладывать какой-нибудь пост (в первую очередь про финалы вп, но нерешенных у меня только 2 осталось, далее будут заклы олимпиады спбгу по информатике) с разбором задач
Codeforces
Dashboard - Высшая Проба 2020 - Финал - Codeforces
Codeforces. Programming competitions and contests, programming community
Forwarded from Градиентное погружение
RuCLIP tiny - быстрее, чем вы думаете 🔥
Спустя около месяца с начала разработки, мы готовы представить вам самую свежую нашу работу - модель для связывания текста и изображения - RuCLIP tiny.
Что в ней такого примечательного? Как минимум её размер на диске 146Мб(!), занимаемый объем ~800Мб в памяти видеокарты, а также кол-во параметров 38М. И все это в fp32.
А что ещё? Конечно же скорость работы, а именно ~16мс на батче размером 64(!). Мы также протестировали нашу разработку на датасете CIFAR100 и получили 46.62% top1 и 73.18% top5 zero-shot accuracy.
Помимо всего прочего мы не забыли сделать удобный интерфейс и ноутбуки для наших пользователей.
Почитать поподробнее можно в нашей статье на хабре
Саму разработку вы можете найти на нашем гитхабе
Спустя около месяца с начала разработки, мы готовы представить вам самую свежую нашу работу - модель для связывания текста и изображения - RuCLIP tiny.
Что в ней такого примечательного? Как минимум её размер на диске 146Мб(!), занимаемый объем ~800Мб в памяти видеокарты, а также кол-во параметров 38М. И все это в fp32.
А что ещё? Конечно же скорость работы, а именно ~16мс на батче размером 64(!). Мы также протестировали нашу разработку на датасете CIFAR100 и получили 46.62% top1 и 73.18% top5 zero-shot accuracy.
Помимо всего прочего мы не забыли сделать удобный интерфейс и ноутбуки для наших пользователей.
Почитать поподробнее можно в нашей статье на хабре
Саму разработку вы можете найти на нашем гитхабе
Сегодня написал финал ВП 2020 года
https://codeforces.com/group/6Saz5idq0O/contest/314675
Набрал 20+20+20+1+13=74 балла (призер от 63, побед от 90)
Задачи оказались гораздо интереснее и сложнее
А) простой жадник: если сумма нечетная - выводим все плюсы
иначе ищем первое нечетное число и после него ставим умножение
B) жадник на указателях: сначала сортируем массив, затем жадно собираем для каждого случая сначала максимум элементов, потом минимум
C) довольно интересное дп. Сначала посортил значения и придумал за O(n^3) - dp[i][j] - ответ, где i - текущая позиция, j - откуда пришли (переход - dp[i][j] = max(dp[j][k]+1 для k от 0 до j-1, при условии, что a[j] - a[k] > a[i] - a[j]), написал - получил баллы, понял что идея рабочая (10/20 баллов). Заметим, что это означает, что длина каждого нового прыжка строго меньше предыдущего, а так как высоты башен уже посорчены, мы можем найти бинпоиском последнее подходящее k и взять максимум на отрезке. Это уже работает за O(n^2 * logn), но набирает 16/20 баллов. Еще можно заметить, что при увеличении j, последнее подходящее k уменьшается, поэтому предподсчитаем эти k за n^2. Далее чуть-чуть попихал и получил 20 баллов
D) не придумал, заслал кукарек и получил 1 балл
E) долго думал, потом решил попробовать идею выделения меньших элементов (если существует k подходящих подотрезков, то существует k "центральных" элементов (которые как раз медианы), следовательно ответ это длина отрезка минус удвоенное кол-во элементов, меньших m). Получил 13 баллов, очень удивился. Стал писать merge sort tree, но не успел отдебагать и поэтому только 13 баллов.
Впринципе неплохо, но мог и лучше написать
https://codeforces.com/group/6Saz5idq0O/contest/314675
Набрал 20+20+20+1+13=74 балла (призер от 63, побед от 90)
Задачи оказались гораздо интереснее и сложнее
А) простой жадник: если сумма нечетная - выводим все плюсы
иначе ищем первое нечетное число и после него ставим умножение
B) жадник на указателях: сначала сортируем массив, затем жадно собираем для каждого случая сначала максимум элементов, потом минимум
C) довольно интересное дп. Сначала посортил значения и придумал за O(n^3) - dp[i][j] - ответ, где i - текущая позиция, j - откуда пришли (переход - dp[i][j] = max(dp[j][k]+1 для k от 0 до j-1, при условии, что a[j] - a[k] > a[i] - a[j]), написал - получил баллы, понял что идея рабочая (10/20 баллов). Заметим, что это означает, что длина каждого нового прыжка строго меньше предыдущего, а так как высоты башен уже посорчены, мы можем найти бинпоиском последнее подходящее k и взять максимум на отрезке. Это уже работает за O(n^2 * logn), но набирает 16/20 баллов. Еще можно заметить, что при увеличении j, последнее подходящее k уменьшается, поэтому предподсчитаем эти k за n^2. Далее чуть-чуть попихал и получил 20 баллов
D) не придумал, заслал кукарек и получил 1 балл
E) долго думал, потом решил попробовать идею выделения меньших элементов (если существует k подходящих подотрезков, то существует k "центральных" элементов (которые как раз медианы), следовательно ответ это длина отрезка минус удвоенное кол-во элементов, меньших m). Получил 13 баллов, очень удивился. Стал писать merge sort tree, но не успел отдебагать и поэтому только 13 баллов.
Впринципе неплохо, но мог и лучше написать
👍2
Сегодня написал финал вп за 2021 год
20+20+20+0+9=69 = призер 3й степени
В общем слил. А в добавок в этому еще и приболел (пока 37.8 температура).
Ну и конечно же половину тура у меня голова болела так, что я тупо смотрел в экран и не мог думать.
Еще полчаса читал условие Ешки, пытался понять что вообще происходит в задаче.
А) простая математика (я писал бинпоиск)
B) простая математика (перебор до корня)
C) довольно сложное (для меня) дп по подотрезкам, долго думал и писал
D) придумал вроде рабочее дп по поддеревьям, но так и не отдебагал (квадрат по сложности)
Е) как выше писал - полчаса тупил не мог понять что вообще происходит, далее придумал решение за O(nm), написал, получил 9 баллов. Как оптимизировать не придумал, но судя по подтаскам, либо дд, либо корневая.
Что могу сказать по задачам финалов ВП. Поначалу (до 2019 включительно) это были относительно простые, но идейные задачи на разные темы. А вот финал за 2020 и 2021 год - это простая математика + динамика + до/корневая. Будет забавно, если на финале 2022 выдадут также первые 2 таски на математику, потом 1 на динамику, потом 1 но что-нибудь и еще одну на до/корневую.
20+20+20+0+9=69 = призер 3й степени
В общем слил. А в добавок в этому еще и приболел (пока 37.8 температура).
Ну и конечно же половину тура у меня голова болела так, что я тупо смотрел в экран и не мог думать.
Еще полчаса читал условие Ешки, пытался понять что вообще происходит в задаче.
А) простая математика (я писал бинпоиск)
B) простая математика (перебор до корня)
C) довольно сложное (для меня) дп по подотрезкам, долго думал и писал
D) придумал вроде рабочее дп по поддеревьям, но так и не отдебагал (квадрат по сложности)
Е) как выше писал - полчаса тупил не мог понять что вообще происходит, далее придумал решение за O(nm), написал, получил 9 баллов. Как оптимизировать не придумал, но судя по подтаскам, либо дд, либо корневая.
Что могу сказать по задачам финалов ВП. Поначалу (до 2019 включительно) это были относительно простые, но идейные задачи на разные темы. А вот финал за 2020 и 2021 год - это простая математика + динамика + до/корневая. Будет забавно, если на финале 2022 выдадут также первые 2 таски на математику, потом 1 на динамику, потом 1 но что-нибудь и еще одну на до/корневую.
👍2
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 прошлогодних инд тура.