Форум 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. Недостаточный отдых
Давно у меня такого не было
Наверное, стоило больше выходить отдыхать/кушать

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

Мой профиль

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

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

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