Форум DL

Мой профиль

Коронавирус это надолго. Пора начинать учиться дистанционно.

К республике готовятся

Костяной Андрей,       гимназия 51, 10 кл
Харрасов Антон,        гимназия 10, 10 кл
Ситников Алексей,      СШ 55,       10 кл
Лосев Александр,       СШ 27,        9 кл
Попович Виталий,       СШ 27,        9 кл
Горбатовский Дмитрий,  гимназия 51,  7 кл

Уже дважды выданы задания по теории

11 апреля, Тема первого занятия – ДП

До среды, 22 апреля, предлагаются к решению 6 задач

BY_13_1_3. Бомбардировка        ( 5 / 427)    Костяной 
BY_11_1_3. Конькобежная трасса  (24 / 131)    Харрасов  
BY_15_2_3. Космический корабль  (13 / 131)    Ситников
BY_13_2_3. Турнир ораторов      (49 /  51)    Лосев 
GO_16_1_4. Диск                 (33 /  47)    Попович
GO_11_1_4. RSA++                (87 /  38)    Горбатовский

два числа A/B в скобках обозначают следующее
A – сколько человек сдали на DL эту задачу
B – «сложность задачи» = количеству дней, которые задача доступна для сдачи, делённое на A

В первую очередь нужно решить и описать в форуме (через ссылку «обсудить задачу в форуме»)
решение «своей» задачи (той, напротив которой стоит Ваша фамилия).

А затем попытаться решить все предложенные задачи
(при желании пользуясь добавленными «коллегами» описаниями уже решенных задач)

Для удобства задачи скопированы в курс «Программирование - профессионалы (лич. 2019-2020) (P/O)»
В папку Теория, подпапку ДП_1

Замечу, что все решённые Вами задачи я скопирую в папку BY/GO – полные решения.
А Ваши описания решений распечатаю (с указанием автора) и буду давать ребятам в случае необходимости.
Поэтому желательно описания решений делать как можно более понятными и подробными.
А исходники – максимально читабельными и понятными.
Ориентируйтесь на Мишу Бреля и Илью Васина – они 5 –классники, но сейчас в теории уже в Сложных структурах данных.
Как следствие, такие теоретические занятия принесут пользу не только Вам, но и тем, кто идёт за Вами.

21 апреля (все задачи BY)

                                                                 Сдано   
2012_1_3. Цифровая строка            ( 2 / 976)   Костяной 
2011_2_4. Reverse 2D                 (10 / 297)   Харрасов
2010_1_4. Видео сервис               (16 / 215)   Ситников                  
2012_2_2. Лазер                      (17 / 163)   Лосев          22.04.2020 
2011_2_3. Арифметический показатель  (50 /  64)   Попович
2017_2_2. Новый факультатив          (17 /  61)   Горбатовский

Раз не справляетесь, увеличиваю время на выполнение заданий

Предлагается до 13 мая
В первую очередь сдать и описать свою задачу,
затем сдать и все остальные задачи, в идеале самостоятельно,
если не получается – почитав объяснения

Кроме того, рекомендуется читать объяснения, даже в том случае, если Вы сдали задачу самостоятельно.
Причин две
1. Возможно Вы узнаете что-то полезное, или вообще другой, более эффективный подход к решению задачи
2. Возможно Вы сами придумали более эффективное решение и тогда обязательно поделитесь им с товарищами.

Текущее состояние по теории

Также необходимо решать и дорешивать наши воскресные олимпиады.
При этом сразу переслать всё что сдали на олимпиаде, а потом пытаться дорешать все остальные задачи
Если не получается - кликать "Обсудить задачу в форуме"
и конкретно формулировать, что именно вызывает затруднение.
Надеюсь, всегда получите ответ

Текущее состояние в дорешивании

И, наконец, нужно работать индивидуально на Codeforces
В первую очередь – решать и дорешивать Codeforces-раунды
- те задачи, которые находятся «в зоне Вашего ближайшего развития».

Текущие рейтинги на Codeforces

Мой профиль

3 мая

Текущее состояние в теории (Задано 12 задач)

Решено

Лосев         8
Попович       7
Харрасов      5
Ситников      5
Костяной      5
Горбатовский  4

Текущее состояние в дорешивании воскресных олимпиад (30 задач к дорешиванию)

Решено

Попович       25
Ситников      20
Лосев         20
Костяной       4
Горбатовский   3

Костяной, Харрасов и Горбатовский - пожалуйста перешлите в Р/О задачи, которые сдавали на олимпиаде.
Через он-лайн-редактор это дело нескольких минут.

И будет хорошо видно сколько задач Вам осталось дорешать.
Например - Поповичу - только 5 из 30.

Дорешивание – самый прямой путь к росту мастерства.

Мой профиль

Андрей Костяной:

Здравствуйте! Мы с ребятами поговорили и решили, что хотим решать COCI 2 раза в неделю: по средам и воскресеньям. Можете нам ставить контесты, пожалуйста?

Отличное решение, согласен, сделал, однако очень важно, чтобы ВСЕ, а не только Андрей

Дорешивали все задачи.

Сейчас олимпиада была только по воскресеньям и это не так.
А если дорешивать в два раза больше придётся?

Настраивайтесь дорешивать всё !!!

Ну и теорию тоже

"Чтобы два раза не вставать", выложил новое задание по теории (графы) до 3 июня

BY_2012_2_3. Диверсия               ( 4 / 586)     Костяной
BY_2015_1_4. Служба спасения        (11 / 153)     Харрасов
BY_2013_1_4. Западный поток         (17 / 143)     Ситников
BY_2015_1_3. Путешественник         (26 /  68)     Лосев
BY_2016_2_3. Праздничное украшение  (76 /  19)     Попович
BY_2014_2_3. Дороги                (184 /  12)     Горбатовский

Текущее состояние в теории (Задано 18 задач)
Текущее состояние в дорешивании воскресных олимпиад (30 задач к дорешиванию)

Мой профиль

10 мая

Текущее состояние в теории (Задано 18 задач)

Решено

Костяной     12
Лосев        10
Попович       6
Харрасов      6
Ситников      5
Горбатовский  5

Текущее состояние в дорешивании воскресных олимпиад (35 задач к дорешиванию)

Решено

Костяной      31
Попович       30
Ситников      28
Лосев         25
Харрасов       4
Горбатовский   3

Мой профиль

11.05.2020

Сегодня дорешивал и написал виртуалку 614 Div 1 раунда на CF.

Сначала дорешка. Дорешал две задачи (и еще 2 изика):
1) https://codeforces.com/contest/1286/problem/E, интересная задача, нужно было догадаться, что нужно использовать дерево префикс функции (на самом деле условие задачи на это намекает), но более интересной идеей было сделать ссылки к предкам с другим следующим символом, остальное не так сложно (а, ну еще ответ немного превышал 2^64, поэтому пришлось написать длинку для сложения чисел);
2) https://codeforces.com/contest/1287/problem/B, https://codeforces.com/contest/1287/problem/A, A и B задачи из того же контеста, что и первая задача, сдал просто чтобы руки размять;
3) https://codeforces.com/contest/1307/problem/F, ооочень интересная задача на СНМ (нужно было догадаться, что вместо того, чтобы делить число на 2, мы можем отставить его таким же, но удлинить ребра в два раза, добавив фиктивные вершины и еще несколько красивых идей было).

Теперь виртуалка. Начал неплохо, за 22 минуты сдал A и B c +, начал думать над С. Сделал несколько наблюдений и придумал жадник в который не оч верил, но выглядел +- убедительно. На 1.24 заслал, но тут КФ завис, поэтому я начал думать над D, так как нужно было что-то делать. Примерно к 1.40 КФ отвис и я получил WA 5 по C. Переключился обратно на С, так как на нее код был уже написан, нужно было дебажить. Нашел несколько багов, но исправил только на WA 9 и до конца контеста пытался найти ошибки в коде.

После завершения соревнования решил посмотреть разбор на С, открыл, прочитал 1 слово - ДП и сразу же придумал, как исправить свой жадник на ДП, Исправил, отправил - фулл. Думаю, что проблема вот в чем. Я обычно записываю все идеи по задаче, которые приходят мне в голову и время от времени их перечитываю. Так я никогда не потеряю свою идею, если вдруг решил переключиться на что-то. И когда я прочитал задачу С, я сразу подумал, что там ДП, но записать забыл. Если бы записал, то после того, как получил WA, я бы пробежался по идеям и придумал бы ДП.

Итог: хорошо начал, но обидно, что не сдал C и ничего не придумал в D.

Мой профиль

12.05.2020

Сегодня решал зеркало 1-ого тура респы (это было не запланировано). Начал чуть менее чем через час от начала зеркала, потому что мне сообщили, что возможно будут отбирать на сборы к миру по результатам зеркала. И так, теперь сам контест. Прочитал все задачи, вот первое впечатление:
1) оч не люблю такие задачи, нужно написать какой-нибудь из 100500 вариантов жадников, но сама по себе задача простая;
2) придумал сходу идею с соседними вершинами, потом оказалось, что я даже немного усложнил решение.
3) конструктив - это все, что можно сказать после первого прочтения;
4) оч хорошая задача, сразу много идей решения, относительно быстро придумалась идея с включениями-исключениями на 64 балла.

Так как я понимал, что 4-ая задача скорее всего самая трудная, то я сразу сдал решение на 64, так как писать его было не долго и у меня уже были какие-то баллы по задаче и я мог заняться более простыми. Попытался набросать что-то на 1-ую задачу, получил 48 баллов и решил, что нужно переключиться, чтобы не увязнуть во всех вариантах жадников. Написал 2-ую сначала для проверки идеи на +-50 баллов, потом быстро исправил на 100. Решил вернуться к 1-ой, так как это была явно самая простая задача контеста, попробовал еще пару жадников, потом окинул взглядом "лист идей" и вспомнил, что можно было бы попробовать дихотомию/трихотомию. Быстро написал трих и получил свои 100 баллов. И так, примерно спустя 1 час 40 минут я имел 264 балла и непочатый край работы в 3-ей задаче. Как обычно, я решил написать что-нибудь, чтобы проверить, правильно ли я понял условие и на 2-ом часу я отправил решение на безуспешные 0 баллов. После небольшого тестинга в 2 часа 15 минут я получил 15 баллов по задаче и уже не боясь, что я неправильно понял условие, начала думать настоящее решение. Опять-таки, окинув взглядом "лист идей", я вспомнил про Разделяй-и-Властвуй (по итогу решение не оч напоминает РиВ, но эта идея помогла мне дойти до правильной) и после относительно недолгих раздумий, я придумал, как соптимизировать решение чтобы тратить 5*n/2 запросов. Исправив свой код в 2 часа 50 минут я получил 64 балла. Теперь уже стоял вопрос, что делать дальше: добивать 3-ю или получить еще баллов по 4-ой, но после недолгих раздумий я придумал полное решение по 3-ей, которое тратило 3*n/2 запросов, но для этого мне пришлось бы почти полностью переписать код. К этому времени у меня оставался час. Я решил, что это гарантированные баллы и начал печатать. На 3 часа 30 минут мой код просто начал компилироваться поэтому я отправил то, что у меня было и успешно получил WA 1. Так как я подозревал, что сходу код не заработает, то я не ждал вердикт, а сразу начал дебажить. Ошибок оказалось не так много, поэтому на 3 часа 40 минут я получил 100 баллов. Так как у меня оставалось 20 минут, то я решил попробовать запихать решение по 4-ой, но по итогу у меня это не получилось и я завершил контест с 364 баллами.

Как я знаю, лучший балл на туре на республике 380 баллов (мои же баллы, только 80 по 4-ой). Учитывая, что я решал только 4 часа, голодный и на немалом стрессе, так как мои планы сильно поменялись, то все не так уж плохо, но все равно я знаю, что мог набрать 380. Проблема я думаю в том, что я долго разбирался с 1-ой задачей. В "лист идей" я почти сразу записал трихотомию, поэтому нужно было сразу же ее и проверить, потому что кода писать было немного. Кроме того, я думаю, что я зря написал промежуточные 64 балла по 3-ей, так как я понимал, что скорее всего сдал бы эту задачу на 100, то я просто впустую выбросил почти 40 минут. Полное решение было не так далеко от решения на 64 и я интуитивно понимал, что уже близко, нужно было сразу дожать идею до 100 и писать фулл тоже сразу. Думаю, что нужно было бы поставить какое-нибудь ограничение по типу "если за час до конца ничего не придумаю, то напишу это". В прошлом году такой шаг на республике позволил мне взять 1-ую степень.

Мой профиль

13.05.2020

И так сегодня я планировал отрешать зеркало 2-ого тура респы, ждал этого почти весь день, а по итогу его перенесли на завтра. Поэтому сегодня почти ничего не успел сделать и решил, что пусть это будет "день отдыха".

И так, дорешка:
1) Дорешал задачу D с Div 1 614 CF раунда (https://codeforces.com/contest/1292/problem/D). На самой прорешке я успел придумать, что граф является деревом и что мне нужно найти "центроид", но я не успел придумать, куда мне нужно спускаться. По итогу это оказалось не так сложно и почти вытекало из условия задачи. Кода оказалось очень мало, теоретически можно было бы сдать на контесте, если бы не возникло проблем с C.
2) Еще закинул 2 изика (https://codeforces.com/contest/1293/problem/B, https://codeforces.com/contest/1293/problem/A), это A и B задачи с того же контеста, что и 1-ая задача, закинул, чтобы руки размять, но что-то КФ завис и я пока не знаю вердкита, но я сверился с разбором, идеи похожие. Времени ждать у меня нет, так как завтра утром будет зеркало, нужно лечь пораньше.

Upd: по итогу изики зашли.

Мой профиль

14.05.2020

Сегодня решал 2-ой тур респы. По-классике, первое впечатление о задачах:
1) Изик, придумалась сразу, больше говорить нечего;
2) Эта задача поинтереснее сразу же несколько идей насчет gcd, по итогу придумал 3 решения, потому что боялся словить TL;
3) Сразу смотрится очень страшно, но и сразу же придумалось ДП на 54;
4) Интересная задача, сразу же отметил тот факт, что в графе будет существовать эйлеров цикл (возможно не один), так как это открытые тесты, то несколько жадников сразу придумались.

И так, нужно было действовать. Открытые тесты нужно было проверить на входные данные, может какие-нибудь легкие тесты или что-то тип того. Так и оказалось: 1-ый тест можно было нарисовать руками, а в 3-ем граф - это кольцо. Нарисовал быстро 1-ый тест руками написал ответ, отправил, получил 10 баллов и уже не боясь, что я мог неправильно понять условие, пошел решать изики. 1-ую сдал минут за 10-15. В этот момент я еще не знал точного решения на 2-ую, поэтому отправил брут на 32. И перешел к 3-ей. Я понимал примерно, что 3-я задача самая сложная будет и нужно на нее написать 54 балла, чтобы потом можно было заняться 2-ой и 4-ой. Писал я минут 20 +- и получив свои 54 балла по 3-ей решил вернуться ко 2-ой. Минут 10 додумывал решение и решился написать фулл. Кодил +- 20 минут, заслал. И тут первая неприятность - 80 баллов и ML в придачу. Но я не оч долго с ней разбирался, через минут 7-8 придумал отсечение по памяти и сдал 2-ую задачу на 100. И так, пришло время открытых тестов. Сразу написал решение на граф-кольцо и получил еще 10 баллов. Исправил немного dfs, чтобы решение работало для больших тестов, в которых есть цикл, который проходит по всем вершинам, и получил полные баллы в сумме по 5 тестам и на все это мне потребовалось 40 минут. Теперь нужно было придумать что-нибудь поинтереснее. Очевидная идея с нахождением случайных циклов и добавлением их к ответу. Прямой перебор без всяких рандомов принес мне в сумме 80,95 баллов. Так как я понимал, что авторы могли намеренно отсечь такое решение, то я решил написать что-нибудь еще, чтобы улучшить баллы. Сразу же в голову пришла идея искать самый длинный цикл, который проходит через какую-либо вершину + я относительно недавно писал это с деревьями BFS и решив, что это хорошая идея, начал печатать. Примерно за 20 минут переписал код, а еще через 10 он стал работать и я получил в сумме 83,09 балла. Тут же я заметил, что у меня 4-ый тест находит почти правильный ответ и я решил немного порандомить. Довольно быстро нашелся правильный ответ и я получил +3 балла. Так как осталось примерно 45 минут до конца контеста и я ничего не успел бы уже сделать в 3-ей я стал потихоньку улучшать свое решение по 4-ой набирая баллы. Еще через 10 минут я сдал на полный балл еще один тест, ну и к концу контеста я получил по 4-ой 90,65 балла.

Итоги: 100 100 54 90,65. Вот такая разбалловка, вроде бы неплохо, был бы лучший балл на 2-ом туре и лучший балл по 4-ой задаче в придачу, но открыв результаты зеркала я увидел, что Ропан сдал 4-ую на 100. И я стал подозревать, что мои идеи по поводу Эйлерова цикла были небезосновательными. Я спросил у Керножицкого Саши, есть ли у авторов полиномиальное решение. И оно было. И было связано с Эйлеровыми циклами. Не знаю, насколько трививально было придумать такое (если додуматься до одной вещи, то дальше все не так сложно), но думаю, что за 3 часа, которые у меня были, после того как я сдал 1-ую, 2-ую и 3-ю на их конечный балл, я мог такое придумать, тем более, что про Эйлеровы циклы я подумал сразу. Возможно это непривычно, что открытые тесты имели решение, но все равно, нужно было потратить на это хоть сколько-нибудь времени, потому что не будь там полного решения, я мог бы найти хороший жадник, к примеру.

Мой профиль

15.05.2020

Сегодня написал виртулку 641 Div 1 и начал дорешивать задачи открытой олимпиады школьников.

Сначала виртуалка. Контест не пошел с самого начала. Я не смог быстро придумать A, пришла идея с n - 1 элементом, но я понял, что она не правильная (по итогу оказалось, что нужно было в самом деле использовать n - 1 элемент, но немного не так, как это делал я). Переключился на B. Там получил несколько WA. Решил, что опять нужно отвлечься и переключился на C. Это более стандартная задача и я написал брут, чтобы проверить идею. Он словил TL 15. Я примерно представлял, что нужно было делать, но моя реализация была очень сложной и по итогу я не решил ни одной задачи. Разобрался с решениями. В каждой задаче я был невыносимо близко к финишу, но чуть-чуть не хватало. Уже дорешал задачи. Больше в контесте ничего близкого мне по уровню не было (оставшиеся задачи сдавало <16 человек на контесте).

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

Мой профиль

16.05.2020

Сегодня как и планировал дорешивал открытку и написал 643 Div 2 (для меня анрейт).

Сначала дорешка:
1) https://codeforces.com/contest/1322/problem/B, задача 2_2 с открытки, прикольная идея решения, кроме того оказалось, что на открытку эту задачу дали не впервые (ее давали на info(1)cup), поэтому я дорешал еще и усложненную версию этой задачи на oj (https://oj.uz/problem/view/info1cup17_xorsum);
2) https://codeforces.com/contest/1322/problem/C, задача 2_3 с открытки, интересная задача на жадные алгоритмы и хэши, но по-моему, самое интересное в решении - док-во корректности.

Теперь раунд. Начал неплохо, через 5 минут сдал B. Долговато тупил над А, но в итоге сдал с +1 на 19 минуте (забыл поставить лонги). Потом была С-шка. Задача на математику, это сразу ясно. Относительно быстро придумал идею с прогрессиями, писал минут 15 +-, так как несколько раз все перепроверял, не забыл ли какой частный случай. В итоге сдал с +. Так как с условиями я был ознакомлен, то взялся за Е, так как она мне больше понравилась. Очень быстро придумал идею с трихотомией и также быстро сдал с + (+- 7 минут). Потом взялся за D. Как и всегда в таких задачах, решил найти какую-нибудь закономерность на маленьких тестах, относительно быстро нашел и сдал эту задачу за +-15 минут с +. И так за +- час я сдал 5/6 задач, осталась F. Задача очень интересно поставлена (найти что-то не точь-в-точь, а с погрешностью). Думал над ней минут 30 и дошел до "ужаса" маленьких простых чисел и как их "выщемливать". По моим оценкам решение было рабочим и я начал печатать. За минут 15 закодил, отправил - WA 3. В интерактивках WA в принципе вердикт не приятный, так как он может означать все, что угодно. Я начал просматривать код и быстро нашел баг, отправил - AC.

И все вроде бы отлично, только нужно было дождаться систестов. А они принесли неприятные новости - WA 49 по F. Посмотрел в тесте, в чем конкретно проблема, начал думать. Несколько костылей сразу пришли в голову, написал их - фулл. Потом написал еще один костыль и мое решение начало работать еще и с запасом (всего на 1 запрос, но все же). Как-то так. Обидно, что F не зашла на контесте, но это событие было довольно массовым, так что не так уже все плохо. Думаю, чтобы получить AC сразу, нужно было проверить, сколько запросов нужно на все простые до 1000. Я этого не сделал и понадеялся, что 17 хватит. Если бы я сразу увидел, что не хватает, то костыли написал бы тоже сразу, чтобы сократить число запросов.

Мой профиль

17.05.2020

Сегодня был воскресный контест. Сейчас решаем COCI по 5 задач в контесте. Вот первое впечатление о задачах после прочтения:
1) реализация, все очевидно, это и ожидалось от 1-ой задачи;
2) реализация, опять-таки все очевидно;
3) тут были некоторые трудности, но связаны они были только с неправильным русским условием, после прочтения английского правильное решение довольно быстро придумалось;
4) в задаче сразу намеки на маски, подумал еще про включения-исключения и хэши (до этого решал несколько задач с похожими ограничениями и относительно похожими формулировками и в них использовались эти приемы);
5) посчитать все пары вершин в дереве с каким-то свойством - это довольно часто центроидка;

И так, начал я со 2-ой задачи, потому что она была самой простой на мой взгляд. Сдал за минут 5 +-. Потом взялся за 1-ую. С ней возился долго (учитывая уровень задачи). Вся проблема в очень неудобном формате ввода. Минут за 15 написал и еще за 3 отдебажил. В этот момент я еще точно не разобрался с условием 3-ей, поэтому решил написать на 4-ую те включения-исключения, который я придумал на тот момент. Написал код за минут 12, отправил - 11/110. Понадобилось минут 5, чтобы я понял в чем именно проблема и так как я сразу же не придумал, как ее исправить, я стал думать над 3-ей и 5-ой. Первой придумалась 3-я и я пошел писать. Чтобы ее сдать мне потребовалось минут 15-20. Теперь стоял вопрос, что решать 4-ую или 5-ую, но в тот момент я уже почти додумал идею на 5-ую, поэтому взялся за нее. Додумав детали я стал печатать. Написал и отдебажил код я минут за 40 и с первой же отсылки решение взяло полный балл на oj. Но на DL я словил TL. На oj время на макс тесте было 0,9 секунд, поэтому я решил, что теоретически решение могло взять TL на COCI и мне нужно его исправить (я попробовал прагмы, но не получилось

). Но меня это не сильно подкосило, так как я рассматривал вариант TL, когда писал код (я писал более короткую, но более медленную версию), поэтому я изменил свои oredered_set-ы на сжатые BIT (на это мне потребовалось минут 13) и решение стало укладываться в двойной TL на oj и спокойно зашло на DL. Оставалась четвертая задача. Я стал над ней думать и в голову пришла идея с бором. Написал код я минут за 15, а еще через 5 он стал работать, но словил ML. Еще немного подумав я понял, что можно мой бор заменить на хеши и минут за 10 я исправил свой код до полного решения. Так как я закрыл контест за 3 часа, то я позволил себе поиграться с хешами (разные варианты хеш-таблиц) и самой лучшей оказалась gp_hash_table (+- 400 мс на oj и 0,5 на DL), так что всем советую

Кроме того сегодня я продолжил читать блог про матроиды. Я понимаю, что скорее всего явно пересекать матроиды мне никогда не пригодится, но вот почему я продолжаю его читать. В последнее время стал чаще сталкиваться с жадниками, которые доказываются так: "можно доказать в соответствии с алгортмом Радо-Эдмондса для матроидов". И раньше для меня это был пустой звук. А теперь (хотя я не прочитал и половины блога) я понимаю, почему эти жадники работают (тот же алгоритм Крускала можно так доказать), но что, по-моему, самое важное, я смогу понять на контесте какой жадник будет работать (конечно, не все жадники так можно проверить, но все же). + Возможно я смогу научиться каким-нибудь интересным приемам с множествами или графами.

Мой профиль

18 мая

Текущее состояние в теории (Задано 26 задач)

Решено

             Задачи    ДП 1     ДП 2    Графы   BY_2020
Костяной       17        4        2       6        5
Лосев          12        5        3       4  
Попович         8        6                2 
Харрасов        6        5        1
Горбатовский    6        3        0       3
Ситников        6        4        1       1 

Добавлены задачи Республики 2020.
Все вместе их решать не будем.
Кто хочет отрешать в олимпиадном режиме - может сам себе отмерять 5 часов в любые два дня.
Но обязательно дорешать все задачи  – до 17 июня.

Кроме того, просьба описать решения задач

Костяной      1_4. Ракета на нейтринной тяге 
Харрасов      2_4. Ускоритель частиц 
Лосев         1_3. Любимые игрушки - интерактивная
Попович       2_3. Марсианские Игры
Горбатовский  1_2. Вулканы на Венере
Ситников      2_2. Очаровательные нейтрино

BY_2020
День 1  Авторский видео-разбор,   Костяной 
День 2  Авторский видео-разбор,   Костяной

Текущее состояние в дорешивании воскресных олимпиад (40 задач к дорешиванию)

Решено

Костяной      39
Попович       35
Лосев         29
Ситников      28
Горбатовский  17
Харрасов       4

Динамика рейтингов на Codeforces c 18 января по 18 мая 2020 года


Костяной      1974 -> 2193 = +219
Харрасов      2206 -> 1916 = -290 
Лосев         1621 -> 1749 = +128
Попович       1551 -> 1691 = +140 
Горбатовский  1447 -> 1649 = +202
Ситников      1594 -> 1620 = + 26

Мой профиль

18.05.2020

Сегодня дорешал 2_4 с респы 2020 (очень интересная задача на эйлеров цикл и хитрый парсоч). Еще планировал дорешать 1_4, но я не ожидал, что так долго буду разбираться с матроидами. Зато я закончил читать этот блог (кстати, я походу забыл дать на него ссылку, так что вот https://codeforces.com/blog/entry/69287?locale=ru), осталось только несколько задач решить для закрепления. Как я и ожидал, пока читал блог я несколько интерсных приемов изучил, например:
1) Лемма о замене базиса. Доказательство, что можно из любого базиса получить любой другой базис последовательностью замен. Один из примеров - из любого остова в графе, можно получить любой другой остов последовательностью замен ребер;
2) Алгоритм, как именно находить последовательность операций, чтобы получить из одного остова другой, причем после каждой замены набор будет оставаться остовом;
3) Интересная идея про превосходный парсоч в двудольном графе, ребра которого раскрашены в два цвета (то есть нужно найти превосходный парсоч по одному цвету и превосходный парсоч по второму цвету).

Конечно, это совсем не все, ведь я даже не начал говорить про сами матроиды

, но блог просто отличный, всем советую.

Мой профиль

19.05.2020

Сегодня дорешивал и написал виртуалку 87 educ-а на CF.

Сначала вирт. A и B сдал за минут 10. Потом прочитал C1 и C2 там была геома, что уже не оч приятно, поэтому немного подумав, я временно их пропустил. Прочитал D, очевидное решение с ordered_set, которое словило ML (я заметил маленькие ограничения по памяти, но все равно должно было хватить с запасом, видимо orederd_set хранит кучу лишнего из-за чего память полетела). Немного подумал и переписал с фенвиками и получил AC. И так стоял выбор E или геома. Я парень простой, пошел решать E. Как-то сразу в голову пришла идея посмотреть на циклы, а в циклах нечетной длины все ломалось, значит граф - двудольный. Дальше изи ДП по компонентам. И так к 55 минуте я сдал E с +. Прочитал F, накидал несколько идей, но решил, что нужно все-таки подумать над C. Но в C ничего в голову мне не приходило (потому что я на бумаге неправильно решил для 8-угольника, поэтому ничего не мог придумать), поэтому я решил вернуться к F. К этому моменту я уже почти все придумал, оставались детали (например в каком порядке добавлять 1-ых k-1 героев, но было несложно догадаться, что в порядке возрастания b). Относительно быстро все додумал и пошел печатать. Не помню точно, сколько времени я кодил, но к 1.33 я сдал еще и F с +. Оставалась G и геома. Как я не люблю геому, но пришлось идти ее думать. К сожалению до конца контеста я так и не понял, что неправильно решил тест с 8-угольником поэтому больше я ничего не решил. Думаю, что проблемы не было бы, если бы я сделал правильный чертеж, а не "на глаз". Вывод: строить правильные чертежи при решении геометрии. Задачу G еще не разбирал, так как я не особо думал над ней на контесте. Хочу сначала подумать, а потом, если не придумаю, посмотреть разбор.

Теперь дорешка. Дорешал я сегодня C1 и C2 с educ-а, так как неплохо было потренить тригонометрию (это и для школы полезно). А еще я дорешал 1_4 респы 2020. Вот с этой задачей пришлось повозиться. На Яндекс.Контест (на котором проходила респа) задача зашла довольно быстро, буквально несколько оптимизаций и AC. А вот на DL было 96 баллов (по подгруппам 80) и TL. Не знаю, может нужно поднять TL на DL-ке, но это сейчас не особо важно. Сначала я подумал, что просто перешлю на nit_0 и забуду, но потом я попросил код Мищенко. Он тоже ловил TL, но на некоторых тестах работал заметно быстрее. Я решил разобраться и нашел интересную фишку (благодаря этому мой код на 1_4 заходит даже на NIT_7).

Дело вот в чем. Намного быстрее работает
(x *= y) %= md;
чем,
x = (x * y) % md;

В принципе очевидно почему, но заметить такое было не оч просто, так как смотрится это почти одинаково.

Мой профиль

20.05.2020

Решал 19COCI7_apr:

1) как только прочитал, сразу забил на неё. По ней видно, что это конструктив на графе.
2) сразу видно, что это ДП по числу
3) задача на реализацию
4) на первые три группы - проверить достижимость в орграфе от одной до всех, дальше вроде ССД.

Итак. Прочитал первую, сразу отложил её на самый худой конец, так как там жёсткий конструктив. Вторую почитал, подумал, что-то на ДП смахивает(если думать про фулл),решил почитать дальше. Третью прочитал, что-то она мне сразу не понравилась, отложил. Прочитал четвёртую, придумал на три группы, сел кодить. В итоге за полтора часа я имел 30 баллов по четвёртой, всё остальное по нулям. Решил сесть за вторую, придумал на 8 баллов(1-ая группа), сел писать. Долго ловил багу, связанную с глобальными и локальными переменными. В итоге через час, после взятия баллов по 4-ой, я сдал на 8 баллов. Придумал на вторую группу эту задачу, пошёл писать. Словил ML и исправлял его минут 20. Потом словил TL и тут я решил пересчитать асимптотику на 2-ую группу. Оказалось, что это время было потрачено впустую, потому что не увидел, что TL - 0.5 сек. К 12:30 я имел всё те же 38 баллов. Пошёл писать 3-ю. Придумал идею такую: будем обрабатывать каждый метр, если напоролись на акселератор, тогда сортим чуваков по времени, и ставим в зависимости от позиций буст. Зашло на первую группу, где всего один акселератор. Шёл последний час, и у меня было 0/8/15/30. Решил перечитать условие 3-ей, напоролся на момент, который я неправильно понял. То есть было сказано, если у нас есть буст, мы не должны его изменять, при встрече с другим акселератором. А я понял так: если у нас есть активный буст на новом акселераторе, то надо изменить на новый. В итоге я час искал багу в коде. После контеста решил перечитать условие и в итоге правильно его понял и дорешал через пять минут после конца.

Мои ошибки:

1) внимательней читать условие
2) ВСЕГДА смотреть на TL, ML

3) перед написанием идеи, посчитать её асимптотику на КАЛЬКУЛЯТОРЕ