Форум DL

Мой профиль

https://codeforces.com/problemset/problem/2028/F - 2700, дп, битсет - придумал сам
https://codeforces.com/problemset/problem/2113/E - 2800, поиск в ширину - читал разбор
https://codeforces.com/problemset/problem/2048/G - 2800, математика, комбинаторика - читал разбор (пока не понял)
https://codeforces.com/problemset/problem/1967/D - 2800, дихотомия, жадный - читал разбор

Почему не придумал вторую задачу: не знаю, видимо мало работал с потенциалами (не доказал/заметил, что каждая вершина будет входить в множество кандидатов не более n*(m + 1) раз).
Почему не придумал третью: она было сложной. Я до сих пор не понял разбор с их дивной формулой на пол экрана.
Что не так с последней задачей: подумал, что можно эффективно реализовать через ДО, но не учёл асимптотику дихотомии - O(n*log(n)^3) не пройдёт

Вывод: стоит порешать комбинаторику и задачи с потенциалами или подобные

Мой профиль

https://codeforces.com/problemset/problem/1854/C - 2500, комбинаторика, теория вероятностей - не придумал
https://codeforces.com/problemset/problem/2056/F1 - 2700, комбинаторика, математика - не придумал
https://codeforces.com/problemset/problem/2025/F - 2700, конструктив, графы - придумал сам
https://codeforces.com/problemset/problem/1976/F - 2800, жадный, ДО - вероятно придумал

Нужно решать больше теории вероятностей и комбинаторики - с ними плохо

Мой профиль

https://codeforces.com/problemset/problem/2042/F - 2600, ДО - придумал сам
https://codeforces.com/problemset/problem/1574/F - 2700, ДП - не придумал
https://codeforces.com/problemset/problem/1606/F - 2800, жадный, ДО, дп - не придумал
https://codeforces.com/contest/1654/problem/F - 2800, суф. массив - не придумал (подумал, что не получится сортировать следующий слой суф. массива относительно старого, потому что нельзя прибавить число к последовательности XOR-ов (оказалось, что можно, ведь прибавляемое число - это степень двойки, которую не содержат вторые слагаемые XOR-ов))

Мой профиль

День 1:
Первые полтора часа читал задачи, выбирал полегче и думал над почти полными решениями. Потом вспомнил, что есть очень лёгкие подгруппы и пошёл уже сдавать их.
Сначала решил писать C, потому что она была наиболее интересно, и, как мне кажется, лёгкой. Если бы я доказал одну мелочь, то смог бы получить 86 баллов спокойно (тогда была бы ещё и бронза), но почему-то мне дали только 12 баллов, остальные подгруппы не проходили по WA - переключился на A. Взял максимум лёгких баллов - 39 и пошёл решать B. Это была реально трудная задача, я понял, что фул придумать не смогу, поэтому также взял частички - 35 баллов. За последние пол часа придумал интересный метод в A, но не придал ему особого значения (я, вероятно, не успел бы его закодить), взял 3 балла на второй подзадаче B и исправил баг в C, получив уже 30 баллов.
Разбалловка:
A - 39
B1 - 35 (первая подзадача B)
B2 - 3 (вторая подзадача B)
C - 30
Сумма: 107.
День 2:
Началось всё хорошо. Придумал частичку на D, пошёл писать. За, примерно, час получил 24 балла (а рассчитывал на 39 - была ошибка из-за отсутствия long-ов в одном месте), пошёл решать F. Тоже не придумал ничего полного, не нашёл закономернности, взял 37 баллов на втором часу. Вернулся на D, нашёл баг, получил свои 39 баллов. Сел решать E. Взял базовые 30 баллов, под конец придумал на 79, но не успел написать. Опять-таки, если бы взял, была бы бронза.
Разбалловка:
D - 39
E - 30
F - 37
Сумма за день: 106
Сумма за 2 дня: 213.
Что можно было улучшить:
1. Более систематично рассуждать над C. Если бы я доказал кое-что, не думал бы над тем, как это улучшить, как возиться с центройдами и т. д. Не было бы потрачено много времени впустую.
Как этого добиться: не знаю, делать более смелые предположения, наверное.
2. Много времени потратил на кодинг B1, нужно стараться быстрее реализовывать.
3. Много времени потратил на думание в начале первого дня, вместо того, чтобы поскорее писать частички и замечать что-то по ходу решения.
4. Также в D была проблема с лонгами (и даже не в переменных, которые объявлял я, а в работе с аргументами функции, которые обязаны быть int по определению). Почему? Потому что олимпиада вынуждает отказаться от define int long (long в данном случае 64-битный), потому что мы работаем с функцией, которую вызывает грейдер. Если поставить define в верху файла, будет ошибка компиляции, что нужная функция не найдена, т. к. int в её определении заменился на long. Можно было бы поставить define внутрь функции, но я об этом не подумал, плюс, что делать с глобальными переменными или другими функциями, с которыми мы взаимодейстуем? Кстати, сейчас вспомнил о #undef - тут он, наверное, помог бы. Если кто-то знает хорошее решение этого вопроса, буду рад услышать.
5. Решения на A и C оказались проще, чем я думал, поэтому не стоит слишком усложнять - нужно думать не сильно сложно

P. S. Дорешав только A, B и реализовав мою идею на E получил уже 393 балла - это середина серебра. Можно гораздо лучше

Мой профиль

Почитал твой отчёт о решении IOI 2025.
Понравилось.

Чего не хватает:

Надо написать конкретную тактику решения задач на олимпиаде.
Потом обсудим.
Зафиксируешь тактику (если нужно, предварительно поправишь).

И потом по этой тактике порешать IOI 2024.
Потом снова отчёт и при необходимости коррекция тактики.

Мой профиль

Почему я не написал стратегию? Во второй день я изменил тактику, стал меньше думать над полными решениями, но результат получился не лучше. Расскажу, как я решал (как её улучшить я не знаю):

1. Читать задачи по порядку
2. Если какая-то заинтересовала, посидеть, подумать над ней 20-35 минут
3. Если что-то придумал, пойти писать, иначе переходить к другим задачам
4. Переходить между задачами в поисках идей на подзадачи, тратя по 10 мин. на неинтересные (которые кажутся не прибыльными, тупиковыми, сложными) и 20 мин. на интересные.

номерЗадачи = 0
while (меня что-то не привлекло или не прочитал все задачи)
    if (задача[номерЗадачи] меня заинтересовала) {
        думаю над ней 20-35 минут
        if (по ходу раздумий она не перестала быть мне интересна)
            кодирую задача[номерЗадачи] //Тогда обычно получаю около 40 и более баллов
    }
    else
        номерЗадачи = (номерЗадачи + 1) % 3
while (время не закончилось) {
    if (на задача[номерЗадачи] появилась неплохая идея)
        трачу 20 минут на развитие этой идеи
    else
        думаю 10 минут над ней
    if (придумал подгруппу на задача[номерЗадачи])
        кодирую то, что придумал
    номерЗадачи = (номерЗадачи + 1) % 3
}

/*
Прочитать первую задачу. Если она меня зацепила (стала интересной, увидел потенциал), 20 мин. трачу на раздумья над ней (не полное решение, хотя-бы большую часть подгрупп или замечание какого-то упрощения) и придумываю неплохой решение, близкое к фулу (но на этих олимпиадах додумать его не успевал и получал 30 баллов), иначе читаю следующую задачу. Если меня ничего не привлекло, беру неполные баллы по каждой задаче по порядку там, где могу. Так делаю до конца олимпиады. По ходу меня должно что-то привлечь, если этого не произошло - хорошо, дальше переключаюсь между задачами, придумывая подгруппы (примерно раз в 10 мин.). Таким образом я не зацикливаясь на одной задаче и беру баллы по каждой из них.
*/

По результатам этих контестов это неплохая тактика - я не рассеиваю внимание и придумываю неплохое решение на задачи. Да, результат получался не очень, но, я думаю, проблема в опыте. Я не знаю, как улучшить тактику и что в ней плохого, пока не встретил какую-то проблему. Единственное, что было не так - слишком долго думал, долго писал и делал баги. Чтобы избавиться от первой проблемы стоит ставить таймер или засекать время, чтобы долго не писать, нужно чуть больше продумывать реализацию - это не задачи на стандартные алгоритмы, где кодируется то, что делал уже много раз - тут нужна большая внимательность. Тогда и не будет багов. А если будут, сразу проверять переполнение чисел, либо придумать, протестировать методы для использования лонгов по умолчанию.

Мой профиль

Хорошо.
А теперь надо всё это формализовать.

1.
2.
3.
...

Мой профиль

Тактика:

1. Читать задачи по порядку
2. Если какая-то заинтересовала, посидеть, подумать над ней 20-35 минут
3. Если что-то придумал, пойти писать, иначе переходить к другим задачам
4. Переходить между задачами в поисках идей на подзадачи, тратя по 10 мин. на неинтересные (которые кажутся не прибыльными, тупиковыми, сложными) и 20 мин. на интересные.

Советы:

1. Ставить таймер, чтобы не тратить на задачу больше времени, чем нужно
2. Сильно продумывать решение перед кодированием
3. Стараться засунуть 64-битные числа куда только можно
4. Быть объективнее при придумывании задач: выдвигать смелые предположения и пытаться подстроить задачу/решение под них
5. Не слишком усложнять. Одна-две задачи будут не слишком сложными, а на 70 баллов можно сдать вообще все задачи

Мой профиль

Да теперь хорошо.
Когда прорешаешь по этой тактике IOI 2024, снова отпишись
- как решал – поподробнее
- возникшие предложения/советы/изменения в тактику
- обновлённая тактика

Мой профиль

https://codeforces.com/contest/2150/problem/F - ~3200, графы, конструктив. Читал разбор.
https://codeforces.com/contest/1111/problem/E - 2500, ДП на дереве, переподвешивание. Придумал сам.
https://codeforces.com/contest/889/problem/E - 3000, ДП. Читал разбор.
https://codeforces.com/contest/1205/problem/D - 2700, графы, конструктив. Читал разбор.
https://codeforces.com/contest/2150/problem/E1 - ~2400, интерактив, конструктив. Придумал сам.

Мой профиль

https://codeforces.com/contest/2169/problem/E - 2400, ДП. Придумал сам.
https://codeforces.com/contest/2182/problem/G - ~2700, ДП + small-to-large. Придумал сам.
https://codeforces.com/contest/2190/problem/D - ~2400, деревья + комбинаторика. Придумал сам.

Мой профиль

https://codeforces.com/problemset/problem/2210/E - 2700, конструктив, интерактив - не придумал за час.

Сделал очевидные преобразования, свёл задачу к запросам gcd кол-ва нулей и кол-ва единиц на отрезке, но как при помощи него найти их расположение не придумал.
Оказалось, что можно постепенно строить префикс, делать запрос на нём максимальной чётной длины и смотреть будет ли gcd чётным. Если gcd чётный то кол-во единиц на отрезке чётное и мы ставим 0 или 1, чтобы на этом отрезке это выполнялось.
Однако, это не проходит по кол-ву запросов. Чтобы соптимизировать это, нужно отказаться от 1 запроса к префиксу и заменить его двумя (на префиксе i и i - 2), чтобы находить чётность единиц на отрезке i - 1..i. Это ничего не даёт, если мы будем делать запросы только к префиксу, но теперь для i < n / 2 можно делать запросы к суффиксу, что сильно оптимизирует суммарную стоимость операций, потому что сумма второй половины гармонического ряда (1 / k + 1 / (k + 1) + ... + 1 / 2k = ln(2)).

Нужно было подумать, что через gcd находится какая-то простая информация (чётность) и строка строится по порядку (на префиксе), но я пытался искать какие-то красивые алгоритмы, дающие много информации, а уже потом объединять эту информацию в одно целое.

Мой профиль

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

https://codeforces.com/problemset/problem/2210/E - 2700, конструктив, интерактив - не придумал за час.

Нужно было подумать, что через gcd находится какая-то простая информация (чётность) и строка строится по порядку (на префиксе), но я пытался искать какие-то красивые алгоритмы, дающие много информации, а уже потом объединять эту информацию в одно целое.

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

Мой профиль

Сначала контеста я прочитал все задачи и мысленно обозначил темы на каждую задачу и в задаче D как мне показалась самая приятная тема и я стал думать над ней я пытался переключаться на J но не смог увидеть закономерность

Мой профиль

Сначала я прочитал все задачи и мне показалось что в задаче J надо было понять как можно делать рекурсивный спуск. Я придумал это почти сразу но застрял на том что моя идея спуска работает за O(n*n). Через час я придумал что можно написать декартовое дерево но решил что это слишком сложно + я его не разу не писал. И спустя ещё час придумал что вместо декартового дерева можно написать фенвик. Ну и сдал на 100 баллов.

Дальше я пошел решать задачу K но спустя полтора часа придумал , что это можно решить алгоритмом Мо с откатами что я пару раз видел но не разу не писал + решение работает за O(n*sqrt(n)*log n) что для 2 секунд слишком много и решил временно бросить задачу.

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