Форум DL

Мой профиль

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

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

Давайте все бороться за попадание на республике в 8-ку сильнейших - на отбор к IOI.

1. Решение олимпиад по воскресеньям и на сборах
Программирование - профессионалы (лич. 2020-2021): Зимний Кубок – 2020/2021

2. Дорешивание
Полная таблица

На 14 января 2020

1 - 3	Лосев Александр	      40	
1 - 3	Попович Виталий	      40
1 - 3	Ситников Алексей      40
4	Костяной Андрей	      37
5	Горбатовский Дмитрий  24
6	Харрасов Антон	      19

Полные решения с олимпиад нужно пересылать в Р/О.
И стараться дорешать все задачи.

3. Регулярно решать раунды на codeforces - повышать рейтинг
(дорешивая, то что находится "в зоне ближайшего развития")
Динамически формируемая таблица

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

2320	Костяной Андрей	        Гомель	
2272	Харрасов Антон	        Гомель	
2151	Дамасевич Станислав	Мозырь	
2072	Галух Никита	        Гомель	
2031	Кругликов Игорь	        Гомель	
1961	Попович Виталий	        Гомель	
1835	Горбатовский Дмитрий	Гомель	
1813	Кольченко Антон	        Мозырь	
1794	Ситников Алексей	Гомель	
1753	Лосев Александр	        Гомель	
1712	Веретенников Максим	Гомель	
1639	Черноокий Никита	Мозырь	
1583	Почепко Илья	        Светлогорск
1571	Отращенок Александр	Мозырь	
1493	Булавко Тимофей	        Мозырь

4. Регулярный самоанализ
подобный тому, как это регулярно делает Андрей Костяной.

Мой профиль

Прошла областная олимпиада 2021-ого года. Отрешал её на 615 баллов (10-ое место), но до начала олимпиады рассчитывал войти в топ-5.

Первый день:

Предыстория: я рассчитывал, что нас вечером после пробного тура отпустят в магазин, но нас не пустили), поэтому я ничего не покупал в Гомеле на первый день и хотел купить шоколадку уже на месте. Пришёл на контест без воды и без шоколадки

1) В задаче А я минут 10-15 тупил и не мог нормально реализовать решение
2) Задачу В сдал за 2 минуты после сдачи А
3) В задаче С сразу пришла в голову идея с ДПшкой по диагоналям и считать ответ с помощью дихи. Писал я её примерно час(минут 20 копипастил и изменял названия переменных) и минут 15 дебажил код, так как ошибся в формулах для проверки правильности квадрата.
4) Чтобы сдать последнюю задачу, оставалось 3 часа и ~30 минут. Изначально написал группы, где заходил обычный брут за O(8 * q * n). Пытался придумать фулл, не сдавая больше никаких групп, но как оказалось, ничего в голову не пришло, поэтому я пошёл думать над группами и зачастую можно было выйти к фулл решению. Придумал группу, где не было операций ксора, но не был уверен что она пройдёт, так как не мог оценить асимптотику. К моему удивлению, эта группа зашла и решил думать над группой, где числа в массиве всегда не более 1-цы. Придумал обычный спуск по ДО с ленивым проталкиванием, но у меня почему-то не заходило решение и я пытался отдебажить его до конца контеста. Примерно за час до конца контеста я осознал фулловое решение, но в нём мне нужно было скомбайнить решения для группы, где нет операций ксоров, и для группы, где числа <= 1. Я принял решение отдебажить код на группу ai <= 1, но до конца контеста так и не отдебажил.

После конца контеста я узнал два решения на задачу D:
1) решение через ДП f[i, j]: где i - последнее использованное число, j - длина подпоследовательности и в f[i, j] храниться минимальная позиция, на которой будет оканчиваться подпоследовательность с параметрами (i; j)
2) второе решение было такое же, как я придумал на контесте

Второй день:

Предыстория: нас отвели в магазин, где я на второй день прикупил сока и шоколадки

1) задача А была на реализацию того, что сказано в условии, сдал за 10 минут
2) задачу В сдал за 2 минуты после сдачи А
3) Остались две самые интересные задачи. Прочитав задачу С, у меня не было никаких идей, переключился на D, написал группы на вывод максимальной "безопасности". Вернулся к Сшке и придумал линейное решение через стандартный приём с префикс.суммами(pr[r] ^ pr[l] = s). Решил проанализировать то, как выглядять префиксные ксоры и нашёл интересную закономерность, от которой отталкивались будущие решения. Обратно переключился на D, так как там были ещё группы, где можно было написать квадрат. Написал решение за квадрат, перебирая вершины, которые я удалю из дерево и просто посчитать ответ. В итоге у меня оставалось где-то часа два и было баллов = 100/100/34/34. Переключился на С, так как там были ещё группы, которые я не сдал, не считая последнюю. Примерно минут 20 посидев перед монитором и влупляясь на префикс.ксоры я вывел формулу для подгруппы l = 1, s = 0. Ещё немножко проанализировав я написал группу для s = 0, но у меня ни прошлая, ни эта группа не заходили. В итоге бага была из-за переполнения(я не брал число x и число y по модулю, когда их перемножал по модулю, (x, y <= 1e18)). В итоге я сел придумывать фулл на D, так как я не особо дружу с математикой(задача С) в олимпиадной проге. Пытался писать жадники с центроидной декомпозицией, но они все не заходили, так как там фулл - далеко не жадник, а дерево Ли Шао(подобие дерева отрезков для подсчёта выпуклой оболочки).

На контесте я не думал над D, как не над жадником. На разборе Андрей рассказал, какие формулы брались за прямые и я осознал, что даже не пытался расписывать формулы подсчёта ответа для двух каких-то вершин. Но если бы я даже додумался до этого, до её бы не сдал, так как у меня не было практики с деревом Ли Шао. По задаче С нечего говорить, так как там просто бы разбор большого кол-ва случаев впридачу с математикой.

По итогам у меня стало: 100/100/100/31 + 100/100/50/34

За второй день я был доволен, так как его отрещал на максимуме, а вот за первый день мне было обидно по задаче D, где я придумал фулл, но не отдебажил код до рабочего состояния(я этот день решал без шоколадки

).

Сборы к области я писал на более-менее стабильный топ-3 Гомеля, но по областной олимпиаде я топ-5 Гомеля, что не оправдало мои ожидания

Мой профиль

Александр Лосев:

Первый день:

Пришёл на контест без воды и без шоколадки

А остальные из дома брали? Может для надёжности так и делать?

1) В задаче А я минут 10-15 тупил и не мог нормально реализовать решение

Надо это исключить как класс. С первой минуты работать внимательно и собранно на КАЖДОЙ ТРЕНИРОВКЕ.

минут 15 дебажил код, так как ошибся в формулах для проверки правильности квадрата.

И снова чуть медленнее, внимательнее к деталям.

Чтобы сдать последнюю задачу, оставалось 3 часа и ~30 минут.

Круто - значит уровень есть. Надо только его показывать!!!

Небольшое отступление

В 1999 году Слава Вдовиченко на IOI сидел рядом с китайцем.
Славу поразило - китаец первые 3 часа не прикасался к клавиатуре - думал.

Наверно это главное, чему сейчас нужно научиться и Саше, и всем остальным
(пытаясь развивать навык на каждой тренировке и анализируя результат).

ДУМАТЬ без страха перед временем и сложностью задачи.

Изначально написал группы, где заходил обычный брут за O(8 * q * n).

Очень правильно, так проверяется окончательно, что правильно понял условие задачи.

Пытался придумать фулл, не сдавая больше никаких групп,

А вот это возможно неправильный ход.
Надо думать на группами!!! Писать необязательно, а думать надо - именнно потому, что думая над группами

зачастую можно выйти к фулл решению.

но у меня почему-то не заходило решение и я пытался отдебажить его до конца контеста.

Это тоже надо исключить как класс - должна быть стратегия тестирования (диагностирования и поиска ошибок) и инструментальные средства (вплоть до автоматического сравнения брута с конструктивом).

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

Примерно за час до конца контеста я осознал фулловое решение

так и бывает (историю про лягушку в сметане знаете?)
https://nm-kotlyar.livejournal.com/50295.html

Я принял решение отдебажить код на группу ai <= 1, но до конца контеста так и не отдебажил.

И снова отладка. Кстати 34 отсылки - тоже следствие непоставленного процесса отладки программ, включая автоперетестирование на всех ранее подготовленных тестах после проведенных изменений исходника и/или ПЕРЕД отсылкой в тест-систему.

второе решение было такое же, как я придумал на контесте

Отладка - твоё слабое место сегодня. Надо поработать над ним.

Второй день:

но у меня ни прошлая, ни эта группа не заходили. В итоге бага была из-за переполнения(я не брал число x и число y по модулю, когда их перемножал по модулю, (x, y <= 1e18)).

И снова отладка хромает - ты должен научиться легко и быстро находить такие ошибки в своих программах (а для командной и в чужих

)

так как я не особо дружу с математикой(задача С) в олимпиадной проге.

Отныне надо менять отношение к этому вопросу - и целенаправленно подтягивать олимпадную математику.

Опять же предлагаю посвятить специальное теоретическое занятие (в может и не одно) олимпиадной математике.

там фулл - дерево Ли Шао(подобие дерева отрезков для подсчёта выпуклой оболочки).

Надо разобрать его и сдать задачу - уже можно и на DL.
Кроме того, просьба к Андрею - составить список названий теоретических вещей, которые он знает, а остальные нет. В порядке убывания частоты применения в олимпиадах. Обсудить список на теории, возможно кто-то, например, Антон, сможет дополнить его. И затем решить какие вопросы на теории всё-таки разобрать.
На республике могут пригодиться эти новые теоретические знания.

и я осознал, что даже не пытался расписывать формулы подсчёта ответа для двух каких-то вершин.

Ещё один прокол - учиться думать и не бояться думать - НА КАЖДОЙ тренировке.

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

Ну то есть эту задачу ты обязан сдавать, а с математикой подружиться.

Резюме

1. Разработать технологию и инструментальные средства локализации ошибок, автопроверку корректности работы на всех подготовленных тестах (сохранять их по мере создания). СОВЕРШЕСТВОВАТЬ всё по результатам каждой тренировки.

2. На каждой тренировке тренироваться ДУМАТЬ над сложными задачами
- сначала засылаем брут
- думаем над группами
- пока и если фулл не пришёл в голову - засылаем группы.

3. Подтянуть олимпиадную математику.

4. Подтянуть теоретическую подготовку.

5. Работать чуть основательнее, вдумчивее, пусть даже чуть медленнее
- чтобы не совершать глупых ошибок, на поиск которых потом тратится время и нервы.

Мой профиль

Дорешал 1_4 своим способом и ДПшкой. На контесте я набагал с ДОшкой, а дома я с нуля код написал и он с первого раза заработал.

Мой профиль

Здорово только надо НА ОЛИМПИАДЕ так же делать.
"Дорога ложка к обеду"

Мой профиль

Расскажу, как я написал IZHO 2020 и область 2021.

IZHO, день 1.
Первые впечатления о задачах:
1) смотрится как изик, сразу несколько жадных идей;
2) задача на запросы, я такое люблю;
3) какой-то сложный конструктив, очень похоже, что подгруппы должны привести к фуллу.

Начал думать над всем. Написал легкий брут на 2-ую. К +- 1.30 сдал полное решение по первой. На 3-ю знал, как написать на 7, но пока решил подумать над 2-ой. Где-то к 2.30 придумал полное по задаче и начал печатать. К +- 3.15 закончил, отправил -- TL (в задаче стояли довольно узкие ограничения по времени). Немного пооптимазил и получил 75 балла к 4 часу. Было 2 варианта: 1) написать брут по 3-ей; 2) исправлять решение по 2-ой. Я решил попытаться исправить решение до 4.30, если нет, то взять гарантированные баллы по 3-ей. У меня получилось исправить решение по 2-ой где-то к 4.30 и я начал быстро печатать решение по 3-ей. К 4.45 сдал на 7. Еще за минут 10 написал решение на еще 9 баллов.

Итог за 1-ый день: 100 + 100 + 16 = 216. В целом неплохо, по 3-ей разбирал решение. Было реально набрать еще 12, но дальше уже прям оч сложно набирать баллы.

IZHO, день 2.
Первые впечатления о задачах:
1) Какая-то комбинаторика;
2) может быть ДП;
3) Задача на силу рук (если не на фулл, то на много баллов)

На этом туре не было ни одной простой задачи (в отличие от 1-ого, где была задача А), поэтому над всеми задачами сразу начал думать по очереди (на каждую минут по 10-15). Сдал брут на B на 20. Где-то к 1.30 придумал интересную подгруппу на А, попробовал написать -- WA. Решил написать брут по А (на 18 баллов), чтобы проверить решение на подгруппу. Сдал его на +- 2 часу и через минут 5-10 исправил свое предыдущее частичное и в сумме получил 34 бала. К этом времени я знал решение по С на 62 балла, но нужно было много печатать. Также я знал решение на B на 59 баллов, поэтому решил написать бруты, а потом за оставшееся время попыться еще набрать баллы. Начал с B и получил еще несколько легких подгрупп (в сумме на 40 баллов) к +- 2.50. Дальше я начал печатать C. Там было много структур и окончательно я сдал С на 62 балла за +- 45 минут до конца. Тут уже я написал брут на B на 19 баллов. И я не смог найти в нем ошибку до конца контеста. Он ловил WA.

Итог за 2-ой день: 34 + 40 + 62 = 136. Результатом очень не доволен по следующим причинам:
1) по задаче B я не получил свои 19 баллов. Во время контеста я успел ассертами проверить, и у меня каким-то образом сумма положительных величин стала отрицательной.
2) по задаче A я набрал всего лишь 34 балла. После контеста я поговорил со Стасом Дамасевичем и я придумал все, для 81 балла, только в одном месте нужно было рассматривать ребра между вершинами разных цветов, а я рассматривал между вершинами одного цвета;
3) по задаче B на 100 тоже думал в нужную сторону, но не смог свести к СНМ по событиям.

Суммарно за 2 дня 352 балла и золотая медаль, но я мог намного лучше.

Область 2021

1-ый день
3 задачи были совсем простыми, закрыл их за минут 45. А потом пришла задача Д. Сходу придумались подгруппы с брутом, на a[i] <= 1 и когда нет xor-операций. Написал сначала брут для проверки идеи. Потом начал думать над фуллом и за весь контест не смог придумать полное решение. Где-то за 1.5 часа до конца написал все бруты окончательно (суммарно на 44 балла). Не знаю, как вышло, что я не смог свести к полному решению, потому что я придумал ДП, когда нету xor-операций и ДО для a[i] <= 1, а если их объединить, то как раз получается полное решение.

2-ой день
2 задачи совсем простые. В С сразу было понятно, что нужно поисследвать. В D сразу понял, что задача на силу рук. Где-то к +- 1 часу от начала контеста вывел все необходимые формулы в D и начал печатаь. В +- 2.20 отправил полное решение -- WA. Еще +- 30 минут искал ошибку и, наконец-то, получил 100 баллов. Потом пошел думать С. Написал брут для проверки идеи. Потом поисследовал и нашел закономерность для s = 0. Дальше стал искать закономерности и свел к задаче "проверить кол-во чисел на отрезке, у которых определенные биты в двоичной записи равны 1". И вот тут наступила роковая ошибка. Я пытался вывести общую формулу для этой задачи, а нужно было просто написать ДП.

Как-то так и закончились 2 эти олимпиады. За 2 олимпиады у меня было 3 задачи, в которых мне оставалось совсем чуть-чуть, но я не смог их дожать до конца. И меня это пугает, потому что я пока не знаю, как с этим бороться. Сейчас пока планирую начать писать как можно больше 5-ти часовых контестов (возможно с опытом придет решение этой проблемы).

Мой профиль

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

Расскажу, как я написал IZHO 2020 и область 2021.

IZHO, день 1.

по 3-ей разбирал решение. Было реально набрать еще 12, но дальше уже прям оч сложно набирать баллы.

А на какую тему задача? Нужно было знать какую-то новую теорию?
Досдавать её вообще не собираешься?

IZHO, день 2.

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

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

я придумал все, для 81 балла, только в одном месте нужно было рассматривать ребра между вершинами разных цветов, а я рассматривал между вершинами одного цвета;

Обидно. А как можно было догадаться?

3) по задаче B на 100 тоже думал в нужную сторону, но не смог свести к СНМ по событиям.

Мне кажется, эту задачу надо на теории ребятам рассказать - "СНМ по событиям" может пригодится

Область 2021

1-ый день
задача Д. Не знаю, как вышло, что я не смог свести к полному решению, потому что я придумал ДП, когда нету xor-операций и ДО для a[i] <= 1, а если их объединить, то как раз получается полное решение.

Надо подумать - как надо действовать в таких ситуациях, чтобы придти к решению (проблема схожная 81-бальной IZHO-задачей)

2-ой день

Потом пошел думать С. Я пытался вывести общую формулу для этой задачи, а нужно было просто написать ДП.

И снова - выбрано неверное направление и идёшь по нему не сворачивая.
Может добавить в тактику в таких сложных ситуациях "встряхивание": вышел в туалет, перекусил, отвлёкся и начал думать о задаче "с чистого листа", чтобы придти к новым идеям. Кстати у тебя было ещё "набрасывание идей" в начале контеста - сейчас ни разу не написал об этом.

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

Ты знаешь проблему - значит уже начал бороться.

Сейчас пока планирую начать писать как можно больше 5-ти часовых контестов (возможно с опытом придет решение этой проблемы).

Не согласен, знаешь анекдот про прапорщика "что тут думать, трясти надо".
Мне кажется, важнее зафиксировать, анализировать и поправлять тактику. И, прежде всего, добавить туда "встряхивание".

Мой профиль

Я сейчас тоже "набрасываю идеи", но все равно сложно начать думать над задачей в новом направлении.

Мой профиль

Область 2021.

1-ый день:
Первые 2 задачи были совсем простые, справился с ними где-то за 15 минут. Задача С была тоже простая, но я изначально написал на неё брут, чтобы проверить правильность подсчёта диагоналей. Дальше без особых проблем сдал на полный балл. Оставалось где-то 3 часа 50 минут и задача D. Я сразу заострил своё внимание на то, что длина не больше 8. Так я пришёл к решению: "Проверять все возможные последовательности". Я насчитал, что всего их 128(256, узнал, что ошибся уже после контеста).Но даже 128 было достаточно много и не укладывалось в TL. На этом же этапе я придумал простой, но как оказалось, очень действенный отсекос. С ним я не смог оценить точную асимптотику, но немного поисследовав, я решил, что это достаточно быстро для полного балла. Прошёл где-то 1 час и 30 минут, и я начал писать решение. Где-то через 30 минут решение было готово, но оно ловило TL. И тут я заметил, что решение проходило подгруппу с полными ограничениями, только вот без операций xor.Так я понял, что где-то не оптимально реализовал проталкивание с xor-ами.Это оказалось правдой. Всё исправил, и решение зашло на полный балл.

2-ой день:
Первые 2 задачи снова были простыми, разобрался с ними за 20 минут. Прочитав задачу С: вероятно ДП, нужно много исследовать. Написав простые подгруппы, я начал исследовать задаче брутом. Тут придумал решение для случая s = 0, написал, зашло. Дальше, на протяжении следующего часа, ничего вразумительного я не нашёл. Оставалось ещё 3 часа и я решил перейти на задачу D, и вернуться на задачу С попозже. Написав подгруппы, я начал думать над полным решением. Тут меня посещало много разных идей, но только одна была хоть как-то близка к полному решению. На этом этапе я придумал как считать для вершин, где одна из них будет предком другой, но для другого случая нужно было просто раскрывать формулу, но как-то до такого просто действия и не дошёл(на этом этапе я подумал, что "захожу в дебри" и решил переключиться). Тогда оставалось где-то 1 час и 20 минут до конца. Подумав 20 минут над задачей С, действительно близкого к полному решению ничего не придумал. Тогда я окончательно сосредоточился над задачей D, но к последней идее уже не возвращался. Последние 20 минут пихал решение с жадосом(написал его с решения на подгруппы за 2-5 минут).

Итог: Наверное только во второй день я критически ошибся, что не пошёл дальше с решением на D, может позже и догадался бы раскрыть формулу. Знаний, чтобы решить эту задачу у меня хватало. По задаче С к полному решению я был далёк.

UPD: 2_4 дорешал.

Мой профиль

Отчёт за третий этап респы 2021

баллы: 100 100 100 100 100 100 100 34

У меня на обоих турах были шоколадки, поэтому написал относительно неплохо, хотя можно было и лучше )

В первый день быстро придумывал и сдавал всё, закрылся за полтора часа с четырьмя first-ac. Частичные решения не сдавал.

Во второй день задачи были сложнее (кстати, странно, что не дали открытые тесты).

2-1 и 2-2 получились за 14 минут.

2-3 сразу подумал о префиксных ксорах, но конкретнее ничего не придумывалось, поэтому решил, что прикол в их вычислении. Вывел в консоль, так и оказалось. Зависимость от двух последних битов параметра, то есть на пару чисел вырисовывалось 16 случаев. Начал разбирать их лапками. 4 из них решались с помощью дп по числу (довольно очевидного), остальные были плюс-минус однообразные. Через боль и дебаг в 2:21 я закрыл третью задачу.

На 2-4 оставалось полконтеста. CHT распознал почти сразу, решил проверить правильность формул на частичных. Поймал баг, пересчитал, формулы были неправильные. В итоге доисправлялся до 3:48, когда частичное с моими формулами зашло (34 балла). Дальше что-то пошло не так. Оптимизация решения состояла из двух частей, когда пара вершин предок-потомок и когда два независимых поддерева. Второй случай придумал ещё до сдачи частичного, через дерево Ли-Шао. А вот с первым я затупил. Более лёгким подходом, который я не заметил, было рассматривать перебор верхней вершины (которая предок), и относительно неё искать оптимальную снизу. Тогда это возможно реализовать сливанием поддеревьев small-to-large. Я же пытался сделать наоборот, искать верхнюю относительно нижней. Для этого сначала я пытался поддерживать стек выпуклой оболочки во время обхода дерева, но потом дошло, что это в некоторых случаях близко к квадрату. Тогда пришла тупая идея — строить второе дерево по прямым (чтобы любой путь в нём от корня вниз был какой-то оболочкой), а диху по стеку заменить на двоичные подъёмы. С этой идеей я и провозился до конца. Возможно, так тоже можно было сдать задачу, но я не успел. Вдобавок, за минут 10 до конца я обнаружил, что вместо нижней огибающей поддерживал верхнюю, а исправить все с этим связанные детали и закодить вторую часть решения с лишайником уже не оставалось времени. За эти 10 минут пытался придумать полностью другое решение (ну а вдруг всё-таки жадос).

Так и было слито первое место.

Мой профиль

Третий этап Республиканской олимпиады 2020-2021

Начитавшись и наслушавшись мотивационных речей о советах к регионам, я все равно пришел на первый тур слегка взволнованный (11-ый класс как бы и последний шанс)

Первый тур
Начал очень плохо. Из-за волнения я запутался в мыслях и в течении первых 20 минут не мог нормально понять условие задачи A. В итоге решил пару минут забить на задачи и перевести дух, чтобы успокоиться. Дальше прочитал B и сдал сразу же. Понимаю, что сдать B, но не сдать A, это как-то неправильно. Просидев над A еще 30 минут, я ее наконец-то сдал. Дальше прочитал С. Идею придумал моментально, но кодить не стал и решил прочитать D, чтобы попытаться набрать баллы (меня что-то "торкнуло", что с задачей С будут проблемы, и я не ошибся). За 10 минут взял 22 балла и пошел кодить С. За 1:20 я закодил решение, которое словило TL (решение было за O(N * M * log(min(N, M)))). Исправил я это, просто переписав векторы на статичные массивы. Но я словил сначала RE, а потом WA. В итоге, спустя 50 минут после первой посылке по C, я наконец-то ее сдал, написав решение за O(N * M) (к такой асимптотике я пришел, когда написал максимальный тест, где матрица - шахматная доска. Скорее всего, если бы я этого не сделал, то я бы еще долго возился с этой задачей). Потом через 1:20 я сдал D еще на 13 баллов и до конца контеста просто пытался придумать полное решение, т.к. понимал, что если и придумаю, то закодить не успею.

По итогу, 100 + 100 + 100 + 35 за первый тур. Неплохо, но можно и нужно было лучше, т.к. я был близок к полному решению (почти придумал, как считать ответ без операций "xor")

Второй тур

Забыв про первый тур (на удивление, это у меня легко получилось), я пришел на второй тур уже спокойный и не волновался. За 10 минут сдал AB и получил First-AC за них. Оставалось 4:50 на CD. Первым делом я решил прочитать обе эти задачи, чтобы понять, на какой из них будет проще получить баллы. На C придумались префиксные суммы и я решил написать их и получить 34 балла, что я и сделал. Потом я начал писать D за O(N^2). Сначала отправил это решение, а потом заметил группу, где в тестах нужно найти только максимальный ответ. Написал этот случай, получил в сумме за эту задачу 34 балла и начал писать группы для C, т.к. на D оставалось только полное решение. Через 50 минут после разбора случаев, написания кода, потраченных нервов, и стресс-тестинга, я сдал C на 50 баллов и там тоже оставалась группа для полного решения. Я подозревал, что там будет что-то связанное с ДП по числу, поэтому решил посидеть подумать над D (т.к. в ДП я не очень силен). В D было очень много идей, но лишь некоторые я решил реализовать. Когда я заканчивал каждую идею, то я начинал понимать, что они неправильные, т.к. "выплывали" тесты, на которых решения могут ломаться. Дальше до конца контеста я прыгал между задачами С и D. В оставшиеся 15 минут я сел думать над полным решением по D, т.к. С я не успел бы в любом случае. Спустя 7 минут я решил расписать формулы для подсчета ответа. Как потом оказалось, там было уравнение прямой, что я не заметил (вроде как я начал думать о чем-то другом).

Итог, 100 + 100 + 50 + 34 и 2 First-AC (вроде ничего "сверхъестественного", но приятно).

Выводы за эти 2 тура:
0. Волноваться - очень плохо. Но и нельзя быть уверенным на 100%, т.к. ты начинаешь расслабляться. От волнения нужно как-то избавиться, чтобы не было похожей ситуации на 4-ом этапе ("может тоже ходить к психологу, как Андрей?))").
1. Очень мало практики в написании кода. В 1-3 можно было написать ДП намного проще, а я все усложнил.
2. Писал код сразу же, как только придумал идею. Я считаю, что стоит посидеть лишние минуты 2-3 и обдумать идею до конца, чтобы не было таких ситуаций, что замечаешь ошибку после того, как закодил половину задачи.

Выше я писал, что начитался мотивационных речей. Если кому-нибудь интересно, то можете почитать (лично мне они очень сильно помогли)
Как затащить регион
______________________
Жизнь - игра. Сюжет - так себе, но графика потрясающая.

Мой профиль

01.01.2021 - 18.01.2020

До этого уже писал про область и Жаутыку, теперь расскажу, что еще делал в это время.

Дорешка:
1) https://codeforces.com/contest/1400/problem/G, интересная задача на вкл-искл + ДП;
2) задача B 2-ого дня Жаутыковской олимпиады (СНМ по событиям);

На длинном туре открытой олимпиаде сдал задачу H на 100 баллов.

Написал atcoder beginner contest 187. Это контест для новичков на atcoder. Сдал все задачи за +- 37 минут. Как я уже и говорил, на atcoder есть хорошие Grand контесты, но чтобы в них участвовать мне нужно сначала поднять какой-то рейтинг (для этого я и написал beginner контест).

03.01 написали личную тренировку IOIP2018_21Jan. Сдал все задачи за +- 2 часа. A,B нужно было реализовать то, что сказали. В C нужно было написать алгоритм Манакера (поиск всех палиндромов строки). В Д нужно было применить стандартную оптимизацию ДП на дереве с n^3 -> n^2.

Написал виртуалку atocder Grand 51. Не сдал ни одной задачи, был очень близок к B (ее уже дорешал). Еще дорешал А, также планирую дорешать C.

17.01 написали 1-ый день открытой олимпиады 2018 года. Получил 100 + 100 + 100 + 58 баллов, что довольно неплохо. В задаче Д нужно было придумать красивую "Разделяй-и-Властвуй" идею. Уже дорешал эту задачу.

Мой профиль

15.01.2021 - 19.01.2021

В воскресенье писали московскую открытку. Написал плохо, так как застопорился на Сшке и не смог придумать жадность

Дорешка:
1) дорешал воскресную олимпу на фулл
2) дорешал 2_4 области через small-to-large (дорешивал со спокойной душой под музычку

)
3) дорешал A-D с atcoder regular 111
4) https://codeforces.com/contest/1473/problem/F , интересная, по-моему мнению, задачка на min-cut

Написал codeforces round 696:
В начале сильно тупил, поздно сдал А, после её сдал быстро В, потом долго тупил над Сшкой, сдал её на втором часу. Почти моментально придумал идею с ДОшкой(у остальных какие-то жадники, но в них тоже стоит разобраться) на D, тщательно перепроверял все формулки, минут 20 потратил на перепроверку кода. Заслал код за 2 минуты до конца контеста и тестировалось около 4 минут. Когда протестировалось, мне выдало RE. После контеста заслал в дорешку тот же код, но увеличил ограничения в два раза(на контесте я ставил 2е5, как было сказано в условии) и он зашёл.

Мои выводы:

1) Нужно сходить к психологу проконсультироваться по поводу "волнений на контесте", а то я заметил, что, когда я спокоен, у меня всё нормально решается.
2) Никогда не спешить писать код на непроверенную идею

Мой профиль

19.01.2020-31.01.2020

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

И так, дорешка:
1) https://codeforces.com/group/Uo1lq8ZyWf/contest/311770/problem/A задача 2_1 с IZHO 2021. Интересная задача на комбинаторику;
2) https://codeforces.com/group/Uo1lq8ZyWf/contest/311770/problem/C задача 2_3 с IZHO 2021. Интересная задача на структуры данных и немного комбинаторики;
3) 1_4 области (задача ДП + ДО);
4) 2_3 области (разбор случаев + ДП);
5) https://atcoder.jp/contests/abc189/tasks/abc189_f задача на теорию вероятности (сводится к системе уравнений) с atcoder beginner contest 189;
6) https://codeforces.com/contest/1400/problem/F задача на алгоритм Ахо-Корасик;
7) https://codeforces.com/contest/1466/problem/G задача с goodbye 2020 на ДП;
8) https://www.codechef.com/problems/ARCRT задача на комбинаторику + Разделяй-и-Властвуй (dynamic connectivity, если быть точнее);
9) https://www.codechef.com/problems/EQLGIFTS задача с january cook off Meet-in-the-middle + принцип Дирихле;
10) https://codeforces.com/gym/102904/problem/B задача с 4-ой командной олимпиады на разделяй-и-властвуй внутри разделяй-и-властвуй + дерево Фенвика;
11-14) https://codeforces.com/contest/1477, ABCD задачи с codeforces 698 Div 1. A и С конструктивные, B немного идеи + ДО, D -- идея + придумать алгоритм построения остова для почти полного графа + придумать алгоритм разбиения дерева на много звезд;

Написал atcoder beginner contest 189 сдал 5/6 задач, в 6-ой была теория вероятности в которой я пытался придумать ДП с префикса, а нужно было написать ДП с суффикса. Причем я писал такую идею в лист идей, но не взялся за нее, потому что ДП с префикса выдавало близкий к нужному результат и мне казалось, что еще "чуть-чуть" и оно заработает.

Написал codechef january cook-off. Сдал 4/6 (6-ую уже дорешал). Что хотелось бы отметить: на контесте у меня был затор на задаче B. Ее сдавало много людей, а я никак не мог придумать. И я решил попробовать воспользоваться советом психолога: рассказать кому-нибудь решение задачи. Смысл в том, что когда ты кому-то рассказываешь решение, то возникает 2 больших бонуса:
1) ты сам разбираешься в своих мыслях (приводишь их в более структурированный вид);
2) в голове срабатывает какая-то фишка, что если ты рассказываешь решение, то значит ты его уже придумал. Сложно это описать, но ты настраиваешься, что сейчас расскажешь решение и мозг на это реагирует, что раз нужно рассказать решение, значит ты его уже придумал. И ты как-то придумываешь решение

В общем, я решил рассказать решение маме и за минут 5-10 просто рассказывая все, что я придумал по задаче, я придумал полное решение (и по итогу сдал эту задачу на контесте). На олимпиаде, к примеру, можно просто представлять, что ты рассказываешь кому-нибудь решение и добиться такого же результата.

Написал 1-ый отбор на ИОИП 2021. Сдал все задачи за +- 139 минут. Получилось обидно с задачей D: у меня по ней было first-ac на +- 71-ой минуте, но после того, как я закрылся, я решил проверить более быструю идею на задачу D и перезаслал ее. Из-за этого мой first-ac отдали другому человеку

(потому что последняя отсылка у меня стала с большим временем).

Мой профиль

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

в 6-ой была теория вероятности в которой я пытался придумать ДП с префикса, а нужно было написать ДП с суффикса. Причем я писал такую идею в лист идей, но не взялся за нее, потому что ДП с префикса выдавало близкий к нужному результат и мне казалось, что еще "чуть-чуть" и оно заработает.

А можно теперь "пост-фактум":

1. Написать, почему в этой задаче ДП с суффикса правильно, а ДП с префикса - неправильно.
2. Сделать попытку ОБОБЩЕНИЯ - когда надо писать ДП с суффикса, а когда - ДП с префикса.

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

В общем, я решил рассказать решение маме и за минут 5-10 просто рассказывая все, что я придумал по задаче, я придумал полное решение (и по итогу сдал эту задачу на контесте). На олимпиаде, к примеру, можно просто представлять, что ты рассказываешь кому-нибудь решение и добиться такого же результата.

Можно ещё попробовать не "представлять, что ты рассказываешь кому-нибудь решение", а подробно зафиксировать на бумаге этот рассказ.