Форум DL

Мой профиль

Долги:

С неоф. сборов:
   E с 19_Rui4 - сложное ДП на дереве
   D c 18_Rui2 - ДП

С оф. сборов:
   D с 24_Rui2 - оптимизированный перебор

Со сборов к респе:
   D1 с 24RU
   C2 с 24RU
   E  с 24_IOIP - поиск макс. клики            + 19.02.25

С воскресок к респе:
   D c 24_COCI2_Nov - dp


С командных:
   E с ФПМИ_7 - meet in the middle, перебор    + 19.01.25
   L с ФПМИ_7 - перебор                        + 30.01.25

С воскресок к миру:
   P1-3 с USACO_25_Feb

С CF:
   https://codeforces.com/problemset/problem/1945/G - придумал декартку, но можно легче

Мой профиль

Геннадий Марцинкевич:

Пятница.
Первые 3 задачи я сдал меньше, чем за час. Прочитал четвёртую, ограничения показались маленькими (900), поэтому подумал, что куб зайдёт. Попытался запихать, но не получилось. На 3-ем часу придумал нормальное решение, но подумал, что оно вряд-ли пройдёт (т. к. медленное решение летело не по времени, а по не времени (WA, RE, ML, я не знаю)), но попытавшись ещё, и подумав над новым решением, понял, что оно скорее всего пройдёт, и с первой попытки сдал.
Вывод: меня запутали ограничения: я подумал, что оно будет работать быстро, а оно слетало по WA. Одним словом, была какая-то ошибка, которую я не смог найти, или вообще нельзя было исправить, написал новое решение и оно зашло. Надо просто быстрее переключаться между решениями

Надо ОБЯЗАТЕЛЬНО разобраться, в чём была проблема в первом решении.
На олимпиаде всё сделал правильно.
Но после олимпиады НАДО РАЗОБРАТЬСЯ.

Мой профиль

Геннадий Марцинкевич:

Дорешать:
E с 19_Rui4
D c 18_Rui1
D c 18_Rui2

Надо темы вписать

Мой профиль

Понедельник.
Решил 3 задачи за 3 часа (мог и быстрее, но что-то затупил над B-шкой, долго думал, потом плюнул и написал "неполное" решение, а оно зашло на фул, и только потом допёрло почему). D была интересной, но я её не придумал. Почему? Никогда не использовал приём разбиения запросов на блоки, и обработки постепенно

Мой профиль

Вторник.
Первые 3 задачи сдал за 1:40. Но D придумал только под конец, и то на 78 баллов. Не хватило времени, чтобы дописать. Как добить до фула пока не знаю

Мой профиль

Долги:

с оф. сборов:
C c 22_IOIP - математика, z-функция +19.02.25
D с 22_IOIP - ДО +19.02.25
c воскресок:
E c 24_COCI5_Mar - числа Гранди +19.02.25
D c 24_COCI1_Oct - включение-исключение +26.02.25
C с 24_COCI2_Nov - математика
D с 24_COCI2_Nov - жадник
E с 24_COCI2_Nov - умный рандом

Мой профиль

Открытая олимпиада по информатике.
День 1:
За первый час я сдал D. Понял, что A - гроб, поэтому сразу отложил. Думал сразу (поочерёдно) над B и C. Придумал B, написал, сдал (время не скажу, но, примерно, 2.5 часа). Долго думал над C, придумать не смог и до конца контеста набирал неполные баллы (получилось 82 - это максимум неполных баллов). Затем стал писать А, но не успел.
День 2:
За 1.5 часа сдал B и C. В D меня запутала фраза (если максимумы равны, берите тот, что стоит раньше. Я подумал, что это на что-то влияет, и написал только на 4 (мог больше)). Но вот A понравилась, я подумал, что она лёгкая. Придумал решение для конденсированного графа (25 баллов), но для одной компоненты не смог. Под конец стал писать полный перебор, но тоже не успел.

Выводы:
Нужно больше времени оставлять на неполные баллы. И надо научится не допускать таких тупых ошибок: запутывании в условии и выбора задачи для фула или неполных баллов (а то большую частб 2-го дня я думал над самой сложной задачей контеста)

Мой профиль

Респа 2025:
День 1: A, B закрыл за 2 часа. Можно было и быстрее, но я пытался всё доказать, чтобы не сделать багов, поэтому считаю это адекватным результатом. C придумать так и не смог (это была конструктивная интерактивка на поиск перестановки), поэтому брал частички. В D я не заметил,что можно забыть об изначальном массиве, и работать только с преф. суммами. Тогда было бы около 70 баллов.

День 2: A я сдал только через (вроде-бы) полтора часа (быстрее вряд-ли бы получилось, это был чистый конструктив). Над B я долго думал, но по итогу начал решение в лоб за O(n^2), хотя сам думал, что оно работает за линию. На 4-ом часу я понял, что оно работает за квадрат, но как соптимизировать я не придумал (тоже что-то типа конструктивна, только не глобально, а только конструктивно придумать оптимизацию (рассматривать только вершину 1, и его соседей)). C была действительно сложной. Я взял 2 частички на 7+5 баллов. Мог бы ещё 2 на 11+18, но устал и придумать не смог. Аналогичная ситуация с D2. Взял 14 баллов частичками. Если бы кое-что заметил, мог бы ещё 8. Вряд-ли я бы взял ещё что-то, но, в принципе, это не невозможно.

Итого я мог добрать 48 (C1) + 70 (D1) + 31 (B2) + 29 (C2) + 8 (D2) = +186 баллов

Почему я плохо отрешал:
1. Вся респе была конструктивном. Достаточно было заметить 1 деталь, и задача решалась либо на фул, либо на 70 баллов в лёгкую (за искл. C2/D2 - там нужно было заметить парочку вещей).
2. Практически было задач на структуры, алгоритмы, а когда были, то главная сложность была не в них, или реализации, а в заседании этих пары деталей, без которых задачу не решить. В прошлом и позапрошлом годах задачи были поинтереснее, менее конструктивные, где один может придумать, а другой нет.
3. Не было открытых тестов. Я вообще планировал на них взять довольно много баллов. Это, конечно, не отговорка, но тоже сильно грустно.

Мой профиль

Геннадий Марцинкевич:

Респе 2015:
Почему я плохо отрешал:
1. Вся респе была конструктивном. Достаточно было заметить 1 деталь, и задача решалась либо на фул, либо на 70 баллов в лёгкую (за искл. C2/D2 - там нужно было заметить парочку вещей).
2. Практически было задач на структуры, алгоритмы, а когда были, то главная сложность была не в них, или реализации, а в заседании этих пары деталей, без которых задачу не решить. В прошлом и позапрошлом годах задачи были поинтереснее, менее конструктивные, где один может придумать, а другой нет.
3. Не было открытых тестов. Я вообще планировал на них взять довольно много баллов. Это, конечно, не отговорка, но тоже сильно грустно.

К сожалению, для участников и тренеров - курс на конструктивы - это МНОГОЛЕТНИЙ ТРЕНД международных и, соответственно, республиканских олимпиад.

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

Почему это "к сожалению" для участников ты сам объяснил.
Почему лично для меня "к сожалению" как для тренера.
Потому что возникает очень сложный вопрос: "как же развивать умение решать конструктивы"?

Я, как тренер, планирую изучать этот вопрос.
А пока для Вас - участников - знаю только такие ответы:

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

Ну и тебе лично предлагаю переходить от слов к делу.
До отбора к миру в дополнение к плановой работе по решению/дорешиванию воскресных олимпиад.
Решать без кодирования задачи на «конструктивы» и только их.

Сначала пытаешься написать собственную стратегию поиска решений конструктивных задач.
Далее только придумывание – берёшь три штуки – думаешь два часа – читаешь разбор, если не придумал.
Обязательно пополняешь собственную стратегию.

А ещё сначала почитать эту тему
https://dl.gsu.by/NForum/posts/topicshow/4178.dl?postid=112813#112813

Мой профиль

Спасибо. Вот, что я для себя отметил:
1. Не нужно думать над задачей обобщённо, т. е. пытаться сразу придумать правильное решение (если получается, то замечательно, но если это жёсткий конструктив, надо идти постепенно).
2. Надо делать смелые, очевидные предположения, и пытаться от них отталкиваться. Если данное предположение ничего не дало, не выбрасывать его, а где-то выписывать, вдруг в будущем, когда появятся новые идеи/доказательства его можно будет продлить? Или наоборот опровергнуть?
3. Не бояться делать перерывы. Если задача не решается, надо заставить себя отвлечься, сходить поесть, попить, даже если не сильно хочется, чтобы мозг просто отпустил, передохнул с предыдущих задач. Если это обычная задача (не жёсткий конструктив), я так не делаю, т. к. тратится очень много времени.
4. Не бояться делать неверные посылки. Можно (и даже нужно) проверять всякую "дичь", вдруг она что-то сильно оптимизирует (если бы я этим воспользовался, может сдал бы B2), выражать свои предположения в коде. Можно проверять их assert-ами, как вариант - если слетит по RE, значит предположение неверно (или не совсем верно (!)).

P. S. Решать больше codeforces. Сейчас мне доступен 1-ый дивизион, и там задачи уже нормальные. Садишься за контест, и можешь сразу думать над хорошими тасками. Первую можно сдать и через пол часа, и при этом получить плюс рейтинга, потому что она сложная. На 2-ом дивизионе, чтобы получить плюс, надо сдать A за 3 мин., B за 10, и т. д. При том сложности они не несут. Единственная их польза в обучении "додумывать", можно не дочитать условие или не доказать решение, но быстренько его заводить и сдать (это умение полезно для A1 и B1, к слову, т. к. Я доказывал A1 пол часа, потом плюнул, написал, что первое в голову пришло (или второе

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

Мой профиль

Как первый шаг очень хорошо.

Но надо сделать и следующие шаги.

Разбить на 2 группы советов:

1. Как учиться решать конструктивы
2. Сделать пошаговую инструкцию - как решать конструктивы

Далее почитать по предложенным мной ссылкам и возможно пополнить обе группы советов.

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

"Дорогу осилит идущий".

Мой профиль

"Как научится решать конструктивы" - вопрос очень сложный. "Как решать конструктивы" уже непростой, но всё-таки решаемый.
Я как раз таки разбил моё сообщение на 2 абзаца: как решать, и как научится. Мне кажется, что научиться можно только опытом. Где его брать? 1. Codeforces раунды. В лучшем случае 1-ый дивизион.
2. Тренировочные олимпиады (но там подобной сложности конструктивы попадаются довольно редко)
3. Архив респы. Там довольно трудные конструктивы, особенно в последние года.
4. Для уровня повыше - архив IOI
Вот вроде-бы и всё.

По хорошему, если отвечать на вопрос "Как решать конструктивы", надо делать отдельный пост в какой-то теме, или новую тему создавать. И желательно этот пост либо несколько человек должны сразу делать, либо дополнять своими методами в будущем. В предыдущем посте я расписал полезные для меня приёмы, которые увидел в Ваших сообщениях. Это то, чего мне не хватало. Но если писать о том, "Как решать" в целом, то надо писать с самого начала. Думаю, лучше это сделать очно (в воскресенье, или среду в 27 школе)

Мой профиль

А разве не полезно почитать советы других людей, начиная с Михаила Мирзаянова и извлечь что-то для себя?

https://dl.gsu.by/NForum/posts/topicshow/4178.dl?postid=112813#112813

Мой профиль

Долги 2:


С неоф. сборов:
   E с 19_Rui4 - сложное ДП на дереве
   D c 18_Rui2 - ДП

С оф. сборов:
   D с 24_Rui2 - оптимизированный перебор

Со сборов к респе:
   D1 с 24RU
   C2 с 24RU

С воскресок к респе:
   D c 24_COCI2_Nov - dp

С CF:
   https://codeforces.com/problemset/problem/1945/G - придумал декартку, но можно легче
   https://codeforces.com/contest/2104/problem/F - нашёл неправильную закономерность, как решать не знаю

Интернет-область:
   F - dp
   H - хеши
   I - не помню

Республика 2025:
   D1 на 70+ баллов - дихотомия, ДО. Если на 100, то спуск по дереву
   C2 на 100 баллов - что-то вроде ДП. Точнее не могу сказать, т. к. не знаю
   D2 на 100 баллов - не знаю, как решать, но это не должно быть сильно трудно, или по крайней мере будет интересно  

Командные:
   USACO 2024_December:
      Platinum - тему пока не знаю
   USACO 2025_January:
      Gold 3, Platinum 3 - тему пока не знаю
   USACO 2025_February:
      Platinum 2-3 - тему пока не знаю
   USACO 2025_March:
      Platinum - тему пока не знаю

Мой профиль

Как научиться решать конструктивы (что решать):

Тут я не буду писать тактику, как их решать. Это будет описано дальше. Тут я напишу только места, откуда их брать.
1. Темы в "Базовое программирование" на dl.gsu.by. Я считаю, что нужно сначала прорешать их, а уже потом беспокоиться о конструктивах. Прорешенные темы уже дадут большое прирост в решении конструктивов.
2. Раунды Codeforces. Их нужно решать параллельно темам.
3. Сложные задачи из архива Codeforces. Их я рекомендую решать уже после тем на dl. Если есть лишнее время, лучше порешать темы, будет полезнее.
4. Сложные олимпиады, заточенные на конструктивы: последние года заключительного этапа BelOI (A1 с BelOI 2024, почти весь BelOI 2025), IOI (все года, но, чем новее, тем сложнее, по моему мнению).