Форум DL

Мой профиль

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

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

По-моему, ключевой вопрос

Как писать, не делая ошибки?

И дополнительный важный вопрос

Как системно и быстро искать ошибки?

Надо попробовать найти ответы на эти вопросы.

Начиная с
"НЕ переутомляться перед контестом" - вчера как раз именно так и было
"высыпаться перед контестом"- было сегодня или нет?

Мой профиль

Перед контестом я выспался.
По поводу ошибок:
Ошибки кодинга я разделяю 2 типа:
   0. Забывание что-то написать при реализации (например, обнуление переменной при проталкивании значений в ДО, отсутствие обновления структуры при телепортировании указателя на несколько позиций)
   1. Неправильная реализация - обычно глупая ошибка, связанная с написанием чего-то на автомате, не задумываясь (например, как было с неправильной переменной в дихотомии, циклом размера n по вектору длины меньше n).
 
Эти ошибки не делать невозможно (многие виды др. ошибок возможно искоренить на корню дисциплиной или хорошей техникой мышления/кодирования, но ошибки реализации возникают из-за сосредотачивания на чём-то другой, упуская внимание с деталей, да, можно сильно сократить их кол-во, если кодировать очень медленно и вдумчиво, но это тратит слишком много сил и времени на олимпиаде - с такой тактикой можно еле решить 1 задачу за 5 часов) - мы люди, мы ошибаемся - нужно думать, как находить их мгновенно, просто мельком просмотрев код, перед отправкой, во время тестирования, или после получения вердикта тест-системы.

Как находить их:
   1. Выписывать ошибки, перечитывать эти чек-листы перед соревнованием и стараться проходиться по ним, проверяя код.
   0. Тут уже сложнее - чтобы выявить этот тип нужно потратить приличное кол-во сил на раздумья. Как это делать максимально эффективно:
      0.0. Перечитать условия, убедиться, что правильно его понял
      0.1. Убедиться в правильности своей идеи, доказать её ещё раз, разобрать случаи
      0.2. Если всё из этого правильно, значит проблема в реализации, логика не сломалась, мир не разрушается - как бы код красиво и закончено не выглядел, мы что-то в нём забыли реализовать
      0.3. Выписываем идею кода построчно или схемой, или как-нибудь ещё, каждую секунду спрашивая себя: "все ли подробности я описал", "ничего ли я не забыл", "как лучше это реализовать" и т. д. В общем становимся максимально придирчивыми, при этом не смотря в код - работаем только с идеей, с тем, что мы хотим получить, абстрактной реализацией, которую придумали, не копируя ошибки кода - получаем, этакий, псевдо-код, который максимально схож с идеей, при этом похож на код
      0.4. Максимально придирчиво соотнести код с псевдо-кодом, стараясь понять, какое уточнение реализации я упустил

Мой профиль

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

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

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

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

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

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

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

Объедини все ошибки в одно сообщение и ПОПОЛНЯЙ после каждого командного и личного контеста, включая CF-раунды.

Мой профиль

Долги 4:
Важное (?):

Командные:
   ФПМИ 3:
      C
Дорешать:
   2 день IOI 2025
   Открытую олимпиаду школьников 2025
   Последние 2-3 CF-раунда
   Последние 2 воскресные олимпиады
   D2 с области
   A с командной олимпиады: дана матрица 2000*2000 из 0 и 1, найти площадь макс. прямоугольника, содержащего не более 1 единицы
   Повторить LCP, FFT, тест Миллера-Рабина
   Ощущаю проблемы с комбинаторикой и сложными ДП, нужно решать их

Порешать:
   Сборы RuCode
   IOI прошлых лет
   Тем-туры (и посмотреть по ним лекции) Т-поколения

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

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

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

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

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

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

Мой профиль

Школьная олимпиада
Решил первые 6 задач (A-F) за 13 минут.
Сразу придумал G, написал - получил то ли 0, то ли 15 баллов.
Понял, что неправильно обработал старт с 0-ой вершины - 15 баллов.
Решил почитать следующие задачи.
H показалась сложной, либо в плане решения, либо в плане доказательства
(полагаю, там просто жадник, пока не думал работает ли он),
поэтому переключился на I. Прочитал, тоже придумал сразу.
Написал - 0 баллов. Сначала понял, что неправильно обрабатываю макс= на пути, исправил - 0 баллов.
Потом перечитал условие, понял, что граф не обязательно связанный. Исправил, сдал.
Пересел на G. Так и не понял, что не так.
За 15 минут до конца решил взять баллов на H - через 2 минуты было 15.
В спешке забыл, что нужно выбрать ровно k чисел, а не любое кол-во,
стал писать dp, но оно не заработало. Олимпиада кончилась.

В чём ошибки:
Криво обработал старт dp в G.
Криво написал макс= на пути в H.
Сразу не понял, что граф не обязательно связанный.
Потратил много времени на G, возможно, стоило решать H

Мой профиль

25_Rui1 и 25_Rui2

В первый день 3-ю по кол-ву задачу я дописал спустя 2:50,
однако, перепутал переменные q и n в цикле,
не очищал массивы между тестами и экспериментировал с хешами.
В общем, сдал только в 3:40. Можно было сдать быстрее,
но думать было тяжело и печатал я на клавиатуре ноутбука,
где моя скорость ниже, чем на проводной.
Быстро придумал B, но из-за трудностей в случаях
и ограничении на кол-во запросов долго её писал,
а потом ещё и дебагал. В общем не успел.

Во второй день я решил B только спустя час
(хотя, это самая трудная задача контеста,
её решало большинство, при том на 90 баллов,
поэтому я решил также работать с ней).
Прочитав задачу C, я придумал разделение
запросов на те, что больше и меньше sqrt(10^6)
и пытался решить этой идеей до конца олимпиады,
однако, нужно было всего лишь разделить
запросы на >=3, =2 и =1 и той же
методой решить гораздо быстрее.
Об этом я догадался только после конца олимпиады.
D была в принципе лёгкой задачей без структур
и особых алгоритмов - просто несколько двусвязных списков.
Над ней нужно было только немного подумать.

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

P. S. Уточнение моей ошибки а задаче C, которую можно было решать сильно проще и быстрее:
Отметание лёгких случаев:
Нужно было посчитать кол-во вхождений каждой в вертикальные пути дерева. Я отдельно рассмотрел строки длины >sqrt и <sqrt.
Строки >sqrt обрабатывал хешами, проходясь в лоб по всем позициям, где они могли закончится (по вершинам, цвета последней
буквы строки запроса. Т. к. цвета распределены равновероятно, их около n / 26). Однако, это работало слишком медленно и я
пытался городить чёрти-что с unordered_map для остальных строк, чтобы ускорить их. Однако, решение проблемы гораздо проще:
вместо прохода по n/26 вершинам, у которых цвет совпадает с последней буквой строки нужно проходиться по n / 26 / 26 вершинам,
у которых с предком и концом строки совпадают 2 буквы. Тогда мы можем уменьшить длину строк, которые мы обрабатываем
другим методом, тем самым ускорив всё решение

Мой профиль

https://dl.gsu.by/TableViewer.asp?nid=2575413&fn=solutions_2452934_7dX5Z_1739854665725.htm

Мой профиль

Долги 5:
Важное (?):

Командные:
   ФПМИ 3:
      C
Дорешать:
   2 день IOI 2025
   Открытую олимпиаду школьников 2025
   Последние 2-3 CF-раунда
   Последние 2 воскресные олимпиады
   Повторить LCP, FFT, тест Миллера-Рабина
   Ощущаю проблемы с комбинаторикой и сложными ДП, нужно решать их

Порешать:
   Сборы RuCode
   IOI прошлых лет
   Тем-туры (и посмотреть по ним лекции) Т-поколения

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

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

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

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

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

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

Мой профиль

Решал я как-то IOI 2019, day 1...

Пишу потому, что в 2 не решённых задачах правильные идеи мелькали у меня в голове, но я всё равно из не решил.
Почему так произошло?
Основная проблема - меня заклинило на частичках.
У меня неплохо получается их брать и я стараюсь выжать из них максимум. Например, в B я пихал рандомный перебор.
У меня мелькала идея о центройде, но я надеялся добиться ?60 баллов, не вышло.
В C я пытался писать O(n?m * log(m)) (и то оно слетало по WA),
хотя было предположение, что всего возможных подходящих вариантов в строке - O(n).
Эта идея пришла ко мне, когда я работал с преф./суф. максимумами (их всего n штук),
но потом я решил, что с одной стороны может быть 1 преф. макс.,
с другой суф. макс. и кол-во возможных комбинаций будет n?.

Основная проблема во времени, и даже, скорее, в том, что я мямля, которая не может посидеть 30 минут и придумать задачу
- через 10 мин. я уже бегу за неполными баллами.
Над центройдом в B я особо не думал, хотя это основной ключ задачи и подиумов о нём,
я бы спокойно её решил, но я остался "в домике"...

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

Надо изменить что-то в тактике

Мой профиль

Ну например так - мои соображения "для затравки"

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

Потом реализации

От "пропихиваний", мне кажется, нужно вообще отказаться.

Ты конечно напишешь свой вариант.

Мой профиль

mr. Chest:

Основная проблема во времени, и даже, скорее, в том, что я мямля, которая не может посидеть 30 минут и придумать задачу
- через 10 мин. я уже бегу за неполными баллами.

Я тут свои 5 копеек хочу вставить. Ты не мямля, это нормальный подход брать частичные баллы чуть ли не сразу(лучше, чем до конца с нулем баллов пытаться придумать решение на полный балл). Но:

1) Может стоит еще помимо брутов/(несвязных с фуллом групп) проанализировать группы(или наборы групп) на количество потенциального затраченного времени на придумывание(возможно уже придумал, как прочитал группу) + реализацию

2) Применить пункт 1) ко всем задачам с самого начала

3) В зависимости от таких "первых взглядов" на задачи принимать решение о реализации конкретных групп

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

Мой профиль

Да, безусловно я пытаюсь рассчитывать время на придумывание и реализацию подгрупп,
но я начинаю решать их слишком рано - после их решения у меня не остаётся времени на поиск полного.
Я метаюсь между двумя вариантами:
сидеть и думать над фулом (что не обязательно увенчается успехом) и брать неполные баллы.
Сейчас уже тот период, когда я способен решить почти любую задачу, но не обязательно решу её.
Бывает, что на решение уходит 4 часа (или я чего-то не замечу, устану, зациклюсь и др.),
но я не хочу сидеть как Кирилл и все 4 часа решать одну задачу.
Я ищу способ понимать: смогу ли я её решить и стоит ли мне сидеть,
либо брать неполные баллы по максимуму (с тем, до какой поры стоит пытаться брать
неполные баллы определиться легче - просто переключаюсь между
задачами и пытаюсь улучшить решение в каждой из них, тратя время
пропорциональное тем баллам, на сколько я могу их увеличить (е
сли у 2 задач есть подгруппы на 10 и 20 баллов соответственно,
то я сижу над второй в 2 раза больше, если, конечно, получается)).
Мне понравилась идея Михаила Семёновича - отводить на задачу 30-40 минут для поиска полного решения,
вообще не думая над подгруппами. Это позволит не распыляться и хорошо продумывать идеи.
Конечно, не факт, что это хорошо работает, поэтому я приветствую все предложения,
но просто "принимать решение о реализации конкретных групп" - это слишком размыто
и не решает проблему что делать: фул или подгруппы при том, что и то, и другое успеть невозможно.

Мой профиль

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

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

Если за 40 минут ты не придумал фулл - надо писать подгруппы.
Ничего тут не размыто - всё предельно ясно.
40 минут - условное время, можешь изменить его на 30 или на 60 минут.
Важно, чтобы тебе хватило времени написать то, что придумал.

А вообще критерий истины - практика.
Для этого мы каждое воскресенье и решаем олимпиады - причем теперь именно IOI.
Фиксируй тактику - следуй ей на олимпиаде - после олимпиады рефлексируй и, если нужно, корректируй тактику.
Так методом последовательных приближений должно получится то, что ТЕБЕ нужно.

Я бы ещё подумал и в таком направлении.
Отбирать полгруппы, которые приближают к полным идеям.
А подгруппы - частные случаи - делать только в когда ничего другого не можешь придумать.

Мой профиль

Долги 6:
Важное (?):

Командные:
   ФПМИ 3:
      C
Дорешать:
   2 день IOI 2025
   Открытую олимпиаду школьников 2025
   Последние 2-3 CF-раунда
   Последние 2 воскресные олимпиады
   Повторить LCP, FFT, тест Миллера-Рабина
   Ощущаю проблемы с комбинаторикой и сложными ДП, нужно решать их
   C с 25_COCI3_Dec - после восстановления пар, можно восстановить (или перебрать пару) направлений

Порешать:
   Сборы RuCode
   IOI прошлых лет
   Тем-туры (и посмотреть по ним лекции) Т-поколения

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

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

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

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

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

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

Мой профиль

25_COCI3_Dec

За 20 мин я решил A, B и стал думать над C.
Спустя пол часа прочитал D и вернулся к C.
Ещё через пол часа прочитал E, сдал за 10 мин.
Решил, что C - гроб и оставшиеся 3 часа уделил D.
Спустя полтора часа раздумий решил написать O(n^3). Получил свои 61 балл и стал думать дальше.
Я забыл, что ограничение на высоту дерева 36 и поэтому не предавал старому решению большого значения. Да и, как я выяснил, его допихать, вероятно, нельзя.
Спустя время я таки решился воплотить первую идею - FFT с КТО за O(n^2 * log(n)). Это было глупо, я знал, но ничего другого я придумать не мог.
Оно не прошло из-за чего-то и по TL в самом конце олимпиады, ничего сделать я не смог и не мог бы.

Ошибки:
Стал писать FFT - нужно было дальше думать над задачей и условием
Не придумал, что в C можно ориентировать граф.