Форум DL

Мой профиль

ЗКШ День1:

Прочитал А, подумал над формулами какими-то, которые +- однозначно должны были ответ восстановить, но нет. Прочитал В. Сразу пришла идея с маскми, написал и получил WA. Сначала заметил багу, что я не чистил граф для вершины 0(там мультитесты). Все равно WA. Решил перечитать условие и заметил во входных данных важную штуку, из-за которой и падало, исправил и сдал. Вернулся на А. Придумал жадное решение и словил WA. Немного подумал, почему это может быть неправильно, но безуспешно. Переключился на С. Прочитал, написал бфс и словил WA, подумал, что надо еще два перехода добавить и получил АС. Вернулся к А. Посидел, пытался найти крайние случаи, которые не работали бы, но все работало. Подумал, а вдруг у меня неоднозначно можно поставить элемент в позицию i, а для первого элемента, который я ставлю, у меня нет ответа дальше, а для второго будет. Написал рекурсию и получил АС. Прочитал D. Задача выглядела несложно, придумал медленное ДП и варианты его оптимизаций. Сначала написал медленное ДП. Словил WA10. Подумал, что ладно, может в этом решении набагал, а в оптимизации, которое я доказал этим медленным решением, а точнее проверил для кучи рандомных тестов верность условия opt[i] <= opt[i + 1], чтобы убедиться, что можно писать разделяйку. Написал разделяйку, добавил assert и словил RE. В данном случае я уже знал, что у меня не ищет opt, когда должен найти. Взял кубическое решение, поочередно тестил со всякими ассертами, некоторые работали, но все равно я не понимал, почему падало. Вспоминаю, что у меня стоит 1<<h, а h <= 50. У меня ловило в итоге переполнение(локально я тестил на макс тестах и все работало нормально

). Поставил лонги и сдал задачу. Было время подумать над E. Думал в сторону потоков, а если точнее, то в сторону min-cost-max-flow. Никак не мог придумать то, как правильно построить сеть, чтобы запустить min-cost. В итоге решил написать жадник, так как уже ничего в голову больше не приходило. Словил -1 и на этом у меня достижения по задаче закончились

что произошло:
1) опять невнимательные баги
2) я был прав, что в задаче Е решение через min-cost-max-flow. Уже дорешал. Док-во построения сети очень интересное, чуть позже почитаю
3) авторское решение на D было через оптимизацию Кнута, которую я не знал. Там свойство схоже со свойством разделяйки, поэтому нетрудно запомнить и его

Мой профиль

ЗКШ День2:

Прелюдия:
Меньше знаешь, крепче спишь...

В начале контеста были технические проблемы, поэтому примерно 20 минут ушли впустую у всех. Прочитал А и сразу пропустил, так как не знал, в какую сторону даже думать надо. В показалось простой, написал очевидное ДП и словил WA. Поставил еще больше infinity - WA. Сделал пересчет через лонги(там ответ в частности дробный) - WA. Вернул даблы и поменял в порядок циклов - OK. До сих пор не понимаю, в чем была разница между порядком циклов. Прочитал C. Казалось не очень трудной, думал в сторону жадника, так как под оптимизацию ДПшек ниодна из моего арсенала(!) не подходила. Придумал хороший жадник, заслал и получил WA. Подумал над вариантами багов. Контртестов найти не смог, поэтому перешел на F(ее много сдавало). Тоже выглядела простым жадником. Решил проверить одно жадное решение, которое я и доказать не мог, и опровергнуть. Словил WA. Также немного подумал и решил обратно перейти на другие задачи. Прочитал D, тоже постановка задачи не казалась трудной, и интуитивно должно было быть все просто, но я не смог туда придумать ничего толкового. Решил подумать над А. Придумал красивую идею, но так отдебагать не успел до конца контеста

Выводы:
1) в задаче F я не выписал формулу соблюдения условия, редкий случай, стараюсь всегда выписывать их
2) спросил у китайца решение на С. Тот сказал, что не знает жадного решения на него, а решал через лямбда оптимизацию ДП. Раньше я этого не знал, уже задачу через этот метод дорешал. Узнал что-то новое и полезное
3) авторское решение было абсолютно схоже с моим, но я не разобрал еще один случай, из-за которого и слетало. Делать больше тестов с крайними случаями. Больше думать!!!
4) как и говорил, задача D идейно была простой, да и она очевидная. Дорешаю в ближайшее время ее. Наверное, переволновался, меньше думать о своем результате, лучше думать о том, как сдать задачу(не важно какую)

Мой профиль

Александр Лосев:

ЗКШ День1:

Написал по почте ещё до выкладывания анализа тобой. Сохраняю для истории
Я правильно понимаю, что ты ПЕРВЫЙ среди белорусов?
Супер!!!
И всё равно надо продолжать «движение вверх».

Глядя на таблицу результатов –много лишних отсылок -надо
1. Качественнее работать с условиями задач.
2. Лучше продумывать решения.
3. Писать с меньшим количеством ошибок, а лучше совсем без них.

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

Мой профиль

Александр Лосев:

ЗКШ День2:

Опять же написал по почте ещё до выкладывания анализа
Сегодня много хуже.
Может усталость?

В любом случае
- анализ–выводы и научиться теории, которую не знал.

Теперь по тексту

Прелюдия: Меньше знаешь, крепче спишь...

Это к чему - пояснишь мысль?

До сих пор не понимаю, в чем была разница между порядком циклов.

Нужно обязательно разобраться - пусть и после окончания всех контестов.

1) в задаче F я не выписал формулу соблюдения условия, редкий случай, стараюсь всегда выписывать их

Надо раз и навсегда исключить нарушения тактики

2) спросил у китайца решение на С.

Здорово, что не стесняешься спрашивать.

Тот сказал, что не знает жадного решения на него, а решал через лямбда оптимизацию ДП. Раньше я этого не знал, уже задачу через этот метод дорешал. Узнал что-то новое и полезное

Здорово

3) авторское решение было абсолютно схоже с моим, но я не разобрал еще один случай, из-за которого и слетало. Делать больше тестов с крайними случаями. Больше думать!!!

Как важно!!!

лучше думать о том, как сдать задачу(не важно какую)

Возражу. Мне кажется, надо держать под контролем весь контест, пытаться продвигаться по всем задачам и больше уделять времени тем, где кажется более вероятным получение нужного результата. Ну и да при принятии решений о выделении времени задачам учитывать текущее состояние таблицы результатов.

Мой профиль

ЗКШ День3:

Прочитал А. Идей сразу не было, поэтому перешел дальше. Вшка была очень простой. Написал и словил WA9. Изначально нашел багу в хешах(она и была реальной багой), но все равно WA9. Подумал над частным случаем, который должен был учитываться, исправил и словил AC. Переключился на А. Подумал над самым худшем случаем и старался придумать корректный алгоритм для решения задачи(там чистый конструктив), но все безуспешно. Смотрю, что потихоньку сдают C, поэтому переключился на нее. Прочитал, посмотрел ограничения и подумал над корневой декомпозицией. Быстро додумал до корректного состояния. Написал и словил WA. Поставил размер блока такой, чтобы в семпле был не один блок, а несколько, и словил WA(локально). Ошибка была в том, что я неверно индексы расставлял в двух методах. Заслал и сдал. Пошел обратно на А. Также начал дальше думать над вариантами алгоритмов. Также ничего не подходило, пошел думать над D. Подумал над интерпретацией задачи в модификацию нахождения НВП. Написал и словил WA2. Подумал, перечитал условие. А я же не выписал все формулы, которые были в условии. Выписал и получилось, что некоторые вещи посокращались и придумал ДП за O(n^2 * log2(n)), которое являлось оптимизацией лобового ДП за O(n^3). Написал и сдал задачу.

Что произошло:
1) оказывается, что в А надо было рассмотреть циклические цепочки и с ними пошаманить. Я опирался вообще не на эти факты
2) C можно было через ДО решать, но ,как по мне, через корнячку легче
3) Вовремя одумался в D, что надо выписать формулы условия. Круто!

Завтра выходной(контестов нет, лекций нет), поэтому я попросил китайца скинуть пару задачек на лямбду, чтобы потренироваться. Возможно, еще дорешаю задачу I(вроде Ad Hoc с элементами реализации)

Мой профиль

Задачу E (ты называешь её A) сдало 23 человека.
Ты в таблице 10-й и не сдал её.

Надо исключать такую ситуацию!!!
Расширять направления поиска, заходить с другой стороны и проч.
Подумай сам, что добавить в тактику, чтобы придумывать решения таких задач.
23 человека придумали, значит и ты тоже точно мог придумать.

Мой профиль

ЗКШ День 4:

Прочитал Е. Сначала испугался, но потом легче стало, когда получил ответ на первый семпл. Там просили площадь необычной гиперфигуры внутри гиперпараллелепипеда с ограничениями. Сначала выписал формулу всех координат точек новой фигуры. Дальше думал над формулой площади какой-то странной фигуры, которую я не мог представить. Сначала думал над общим случаем, потом начал разбирать то, как у меня ответ в семпле можно обобщить под общий случай. Повыписывал формулы, подставил под разные прямоугольники, все работало. Написал и словил TL. Я думал, что там ограничения чуть меньше стояли, из-за этого я и словил 2 лишние посылки. Дальше прочитал остальные задачи. Больше понравилась Н, но начал думать в F. Придумал идею, написал и словил WA. Подумал, что ошибка в погрешности, поэтому ее менял и засылал. Подумал, а там есть коварный случай, который не учел. Перешел на Н. Подумал над закономерностями, придумал основную идею, но как ее реализовать быстро я не знал. Так и до конца контеста не смог придумать быстрое решение.

Что произошло:
1) невнимательно прочитал условие
2) в задаче F можно было побольше подумать и сдать, там я был близок к решению
3) аналогично с Н

Мой профиль

Хорошо
1. Ты лучший среди белорусов
2. Ты ТРЕТЬИМ среди всех сдал первую задачу
3. Ты решил сложную нетрадиционную задачу

Плохо
1. По-моему, ты решал задачи БЕЗ ОГЛЯДКИ НА МОНИТОР
--- задачу F, над которой ты мучался, сдали всего 2 человека
--- задачу H сдали 6 человек
2. "Больше понравилась Н, но начал думать в F." - Почему?
--- возможно была ошибка в выборе задачи
3. Ограничения можно и перед отсылкой посмотреть, а не после

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

Мой профиль

ЗКШ День5:

Прочитал Е. Подумал над наивным решением. Решил посмотреть, как далеко оно пройдет и с разными константами. Ничего не получилось, перешел дальше. Прочитал F. Сразу подумал о какой-то страшной интерпретации условия и пропустил. Прочитал оставшиеся задачи. Остановился на J. Там задача основывалась на абсолютно рандомных тестах и частным случаем NP-полной задачи. Придумал что-то +-адекватное. Получил ВА и вернулся на F. Придумал хеши с двумерным ДФ. Написал и словил сначала WA. Кучу мелких багов наловил, а после них еще и ML. Придумал оффлайн решение и сдал задачу. Вернулся на Е. Зашел на емакс(правилами не было запрещено), нашел штуку с дискретным логарифмированием. Взял код и разбил задачу на два случая. Начал ловить TL очень далеко. До конца контеста подбирал разные константы.

Что произошло:
1) перенервничал на F, невнимательно писал код
2) на Е идея правильная, не хватило 5 минут допихать ее(в дорешке допихал)

ЗКШ День6:

Прочитал Е. Придумал жадник, словил ва2. Рассмотрел задачу в виде графа. Надо было найти максимальное независимое множество в графе, что являлось NP-полной задачей, НО граф был особенной конструкции, поэтому решил написать. Словил WA22, что означало хороший результат. Начал искать баги, но все безуспешно. Перешел на G. Начал думать над разными конструктивными алгоритмами. Написал какое-то +-толковое решение, но оно упало на стрессах. В таблице увидел, что сдали H, перешел к ней. Прочитал, написал брут и начал анализировать поведение операции из условия. Нашел закономерности, написал и словил WA. Бага была не в формуле, а в ифе, ее я нашел через стрессы(перед первой посылкой стрессы работали). Вернулся на G. Придумал еще один алгоритм, он тоже упал. Взял тот тест, на котором упало, и на нем поперебирал еще парочку алгосов. Один из них уже казался правдивым. Написал, стрессы работали. Заслал вместе с ассертами и получил АС. Вернулся на Е. Посидел, подумал, убрал один кусок кода, которым я из всех прямых оставлял только различные, и получил АС. Пошел решать F. Думал в сторону min-cost-max-flow, тк обычно такого рода задачи так и решались

Что случилось:
1) не рассмотрел изначально крайний случай с прямой x = 0, из-за чего как раз и падало
2) занял топ3, в следствие чего отбил топ3 в общей рейтинговой таблице дивизиона

Мой профиль

Александр Лосев:

ЗКШ День5:

78 посылок по задаче это «зашквар»
Лучше было 78 раз подумать, чем 78 раз послать

ЗКШ День6:
занял топ3, в следствие чего отбил топ3 в общей рейтинговой таблице дивизиона

Круто, так держать!
Только разрыв от 1-2 места очень большой.
Чего тебе не хватает по сравнению с ними?

Мой профиль

Олимпиада ЗКШ:

Прочитал задачу А. Сразу понял, что надо попариться немного с формулами, поэтому пошел читать дальше. Придумал сразу задачу В, написал и сдал с плюса. Вернулся к А, повыписывал формулы на листочке, некоторые из них проверил через тестсистему на определенных группах. Где-то к концу первого часа ее сдал. Прочитал оставшиеся задачи. Изначально не до конца понял условие С, но зато были идеи в D. Тк задача разбивалась на два случая, один из которых представлял из себя отдельную группу, я начал писать ее. Сдал одну группу, осталось придумать второй случай. Думать долго не пришлось, написал и словил WA. Перечитал код, пару ошибок нашел, но это не помогло продвинуться дальше. Еще раз перечитал код и, как оказалось, я написал функцию построения ДО, а ее не использовал. Заслал и получил AC. Вернулся к С. Время как-то быстро прошло, а оставался уже один час. Перечитал условие, написал брут на 60 баллов. Начал исследовать поведение рекурсии и как-то отсечь просмотр лишних вариантов. Придумал отсекос через графы, но он словил ML. Оставалось 15 минут, а по задачам E(в ней при чтении условия не было никаких идей дальше перебора) и F(были идеи на 55 после прочтения, но долгие по написанию) не было баллов, поэтому решил написать на них бруты. На F у меня была идея через суффавтомат на 55 баллов, но времени не хватало, поэтому написал на 35.

Что случилось:
1) неожиданно для меня время быстро подошло к концу
2) правильный тактический ход под конец олимпиады взять частички на остальных задачах

Мой профиль

Александр Лосев:

Олимпиада ЗКШ:

13-14 в целом и 2-ой(?) среди белорусов - неплохо, но не более теперь для тебя

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

неожиданно для меня время быстро подошло к концу

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

... перечитал код
... еще раз перечитал код
... пару ошибок нашел
... написал функцию построения ДО, а ее не использовал.

Мой профиль

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

13-14 в целом и 2-ой(?) среди белорусов - неплохо, но не более теперь для тебя

Я 3ий. Там еще из Могилева один человек был.

Мой профиль

COCI 2022 Round4:

В задачах АВ проблем не было особых. Прочитал С. Начал перебирать варианты идей. Остановился на разделяй-и-властвуй. Начал выписывать формулы с системами, дошел до системы. И, казалось бы, вроде ошибок математических не допускал, но даже первый семпл не подходил под формулы. За 10 минут не нашел никаких мат ошибок в формулах, поэтому отказался от идеи с разделяйкой, хотя она и была сильно заманчива. Подумал про корневую асимптотику. Сначала думал над корневой декомпозицией, а потом пришел к полной идее. "Большой" случай проверил - работает. А "маленький" случай был чуть посложнее из-за формул. Решил сначала написать для этого случая идею перебором, а потом вывести формулу. Минут 30 выводил, я считаю, что это долго. Оставалось 2 часа на другие задачи. Переборы были очевидны, поэтому я пока их не писал. В задаче Е была группа на m = 2. Подумал, что тут случаи надо разбирать, поэтому думать над ней не стал(а вот и зря). В D думал в сторону жадника и/или модификации центроидной декомпозиции, но толком ничего и не придумал(даже для частного случая цепочки).

Что произошло:
1) сильно морочился с формулами в C. Даже сдав задачу я все равно не понимаю, чего я неправильного сделал. Может не все случаи выписал? Но это крайне маловероятно. Может даже стоит на листке и писать определения обозначений, которые я ввожу, чтобы было легче искать ошибки
2) когда рассматривал идею на D через жадник, то я не рассмотрел вариант с дихотомией по ответу.
3) Зря я не разобрал случай в Е с m = 2, так как от него можно было уже легко полное решение придумать. Нужно уделять КАЖДОЙ подзадаче хоть какое-то время

Мой профиль

Второй отбор на ИОИП2022:

Прочитал задачу А. Не с первого раза понял условие. Пришлось минут 10-20 потратить на его понимание, и то неполное. Прочитал оставшиеся задачи. На задачу В сразу была фулл идея, поэтому пошел решать D. На нее тоже сразу пришла полная идея. Написал и словил WA. Поменял компоратор сортировки - ОК. Вернулся к А. Решил написать хоть какое-то решение, словил 0 баллов. Перешел писать В. Написал и словил неполный балл. Перечитав внимательно код, я нашел ошибку, про которую думал, когда писал, но ее все равно допустил(по привычке пишу циклы от 0, а нельзя было ведущие нули выводить, поэтому надо было с 1). Вернулся к А. Перечитал еще пару раз условие и я наконец-то получил полную картинку об условии и цели в задаче. Сначала придумал наивное решение, которое как раз было фулл, но я еще доказывал то, что оно будет не хуже некоторых других крайних случаев, которые можно сделать. Написал и сдал. Осталась С. Сначала написал что-то на подобие жадника. Словил только балл на вторую подгруппу, понял, что идею дальше развивать не надо. Выписал формулу, получил четкую цель в задаче в виде ориентировке графа так, чтобы колво исходящих ребер было равно колву входящих(это исходит из формулы подсчета ответа суммы по всем in[v] * out[v], а максимум достигается тогда, когда in[v] = out[v]). Написал жадное решение, сначала ничего не брало, поисправлял баги и получил баллы за третью группу. Думал, что уже хорошо, есть куда развивать идею дальше. В итоге так и не добил ее до конца, поэтому решил объединить 3 решения на 3 группы, чтобы взять 56.

Что произошло:
1) долго не мог понять условие, тк невнимательно читал(медленно, но не достаточно)
2) в задаче С не увидел задачу о нахождении эйлерова цикла. А точнее, я не знал, что в нем колво исходящих ребер равно колву входящих. А знал только про главное его свойство существования

На досуге:
1) решил задачу D с последнего див1(2800 рейтинга на ней стоит на кф, она же задача с открытки, которую сдал только один белорус). Придумал ее за минут 10, а реализовал с последующим поиском ошибок минут за 40-50. Решил я ее нестандартным методом и немного сложнее авторского решения, а именно:
В задаче надо было соптимизировать некоторую ДП. Авторы это сделали с помощью свойства, которое можно доказать. А я решил воспользоваться методом оптимизации разделяй-и-властвуй. Только не той, где выполняется свойство opt[i] <= opt[i + 1] <= opt[i + 2], а которая очень редко встречается. А точнее, сначала посчитаем рекурсивно значения ДП в левой половине, потом с помощью этих значений прорелаксируем значения ДП в правой половине и рекурсивно обновим значения ДП справа.
Ссылка на задачу: https://codeforces.com/contest/1648/problem/D
Ссылка на таблицу результатов открытки(это 4ая задача первого дня): https://olympiads.ru/zaoch/2021-22/onsite/standing.shtml
2) зашел чуть дальше, на задачу Е того же див1. Пока что смог определить точно тему. Там задача похожа на старую задачу с респы "западный поток", про которую неоднократно уже повторял. Есть какой-то граф с весами на ребрах, надо построить с помощью него второй большой граф, а с помощью него обновить значения на ребрах первого графа. Во втором графе много ребер лишних, поэтому нужно уметь строить в нем миностов. Так как там граф большой, а в лоб считать нельзя, то надо воспользоваться алгоритмом Борувки. Мне осталось придумать в нем, как искать минимальное по весу ребро в другую компоненту связности. Функция веса ребра нестандартная, поэтому нужно подумать
Ссылка на задачу: https://codeforces.com/contest/1648/problem/E