Только что закончил писать тур финала вп 2018 года.
https://codeforces.com/group/6Saz5idq0O/contest/315127
Написал норм (20+20+20+17+20=97 при пороге 96 на победа в 2018).
A) простая задача на поиск первого элемента с максимальным кол-вом вхождений
B) дано множество отрезков, нужно выделить из них такие отрезки (в т.ч. обрезать имеющиеся) чтобы итоговая длина отрезков была максимальна и в каждой точке было не более 1 отрезка. Сначала долго тупил, но потом все-таки написал сканлайн
С) долго думал, начал писать мосты, понял что лажа, начал нервничать, решил загонять квадрат. Загнал 🤡
D) хорошая задача, сначала тоже тупил и не мог ничего придумать, затем написать разделяйку - ищем минимум в текущем отрезке, добавляем к текущему ответу длину отрезка * минимум, разделяем по минимумам, запускаемся от новых отрезков (в лучшем случае работает nlogn, в худшем n^2) Это + ифание дало 17/20 баллов. Только после конца заметил что минимум для подсчета ответа мы можем брать через ДО, а сами отрезки разделять по заранее выписанным индексам для каждого числа. После тура сдал на 20/20
Е) довольно очевидно сводится к штуке наподобие эйлерова цикла: идем дфс'ом, запоминаем фактически какая вершина раньше какая позже. В ответе - ориентируем ребра так, чтобы они шли из "ранних" в "поздние" вершины
Итого за сегодня сдал всё на фулл (но жалко в D тупил, не успел полностью сдать)
https://codeforces.com/group/6Saz5idq0O/contest/315127
Написал норм (20+20+20+17+20=97 при пороге 96 на победа в 2018).
A) простая задача на поиск первого элемента с максимальным кол-вом вхождений
B) дано множество отрезков, нужно выделить из них такие отрезки (в т.ч. обрезать имеющиеся) чтобы итоговая длина отрезков была максимальна и в каждой точке было не более 1 отрезка. Сначала долго тупил, но потом все-таки написал сканлайн
С) долго думал, начал писать мосты, понял что лажа, начал нервничать, решил загонять квадрат. Загнал 🤡
D) хорошая задача, сначала тоже тупил и не мог ничего придумать, затем написать разделяйку - ищем минимум в текущем отрезке, добавляем к текущему ответу длину отрезка * минимум, разделяем по минимумам, запускаемся от новых отрезков (в лучшем случае работает nlogn, в худшем n^2) Это + ифание дало 17/20 баллов. Только после конца заметил что минимум для подсчета ответа мы можем брать через ДО, а сами отрезки разделять по заранее выписанным индексам для каждого числа. После тура сдал на 20/20
Е) довольно очевидно сводится к штуке наподобие эйлерова цикла: идем дфс'ом, запоминаем фактически какая вершина раньше какая позже. В ответе - ориентируем ребра так, чтобы они шли из "ранних" в "поздние" вершины
Итого за сегодня сдал всё на фулл (но жалко в D тупил, не успел полностью сдать)
Codeforces
Dashboard - Подготовка к Высшей Пробе, День 3 - Codeforces
Codeforces. Programming competitions and contests, programming community
Прошу любить и жаловать, @Vovanm88, наш новый математик. Он будет периодически выкладывать посты по олимпиадной математике.
Всем привет, ребят!
На самом деле, поскольку я буду начинать скорее с азов, я буду(а может и нет, хехе, напишите в комментариях, повторятся или нет) во многом повторятся в одной замечательной книгой, "Как решаются нестандартные задачи", авторы Канель-Белов и Ковальджи. И если вы хотите поглотить все базовые принципы самостоятельно - рекомендую прочитать ее.
На самом деле, поскольку я буду начинать скорее с азов, я буду(а может и нет, хехе, напишите в комментариях, повторятся или нет) во многом повторятся в одной замечательной книгой, "Как решаются нестандартные задачи", авторы Канель-Белов и Ковальджи. И если вы хотите поглотить все базовые принципы самостоятельно - рекомендую прочитать ее.
Первый пост можно сказать по олпроге. Советую всем подучить плюсы, так как код я буду писать на них.
Вот кстати неплохой курс для старта https://stepik.org/course/80538
Вот кстати неплохой курс для старта https://stepik.org/course/80538
Stepik: online education
Основы C/C++ для спортивного программирования
C и C++ являются наиболее подходящими языками для спортивного программирования. Курс направлен на участников, не имеющих опыта работы с данными языками. Программа курса включает в себя знакомство с базовыми понятиями языка: переменные, типы данных, условные…
Старые туры ИОИПа (насколько мне известно, тут есть люди, которые его пишут)
Forwarded from Евгений Катасонов
Forwarded from rainboy
Codeforces
Архив прошедших интернет-олимпиад
Всем привет!
DL летописец pinned «Скоро начнутся финалы перечневых олимпиад, поэтому вот маленький календарик тех, в которых я собираюсь участвовать (фактически это просто напоминалка, но вдруг кому-то поможет не забыть что-нибудь важное) Отборы: ✅МОШ (информатика) - 320/500 проход ✅ ИОИП…»
Пост №1 с полезными материалами для индивидуального тура НТИ.
Сегодня расскажу про немного полезную (а самое главное) штуку .
Допустим нам нужно посчитать в массиве кол-во значений, которые зависят от нескольких элементов/индексов (желательно от двух):
Например https://codeforces.com/contest/1520/problem/D (посчитать кол-во пар j-i=a[j]-a[i] | j > i
Решается подобное очень просто: нужно всего лишь изменить формулку и свести это к известной/простой задаче.
В данном случае можно сделать a[j]-j = a[i]-i. Теперь это можно посчитать очень просто - присвоим каждому элементу массива a[i] = a[i] - i
и посчитаем сколько раз встречается тот или иной индекс. Теперь ответ - это сумма cnt[i] * (cnt[i] - 1) / 2 (cnt[i] - кол-во элементов i в массиве).
Но иногда встречаются задачи и посложнее. Например я встречал почти такое же условие еще наверно в 3-5 задачах на codeforces позже в разных контестах. Также была интересная задача с подобной штукой в финале Технокубка 2021 (задача F). Но там это нужно было считать на графах + не такой тривиальный подсчет и нужно по-хитрее изменить формулу чтобы получить нужную асимптотику.
Для тренировки можете решить ту задачу сами и при желании поискать еще похожие задачи.
(Вот если интересно мой код на питоне (плюсов я тогда еще не знал) для этой задачи (https://codeforces.com/contest/1520/submission/120204431). )
Далее в планах расскать про префиксные/суффиксные штуки, виды бинарного и тернарного поиска, снм, дерево отрезков, немного о графах и комбе. Если кто то захочет по-подробнее узнать о чем-либо еще - пишите,
Сегодня расскажу про немного полезную (а самое главное) штуку .
Допустим нам нужно посчитать в массиве кол-во значений, которые зависят от нескольких элементов/индексов (желательно от двух):
Например https://codeforces.com/contest/1520/problem/D (посчитать кол-во пар j-i=a[j]-a[i] | j > i
Решается подобное очень просто: нужно всего лишь изменить формулку и свести это к известной/простой задаче.
В данном случае можно сделать a[j]-j = a[i]-i. Теперь это можно посчитать очень просто - присвоим каждому элементу массива a[i] = a[i] - i
и посчитаем сколько раз встречается тот или иной индекс. Теперь ответ - это сумма cnt[i] * (cnt[i] - 1) / 2 (cnt[i] - кол-во элементов i в массиве).
Но иногда встречаются задачи и посложнее. Например я встречал почти такое же условие еще наверно в 3-5 задачах на codeforces позже в разных контестах. Также была интересная задача с подобной штукой в финале Технокубка 2021 (задача F). Но там это нужно было считать на графах + не такой тривиальный подсчет и нужно по-хитрее изменить формулу чтобы получить нужную асимптотику.
Для тренировки можете решить ту задачу сами и при желании поискать еще похожие задачи.
(Вот если интересно мой код на питоне (плюсов я тогда еще не знал) для этой задачи (https://codeforces.com/contest/1520/submission/120204431). )
Далее в планах расскать про префиксные/суффиксные штуки, виды бинарного и тернарного поиска, снм, дерево отрезков, немного о графах и комбе. Если кто то захочет по-подробнее узнать о чем-либо еще - пишите,
Codeforces
Problem - D - Codeforces
Codeforces. Programming competitions and contests, programming community
И раз уж на данный момент у меня особо нет времени заниматься data science'ом, хочу порекомендовать вам канал своего друга, который как раз пишет про свои разработки и интересные новости из мира ИИ https://t.iss.one/gradientdip
Telegram
Градиентное погружение
Обсуждаем новости, рассказываем про ML с кодом и колабом, выигрываем соревы 🏆
Контакты: @Cene655, @Cucu_LaPraline
Контакты: @Cene655, @Cucu_LaPraline
Раз уж большинство проголосовали за домашки, то держите ссылку на группу где я буду писать конспекты и добавлять тематические контесты (не забудьте выбрать роль "участник, если хотите решать задачи"): https://codeforces.com/group/a1W1cUWddJ
UPD: прошу строго не судить, я только пробую учить других людей. Если что-то не устраивает - можете смело писать например в лс
UPD: прошу строго не судить, я только пробую учить других людей. Если что-то не устраивает - можете смело писать например в лс
Codeforces
Login - Codeforces
Codeforces. Programming competitions and contests, programming community
Написал отбор на иоип, впринципе слил но не так критично (особенно если учитывать что это первый отбор):
Условия: https://neerc.ifmo.ru/school/io/archive/20220129/problems-20220129-individual.pdf
100+0+100+68
А) простая задача на префсуммы
Б) динамика за O(n*x*k) которую не придумал
С) Заметим, что если рассматривать группы, которые начинаются в i-м отрезке и заканчиваются в j-м, то функция F(i, j) не возрастает при увеличении j (F(i, j) - пересечение отрезков). Соответственно для текущего отрезка i бинпоиском находим первый и последний подходящий отрезок. Осталось быстро считать максимум начал на отрезков на отрезке и минимум концов на отрезке. Я сначала пытался ДО за O(n*log^2 n) запихнуть, но безуспешно, потом пытался спуском получать ответ, но набагал. Сдался и написал спарсы
Д) Решал сначала подгруппы, быстро понял что хлд, но было лень писать поэтому только подгруппы. (Оказывается можно было еще ДО на tin вершин сделать но что то не додумался)
107/470 место
UPD: завтра и послезавтра на codeforces будут контесты, надеюсь их не слить.
Ну и конечно советую всем их написать.
Условия: https://neerc.ifmo.ru/school/io/archive/20220129/problems-20220129-individual.pdf
100+0+100+68
А) простая задача на префсуммы
Б) динамика за O(n*x*k) которую не придумал
С) Заметим, что если рассматривать группы, которые начинаются в i-м отрезке и заканчиваются в j-м, то функция F(i, j) не возрастает при увеличении j (F(i, j) - пересечение отрезков). Соответственно для текущего отрезка i бинпоиском находим первый и последний подходящий отрезок. Осталось быстро считать максимум начал на отрезков на отрезке и минимум концов на отрезке. Я сначала пытался ДО за O(n*log^2 n) запихнуть, но безуспешно, потом пытался спуском получать ответ, но набагал. Сдался и написал спарсы
Д) Решал сначала подгруппы, быстро понял что хлд, но было лень писать поэтому только подгруппы. (Оказывается можно было еще ДО на tin вершин сделать но что то не додумался)
107/470 место
UPD: завтра и послезавтра на codeforces будут контесты, надеюсь их не слить.
Ну и конечно советую всем их написать.
Штош, пришла пора писать математику.
Одна из самых простых идей в олимпиадной математике - идея раскрасок.
Рассмотрим её на примере.
Задача:
Есть поле 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.
Помимо всего прочего мы не забыли сделать удобный интерфейс и ноутбуки для наших пользователей.
Почитать поподробнее можно в нашей статье на хабре
Саму разработку вы можете найти на нашем гитхабе