Форум DL

Мой профиль

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

25_COCI3_Dec

Решил, что C - гроб

Это было правильное решение? Миша же взял 54 балла

Я забыл, что ограничение на высоту дерева 36

Я не понял - если бы не забыл, что это могло изменить?

Не придумал, что в C можно ориентировать граф.

Надо вписать куда-то в тактику - это важный приём при решении задач с помощью ДП на графах.

Мой профиль

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

Решил, что C - гроб

Это было правильное решение? Миша же взял 54 балла

Да. Я достаточно долго над ней думал, чтобы переключиться на остальные задачи.

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

Я забыл, что ограничение на высоту дерева 36

Я не понял - если бы не забыл, что это могло изменить?

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

Мой профиль

Всерос 2025. День 1.
A, B сдал за час. Прочитал C - она оказалась очень интересной. Я впервые реализовал дихотомия внутри другой дихотомии, и ещё внутри lower_bound и оно даже работало сразу, но было очень долгим (получил 35 баллов на DL и 63 на codeforces). Я грешил на int128, но он не виноват. Нужно было разделить решение на 2 половины, дихнуть в каждой по отдельности и сложить минимумы. Я до этого не додумался и сидел, оптимизирован это решение, чтобы на DL тоже получить 63 балла. Мне это удалось, но только в конце олимпиады. На D времени вообще не хватило

Что исправить:
Дольше думать над стрёмными дихами и меньше их пихать, а решать нормально.

Мой профиль

Всерос 2025. Дань 2.

Решил А за 20 минут.
Прочитал B, долго над ней думал.
Понял, что можно находить только 7 рёбер от каждой вершины.
Решил написать квадрат для проверки этой теории.
На 2-ом часу отправил - он не прошёл.
Только на 4-ом понял, почему не работало, исправил.
за пол часа до конца переключился на другие задачи, взял на C 43 балла.

Я не считаю неверным решением продолжение решения B. Если бы я не понял в чём ошибка и не получил бы 88 баллов, наверное, нигде бы столько же добраться не мог (D я вообще не очень понимал и не хотел решать - она казалась гробом, хуже, чем B).

Основная проблема в том, как долго я решал и насколько качественно. Я слишком медленный. Если бы я был в 4 раза быстрее, я бы, возможно, закрыл бы B, взял 90 на C и ещё 50 на D. Нужно каким-то образом ускоряться, пока не знаю как, но сегодня я держал всё под контролем... Кроме B...

Мой профиль

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

Понял, что можно находить только 7 рёбер от каждой вершины.
Решил написать квадрат для проверки этой теории.
На 2-ом часу отправил - он не прошёл.
Только на 4-ом понял, почему не работало, исправил.

Что понял?
Почему не понял раньше?
Что нужно было делать, чтобы понять раньше?
Что нужно было сделать, чтобы не было этой ошибки и огромной траты времени?

Мой профиль

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

Что понял?
Почему не понял раньше?
Что нужно было делать, чтобы понять раньше?
Что нужно было сделать, чтобы не было этой ошибки и огромной траты времени?

0. Когда я проходился по компоненте плохих вершин и заходил в хорошую, я помечал её как посещённую, но в хорошей вершине есть не все рёбра, поэтому в какой-то другой компоненте я в будущем не мог зайти в эту хорошую вершину и не зашёл в эту компоненту, когда стоял в той хорошей вершине.
1. Я проходил сквозь хорошую вершину, находя только суффиксные OR-был ли я в хорошей вершине. Т. е. после запуска в компоненте, хорошими считались только вершины, лежащие на пути от стартовой до хорошей. А также вершины других компонент, в которые я заходил, проходя сквозь хорошую вершину также считались "без пути к хорошей вершине".

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

Мой профиль

Надо вписать куда положено.
1. Ошибки
2. Поправки в тактику

Мой профиль

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

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

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

Среднее (~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 2018

day 1
Первый день я начал не очень. Долго решал А: думал над какими-то цепями Маркова и вероятностью того, что переходов, восстанавливающий 2 буквы окажется больше, чем восстанавливающий 0, однако, потом, когда доделывал эту идеи, заметил оптимизацию последнего случая, применил его к первому и понял как решать задачу с гарантированным нахождением строки без лишних случаев.
Затем я взял 15 баллов на C. Долго думал как решать циклы в 3 подгруппе и решил, что лучше уж я напишу B (хотя циклов там не было, написано, что города соединены в цепочку, я подумал, что там может быть одна цепочка, а все остальные циклы).
Затем я реализовал ДО на 31 балл на B, но оно зашло только на 5 по времени. Видимо, надо было писать ДО снизу или хотя-бы не на структурах.
B оказалась легче, чем C я вполне мог её придумать, но я решил сосредоточить силы на C. Плюс, я много времени потратил на A, поэтому не успел.

day 2
Сразу придумал решение A на 63 балла. Однако, я сильно его упростил. Добавлял переходы в корень дерева только в начало, хотя от их позиции ничего не зависело. Они разбредались по дереву и я не мог вырезать целое поддерево, чтобы их убрать. Почему-то я думал слишком локально, не пытаясь изменить концепцию расстановки этих переходов.
Написал ДО на C на 36 баллов, но из-за ошибки в пересчёте нужна подгруппа не заходила. Около 1.5 часов я дебагал, написал стрессы, нашёл тест, ошибку, исправил, сдал.
B я придумать не смог. Я пропустил подгруппу, где S = 0 (конец одного из путей лежит в корне дерева) и думал, что я смогу решить для дерева сразу. Однако, если решать для обобщённого случая, у меня выходило 69 операций. Я не догадался находить одно из рёбер, просто дихнув его, и решать задачу уже для 2 поддеревьев, пути в которых начинаются с корня. Хотя, опять-таки времени на B не хватило.

Мой профиль

Хорошо, что появилось описание , НО

Этого недостаточно, надо сделать и остальную работу

1. Зафиксировать ошибки в нужных темах форума
2. Оценить, следовал ли тактике
3. Сделать выводы – нужно ли изменять тактику?
4. Если нужно, то почему и как, и измени.

Мой профиль

IOI 2017

day 1
Первые 3 часа я сдавал B. Правильно делал, потому что там нужно было найти несколько закономерностей и вывести простую dp.
В оставшийся час я решал A, но ответ на один из открытых тестов был неправильным (это был основной тест, от решения которого зависело решение всей остальной задачи). Моя стратегия была не оптимальной, но другую придумать я не смог и не успел.

day 2
За 2:40 я сдал A.
Затем написал C, но она не брала 50 баллов, как я хотел (только 12). Из-за сортировки по левой границе отрезков, я забыл передвигать указатель на максимум из него и правой границы - я сдвигал его на правую границу последнего отрезка, которая могла быть меньше его.
За пол часа до конца переключился на B. Написал базовую идею, которая взяла 30 баллов, добить до 51 не успел.

Вывод: надо не ошибаться в max= и тогда это будет мой максимум (хотя решать я могу всё, просто не хватает времени)

Мой профиль

Из-за сортировки по левой границе отрезков, я забыл передвигать указатель на максимум из него и правой границы - я сдвигал его на правую границу последнего отрезка, которая могла быть меньше его.

1. Надо вписать куда положено новую ошибку.
2. Сколько времени писал? Сколько времени искал ошибку?
Можно ли было её обнаружить тестированием? Как?

решать я могу всё

Это здорово - нет ограничений на достижимый результат.

просто не хватает времени

Тебе лично больше времени никто не даст.
Значит надо работать над
- ускорением написания
- не совершением ошибок
- сокращением времени на локализацию ошибок.

Как?
Наверно надо отдельными разделами вписать в тактику

Как писать без ошибок
Как быстро находить ошибки

Мой профиль

Да, я выписал эту ошибку.
Писал конкретно это решение быстро (минут за 7), но до этого долго думал и тестировал другие решения.
Ошибку, увы, не искал - до конца оставалось пол часа и я решил переключиться на B (по итогу взял там 30 баллов - это было правильно).
Ошибок я стал делать меньше, по крайней мере в условиях - много записывают, рисую. Основная проблема тут в том, что я торопился и отошёл от задачи. Наверное, стоит сосредоточиться на ускорении придумыаания сложных задач. Пока не знаю, как это сделать, если задача как сегодняшняя А на придумыаания реализации, где нужно просто потратить 2 часа, сидя, разбирая алгоритмы действий, случаи и прикидывать, сколько это будет работать. У меня это получается, но медленно. Возможно, с опытом придёт, когда отрешаю кучу таких IOI-задач. Но надо их все дорешивать - без этого толку будет мало

Мой профиль

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

Основная проблема тут в том, что я торопился и отошёл от задачи.

Не понял, поясни пожалуйста.

Мой профиль

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

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

Основная проблема тут в том, что я торопился и отошёл от задачи.

Не понял, поясни пожалуйста.

Я имел ввиду, что не сдал C, потому что переключился на B. Если бы я посидел минут 10, наверняка, нашёл бы баг, но этих минут у меня не было.