Форум DL

Мой профиль

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

Если задача довольно сложная или непонятная, не подходить под ваши стандартные алгоритмы, скорее всего её можно сильно упростить, заметив пару деталей. Как это сделать?
1. Покрутить задачу под разными углами: что происходит при той или иной ситуации, попробовать найти закономерность
2. Зафиксировать какое-то предположение, и попробовать его развить, основав свои дальнейшие мысли на нём. Оно может оказаться неправильным, главное, чтобы за время размышлений над ним, нашлись какие-то новые факты, зависимости, упрощения, доказательства - любая полезная информация. Обычно такие предположения очевидны, их можно предположить уже на этапе прочтения условия. Если данное предположение ничего не дало, не выбрасывать его, а где-то выписывать, вдруг в будущем, когда появятся новые идеи/доказательства его можно будет продлить? Или наоборот опровергнуть?
3. Провести исследование: написать какой-то брут, который поможет найти закономерность. Да, на это тратиться довольно много времени, в этом и сложность конструктивов.
4. Попробовать разделить задачу на подзадачи полегче и решить каждую по отдельности.
5. Если это первая задача, которая по логике должная быть лёгкой и есть предположительные идеи, которые работают на семплах, стоит попытаться их реализовать, а не сидеть пол часа над доказательством (у меня были и на этом ошибки), есть большой шанс, что они пройдут.
6. Не нужно думать над задачей обобщённо, т. е. пытаться сразу придумать правильное решение (если получается, то замечательно, но если это жёсткий конструктив, надо идти постепенно).
7. Не бояться делать неверные посылки. Можно (и даже нужно) проверять всякую "дичь", вдруг она что-то сильно оптимизирует (даже, если это звучит как бред, бывает, что доказательство находится уже после контеста), выражать свои предположения в коде. Можно проверять их assert-ами, как вариант - если слетит по RE, значит предположение неверно (или не совсем верно).

Советы:
1. Не бойтесь делать перерывы. Если задача не решается, надо заставить себя отвлечься, сходить поесть, попить, или переключиться на другую задачу, даже если не сильно хочется, чтобы мозг просто отпустил, передохнул с предыдущих и текущей задач. Если это обычная задача (не жёсткий конструктив), я стараюсь так не делать, т. к. тратится очень много времени.
2. Если пытаетесь решить подгруппы - посмотрите внимательно на ограничения! Внимательно, а не как обычно!
Например: была задача C1 с BelOI 2025. Условие пересказывать не хочу, но, если кратко, были даны операции над массивом цифр в 2^20-ичной системе счисления. Нужно было говорить значение всего числа по модулю d <= 20. В одной подгруппе d = 11. Я её пропустил, а зря: 2^20 % 11 = 1, а значит, что порядок цифр (и степеней) нам не важен, что сильно упрощало решение. И такие ошибки довольно часты.
3. Под конец олимпиады трудно придумать что-то творческое, т. к. мозг уже устал. Тут совет 1: передохните, и с новыми силами попытайтесь сосредоточиться на задаче, внимательно отнестись к каждой подгруппе, и попытаться уделить ей достаточно внимания.

Если вы хорошо решаете конструктивы/подгруппы, тут возникает вопрос: что мне делать: решать задачу на 100 или брать частички?
Ответ таков: нужен опыт, чтобы это понимать (не только в спорт. проге, но и в данной конкретной олимпиаде), ведь чем больше решаете, тем лучше вы становитесь, тем больше задач стоит пытаться решать на 100, и тем менее понятно, смогу ли я решить эту задачу, если не придумал за первые 15 мин.? Поэтому, советую, искать в таблице предыдущих годов ваших знакомых (тех, чей уровень вы знаете), и отталкиваться от того, сколько и как решили они.

Интересные приёмы:
1. Если нам нужно, чтобы после перестановки массива a или b, (a[i] - b[i]) делилось на k для всех i, можно понять, что тогда sumA - sumB тоже делится на k, и можно рассматривать только его

Мой профиль

Как решать контесты (тактика во время олимпиады):

1. Решить всякие изики.
Если доступна таблица, следить какая задача самая "лёгкая".
2. Попытаться отсортировать оставшиеся задачи в порядке сложности (если олимпиада не предполагает рандомный порядок задач, лучше довериться даному в условии).
3. Решать остальные задачи в порядке сложности. Особой тактики не дам, так как сам понял, что от них только вред. Не нужно стараться выделить на каждую задачу определённое время, и строго ему следовать. Нужно быть гибче. Лучше следовать простым советам, описанным далее.

Советы:
1. По началу я ставил себе ограничения по времени на каждую задачу, но понял, что это слишком бесполезно, да при этом ещё и "психологически давит". Поэтому я перестал так делать, и поставил другую цель: уделять каждой задаче достаточно времени.
2. Иногда какой-то конструктив, который все решают, а у тебя не получается лучше пропустить, ради более "сложной" для остальных задачи, но которая использует стандартный алгоритм, который легко (хотя бы тебе) придумать.
3. Как говорил Геннадий Короткевич, (не цитата, просто пересказ своими словами) "Нужно уделять каждой задаче минут по 10, а потом переключаться на другую задачу, чтобы быть максимально продуктивным". А вот, что он ещё говорил: "Лучший отдых - это сон". Перед олимпиадой я всегда отсыпаюсь (и даже не за день, а за 3-4, чтобы быть отдохнувшим и бодрым).

Чем проше тактика (но при этом работающая), тем лучше

Мой профиль

Отлично поработал.
Мне очень понравилось.
Но есть и замечания и предложения

1. Старые долги (что осталось ещё нерешённым) нужно СКОПИРОВАТЬ в это сообщение
https://dl.gsu.by/NForum/posts/topicshow/1019.dl?postid=118303#118303
2. Как научиться решать конструктивы (что решать)
- это не только что решать, но и как решать,
а) без кодирования 2 часа на придумывание и прочтение авторских описаний для проверки и самообучения
б) Обязательно пополнять тему «как решать конструктивы» новым опытом
в) Составить ПЛАН и придерживаться его
сколько раз в неделю и в какие дни/какое время будешь тратить эти 2 часа
до отбора к миру желательно как можно чаще – но без переутомления.
г) Как и когда будешь выбирать задачи к рассмотрению?
мои соображения
- выбирать это отдельный процесс от решения, отбор и решение могут быть в разные дни.
- как варианты
.... брать задачи с DIV1 в котором участвовал - понравившиеся задачи, но нерешённые во время раунда
.... брать задачи с DIV2 в котором участвовал - понравившиеся задачи, но нерешённые во время раунда
? как-то учитывать количество сдавших вообще или во время контеста
(идти от более простых конструктивов к более сложным)
- брать старые задачи с тегами конструктив опять-таки по возрастанию рейтингов сложности задач
- или брать три задачи с разными возрастающими по рейтингам сложностью типа 1500 - 1800 - 2100
На следующий заход можно уменьшать или увеличивать сложность
(чтобы что-то решалось для положительных эмоций, а что-то нет - для роста).

Мой профиль

План решения конструктивов:
Четверг и суббота.
Не знаю, смогу ли я решать больше 1 думательного контеста (т. к. устаю, да и ещё дела есть). Попробуем, увидим.

Мой профиль

Сегодня решал задачу, она не прошла ТОЛЬКО на одной машине: DelTA4 at NIT0, компиляторе C++17 GCC 7.3.0.
Спустя время ошибка была найдена: во всём виноваты #pragma GCC target("avx2,bmi"). Именно вкупе! Остальные optimize и target не влияют. Надеюсь это кому-нибудь поможет.

Мой профиль

О том, как я областную интернет олимпиаду решал
Дело пошло хорошо, только до 4-ой задачи. Там я прочитал в условии вместо "или" "и" и решал совершенно противоположную задачу. Даже задавал вопрос в тест. систему. После всё пошло под откос: я переключился на другую задачу: сдал G, потом "придумал" H, долго её доказывал (оказалось, что неправильно), потом долго писал, вспоминая суфф. мас., потом понял, что он не сработает. На 3-ем часа переключился на D, и "проснулся", задачи опять стали сдаваться (D, E). Потратил лишнее время на F, думая, что мы выбираем не подпоследовательности, а подмассивы... Потом вернулся на H, написал хешами, они не проходили по времени. Долго я не понимал почему, потом понял: я тупой - я возводил 26 в степень по модулю прямо в функции взятия хеша (не знаю, почему я так сделал, никогда такого не было, видимо, устал, запутался)... Оставшееся время взял частички на F (и те не все).
Проблемы: плохо читал условия, криво доказывал, делал баги, перемудривал.
Как их решать: не знаю... Давно у меня такого не было, что часть задач решались быстро, красиво, чётко, а другая часть просто жёстко тупилась и сливалась

. Наверное, стоило больше выходить отдыхать/кушать
P. S. Если бы было больше времени, я бы решил больше, наверное

Мой профиль

"За одного битого двух небитых дают"

Давай фиксировать виды ошибок, в надежде что ты не станешь повторять зафиксированные ошибки.

1. Невнимательное чтение условий
- прочитал в условии вместо "или" "и"
- думая, что мы выбираем не подпоследовательности, а подмассивы

2. Ошибки в реализации
- возводил 26 в степень по модулю прямо в функции взятия хеша

3. Недостаточный отдых
Давно у меня такого не было
Наверное, стоило больше выходить отдыхать/кушать

А в ночь перед олимпиадой ты вовремя спать пошёл?

Мой профиль

Михаил Долинский:

А в ночь перед олимпиадой ты вовремя спать пошёл?

Да, и выспался нормально

Мой профиль

USACO 2012 March
Почему я сегодня так плохо отрешал?
1. Не выспался. Наверное, потому что решал CF, долго решал D и не успел придумать E - дорешивал
2. Долго не мог придумать DP на S3 - долго искал за что зацепиться, перебирал много вариантов.
3. Придумал плохое DP на G3, не хотел писать, которое, однако, прошло за 0.5 сек (7*10^8 операций). Из-за чего не придумал нормальное? Мне показалось, что на каждом новом лифте не всегда будет уменьшаться его забитость, из-за чего оно ломалось бы и нужно было придумывать, как поддерживать минимальную забитость на префикс лифтов для каждой маски.
4. Пропустил B3, т. к. думал, что нужны все позиции на пути, а не только конечная. Почему не проверил семпл? Для этого нужен был блокнот, а я ехал в автобусе, а в кабинете решил перейти на др. задачи - они мне показались легче.

Выводы:
Раньше читать условия, не забрасывать то, что не понял/придумал сразу. Дольше думать над решениями, которые кажутся правдоподобными.

Мой профиль

Долги 3:
Важное (7):
Дорешать 2 день IOI 2025
Дорешать C, M, G с командных 2025.09.07
Дорешать остальные командные
Дорешать Минскую учебную смену
Порешать темтур теории чисел Т-поколения
Дорешать задачу E с последнего codeforces

Среднее (~11):

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

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

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

Можно отложить (2):

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

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

Мой профиль

Я весь день возился с багом в реализации задачи и хочу рассказать что было не так.
В коде был set <myStruct>. Для myStruct я определил оператор <, чтобы сет сортировал их в нужном мне порядке. myStruct состоял из 3 int-ов, однако важными для сортировки были только двое. Проблема была в том, что когда в сет попадают 2 разных объекта, и при они совпадают по сортируемым полям (но различаются по не важным/не учтённым в компаратора/операторе сравнения) сет ломается - потому что оператор == выдаёт, что они не равны,а оператор < говорит, что они не больше, не меньше - противоречие. Происходит неопределённое поведение. Поэтому вывод: если вам важна сортировка в сете (на обычную сортировку это, разумеется, не распространяется) только по части полей класса, а не по всем, это не значит, что остальные нужно игнорировать - в компараторе (он же оператор сравнения в данном случае) нужно учесть все поля, или доказать, что одинаковых элементов по проверяемым полям в сете не будет.
UPD: Я ошибся. Решая другую задачу я осознал, что проблема была не в этом - set не использует оператор ==. Вместо него используется !(a < b) && !(b < a). А в той задаче я не учёл факт равенства первых 2-ух сравниваемых значений, при разнице третьего (при этом сет как и должен был оставлял только 1 элемент из них, но по задаче нужно было их различать и оставлять оба).

Мой профиль

Как вы думаете, какой самый неприятный вердикт? WA 212, как на наклейке с Pinely? Нет, это ещё блаженство. А вот WA 2, который не можешь отловить 3 часа - вот это ад. Сегодня я решал контест. Ещё едя в автобусе придумал примерно 6 задач. Однако, смог их решить только в 4:47 (от начала олимпиады). Почему?
1. S1 - почти базовая задача на очередь, только с телепортами. Нужно было прийти из точки A в точку B, по лабиринту. В первой посылке я не учёл, что на телепортах нельзя останавливаться, но WA 2 не ушёл. Тогда я начал тестировать на своих входных данных - безрезультатно. Потом я грешил на неправильные тесты - непарные телепорты (и они там были в 12 тесте, по словам Кости) или наоборот их было слишком много, но тщетно. Многие вообще зачем-то писали set, и я уж склонялся, что для чего-то он здесь нужен. По итогу, потратив кучу времени на раздумья, был найден нерабочий тест. Ошибка оказалась не в тех специфичных и узких случаях, которые я проверял раньше. Всё оказалось гораздо проще - я проходил сквозь стены. Просто не проверял, что новая клетка не стена. Условие я понял верно, несколько раз перечитал его, решение пересматривал, но, вероятно, грешил на механику телепортов, т. к. она более необычна, чем проход сквозь стены. Мысли о них даже не посещали меня.
Как их отлавливать?:
1.1. Придумывать тесты даже на лёгкие случаи, к примеру, без телепортов
1.2. Красиво обрабатывать случаи. Что я имею ввиду: мой код очень красив, особенно, когда в нём проявляются баги. Я просто пытаюсь его упростить и сделать максимально читабельным. Но бывает некоторое я пропускаю - например, при проверке соседей в очереди не заношу новую клетку в отдельную переменную, а потом continue, если она вне поля или стена - я частенько пихаю все проверки (при этом без создания переменной) в один if с множеством &&. Я не говорю делать так сразу - это бывает долго, но, на двумерных массивах или при WA обязательно стоит так переписать.
2. В S2 вообще был рофл (если бы не хотелось плакать). Уже сразу у меня было в принципе верное решение (пусть и немного усложнённое), однако я забыл выводить '\n' в конце запросов, а также вместо Farmer John выводил просто John. Как так получилось? Невнимательно прочитал формат вывода, также в тесте не было этого случая (да, это неправильно грешить на сэмпл, но проверять своё решения на нём стало привычкой, на которую подталкивают все олимпиады - а он как раз таки состоял из одной строки, и без Farmer John).
Как исправлять это?:
2.1. Перечитывать условие и выходной формат в частности. (как бы, я так и делал, только нашёл эту ошибку крайне поздно)
2.2. Стараться копировать варианты ответа, а не вводить руками.

Пока всё, как будут ещё тупые ошибки - напишу. Буду рад советам

Мой профиль

+19 на Silver 1.
Что вообще произошло? Я ничего не мог придумать на эту задачу, поэтому решил попробовать её запихать - на usaco такое срабатывает. Но не в этот раз. По началу был WA4, потом WA5, WA6, 7. Это подстёгивало пытаться дальше, пока я не упёрся в ML8. На этом история закончилась, я пару раз попытался что-то сделать, но не помогло. Уже было потрачено примерно 16 попыток. Затем, в раздумьях над задачей и проверке гипотез израсходовались ещё 2. Затем мы с Сашей решили обсудить эту задачу и поняли, что можно написать компаратор, который быстро работает и не тратит память. Засунули его в сортировку и сдали задачу (но тут я по началу написал qSort, вместо обычной сортировки, да ещё и неправильно - почему-то забыл запускаться в правое поддерево). Какие выводы?
1. Стараться сразу брать максимальные границы, а не повышать их понемногу, чтобы тратить не 16 попыток в старании запихать, а только 3-4.
2. Если уже так долго сижу над одной задачей, стараться перепроверять моё очередное решение, потому что глаз замыливается, внимание рассеивается и становится возможным допускать мелкие недочёты, которые бы в другой задаче никогда не пропустил.
3. Больше думать, меньше гадать, стараться решить задачу нормально

Мой профиль

Ошибки на олимпиадах и как их избегать

*Под типом long в данном посте имеется ввиду int64_t - 64-битное знаковое целое число.

1. Ошибки чтения условий

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

Не замечание отсутствия важной информации
Когда читаешь условие, обычно либо тебе оговаривают подробности, по типу того, что граф связан, либо мысль сама приходит, например, при виде m = n - 1, что граф - дерево. Но иногда бывает, что авторы пытаются подловить на этом. Например, m = n - 1, но граф не связан - т. е. это не дерево, а много связанных графов, как деревьев, так и циклов. Тогда нужно себя заставлять заметить отсутствие этого уточнения и насторожиться.
Как избегать: быть более придирчивым, набираться опыта.

2. Ошибки решений

long'и
Обычно, вверху кода ставится

#define int long

и по поводу переполнений типов можно вообще почти не заморачиваться. Иногда возникает проблема с памятью, тогда define убирается и long'и внимательно расставляются вручную, там где надо. Тогда ошибок обычно не наблюдается, а если появляются - вероятнее всего, это обычная невнимательность. Однако, на IOI все задачи идут с grader'ом. Это значит, что решение работает не с потоками ввода/вывода, а представляет собой функцию, которая принимает входные данные от grade'а жури и возвращает выходные. У такого подхода есть проблемы: входные данные функции должны строго соответствовать условию - если grader передаёт int n, то функция решения должна принимать int n - long n она принимать не может. Из-за этого нельзя использовать глобальные #define int long - нужно использовать его локально через связку #define - #undef. Это делает все остальные числа 64-битными, за исключением аргументов функции. Если, например, производить операции с ними, есть шанс выйти за 32 бита.
Как избегать: все аргументы функции записывать в глобальные 64-битные переменные и работать только с ними, забывая про аргументы функции.

Деление на 0
Самый яркий пример - поиск обратного по составному модулю. Для числа a a^(-1) = a^(ф(m) - 2) (mod m). Для простых m это выливается в малую теорему ферма - a^(-1) = a^(m - 2). Но это не работает для составных m и, например, поиск обратного через классическую функцию

long inv(long x, long mod) {
    return x == 1 ? 1 : mod - mod / x * inv(mod % x, mod) % mod;
}

вылетает по RE - она предназначена для простых m - на составных x может стать равным 0 и попытаться что-то поделить.
Как избегать: запомнить формулу обратно числа через функцию эйлера и не пытаться использовать "лёгкую" функцию для поиска обратного

Выход за границы массива
Обычна данная проблема возникает с динамическими массивами, когда на автомате пишешь for (int i = 0; i < n; ++i), для vector'а, который имеет другой, но при этом похожий (связанный с n, например, 2n) размер.
Как избегать: быть внимательнее к этому вопросу, также использовать for (auto u : v), если не нужно знать индекс элемента.

Не однозначный компаратор у set'а
Когда пишешь свой компаратор для set'a, нужно всегда помнить простое правило: если a < b и b < c, также должно выполняться a < c и !(b < a) и !(c < a) и !(c < b). Более понятным языком: всё должно быть однозначно, и если a < b, то поменяв местами должно выполняться !(b < a), а также не должно выполняться и то, и другой одновременно.
Как избегать: больше продумывать, как должен работать компаратор в set'e.

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

Мой профиль

Областная интернет-олимпиада
1. На задаче E допустил глупую ошибку (при перемещении правого указателя не удалял его значения в сете) - дебагал пол часа. Несколько раз перечитал код, ошибки не нашёл (вероятно из-за того, что он был слишком красивым - отсутствие его куска не бросалось в глаза). Стал считать идею неверной. Логически пришёл к выводу, что раз код не работает - наш мир сломался и логика перестала работать. Написал брутфорс. Нашёл тест на котором не работает, понял в чём ошибка, сдал задачу.
2. В задаче G в дихотомии проверял левую границу, а не медиану - час искал ошибку.
3. В задаче H отмёл корневую декомпозицию, т. к. она слишком медленна, стал думать про ДО. Понял, что нужно поддерживать множество в каждой вершине, дихать (или спускаться) по нему, отрезать префикс и быстро конкантенировать левое множество с суффиксом правого, в связи с чем сделал логичный вывод - это персистентное декартово дерево в ДО. Писал где-то 1.5 часа, потому что решение сложное и никогда раньше такого не делал, не успел додебагать - закончился контест. Когда додебагал получил WA5. Потом узнал, что операции с множествами можно было заменить спуском по правой половине поддерева - это было не очевидно, такого раньше не встречал, не додумался. Впредь буду знать о таком алгоритме.
Вывод:
1. Искать ошибку в дихотомии в проверки левой границы, а не медианы
2. Думать о спуске по дереву, вместо персистентной декартки