Форум DL

Мой профиль

Алексей Данченко:

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

1) решал Rookie SRM 9(контест с topcoder, с настройкой арены и плагинов помог Леша Данченко ),

Здорово. Спасибо Лёше и от меня!

Пожалуйста! Правда, справедливости ради, я был не один, а вместе с Лешей Ропаном. Мы сейчас создали канал в телеграме, где можем помочь новичкам с настройкой topcoder арены и плагинов.

Тогда спасибо и тебе, и Лёше Ропану.

Мой профиль

COI 2021:

Прочитал несколько раз задачу А и никак не мог понять, что от меня просят вывести. Прочитал В и понял, что ничего не понял. Ну хотя бы понял С и D. Начал думать над D.
Сразу пришла в голову разделяйка, так как что-то подобное точно решается разделяйкой. Начал шаманить над способами сортировки через РиВ, но получал постоянно либо 8 баллов на тест n = 8, либо 0. Где-то час перебирал разные методы и все бесполезно.
Вернулся на А и начал перечитывать условие, пока я его не пойму. Минут через 10 я наконец-то допер до того, что от меня хотят. Придумал на фулл и сразу же написал. Прошло много тестов из первой группы, но что-то как-то не заходило. Поэтому я подумал, может не заходило из-за того, что я не выставлял правую границу в позиции r[i], где r[i] - граница интервала какого-то события(у нас либо уходит челик, либо приходит, соответственно на каком-то отрезке будет одно и то же колво челов). Написал и зашло.
Вернулся на D. Подумал, а что если повыводить кучу раз одно и то же, что я выводил в РиВ в первой идее. Написал и начало брать баллы(где-то 40 взяло). Потом для каждого отдельного теста я начал подбирать константы такие, что столько раз я повторю вывод из РиВ. Смог добить тем самым где-то 77 баллов, но я впилил в код еще и брут за линию запросов и дошло до 80+ баллов.
Переключился на С и написал первую группу. Придумал идею на 3ю группу через троичные маски, написал и словил WA где-то далеко не в первом тесте группы. Думаю, что могло быть не так. Как оказалось, у меня в решении не всегда выгодно делать квадраты, которые соответствуют мин/мак координатам из списка, поэтому я забил на С и перешел на В, так как там 0 баллов было. Прочитал, вроде понял условие и написал группу для M <= 2. Получил свои 0 баллов и думаю, что может быть не так. Перечитал условие и смотрю на рисунок из условия. Меня смущала фраза "челик опеределил порядок кирпичей". Я постановил задачу как "вам нужно найти оптимальный порядок", а не то, что в условии подразумевалась эта фраза как "вам дан список кирпичей и вы должны их по порядку класть". Придумал кубический солв. После получения своих баллов за куб, я придумал быстро оптимайз до квадрата и сдал на фулл.

По ошибкам сказать ничего не могу, но в D я был прав, что на фулл там разделяйка. Я не стал добивать решение, так как были нерешенные А и В.

ВсОШ 2021 день 1:
С Ашкой проблем никаких не было.
А вот с Вшкой были проблемы. Начал думать в сторону жадного решения, так как я подобное постоянно решал как "попробую поставить как можно меньший символ на эту позицию".
Для меня в задаче была больше проблема, чтобы насчитать правильно массив f[i] такой, что мы можешь удалить отрезок [i + 1; f[i]) с помощью символа i. Я перебирал разные жадности и стресстестил их через обычные маски, но так и ничего не заработало. В таком случае пошел на D.
Сразу придумал решение на частичные группы, где n <= 500. Написал и с первого компила заработали семплы. Заслал и получил свои 34 балла за группы n <= 2000, немного подумал и понял(+доказал), что асимптотика решения-то быстрее оказывается. К удивлению, решение зашло с первого компила, такое у меня очень редко случается. Подумал, стоит ли добирать еще 34 балла за восстановление ответа, но я этого побоялся и пошел на С.
Решил взять 10 баллов самым тупым способом, но я очень долго исправлял ошибку IL(на dl это ATL). Вообще было не понятно, почему код не работал. Я искал и исправлял баги, но все было бесполезно до того момента, пока не переписал код. Получил 10 баллов и придумал решение на баллов 20+(точно оценить этого вообще нельзя было). Подумал, что лучше написал это решение, чем думать над другими задачами, так как оно было очень легкое. Опять я наткнулся на ту же проблему с IL, я его чуть ли не до конца контеста исправлял. После него я словил TL, что вообще было странно, ибо я как минимум 1 бит за игру передавал. Я за ход передавал 2 бита(типа ход (i; j) соответствовал четностям из строки). И постоянно за ход я покрывал максимум 4 клетки. Так как я покрываю мало клеток, то я за игру передаю как можно больше битов, соответственно, играю как можно меньше игр, чтобы передать строку. Так как игр максимум было |s|=10^5, то асимптотика в каком-то нереально худшем случае должна была быть O(|s| * 32 * 32), что было приемлимо. До конца контеста я никак не смог исправить TL, поэтому остался с 10 баллами по ней.

Что было не так?
В задаче В моей ошибкой было то, что я не подумал над решением в ДП. Так как что, если не ДП, когда не заходит жадник?
После получения 34 баллов по D было ошибкой садиться за С, так как там реализовать восстановление было очень просто(я сначала дорешал на 68, чтобы удостовериться, что было правильней больше подумать над восстановлением и пойти его писать, чем переходить на С). Соответственно, я принял поспешное решение и неразумно оценил ситуацию.

ВсОШ 2021 день2:
С А проблем не было.
Прочитал В и придумал самый тупой жадник, который можно было сюда придумать. Написал, поделал тестов, некоторые падали, соответственно, я исправлял попутно баги. Заслал и получил 7 баллов, что очень странно, так как я рассчитывал на фулл. Еще полчаса где-то посидел и подумал, где чего не хватает или где вообще неверно что-то написано. Вроде все было правильно. Я решил, что лучше понабирать баллы по С и D.
В задаче С я придумал 50 баллов моментально. Быстро написал и получил эти баллы.
Пошел на D. Сначала подумал над тем, какие группы легче, а какие сложнее. Сначала решил написать решение на группы с n <= 20 через битмаски. Было два варианта бимтасок: когда мы использовали mask верши, и когда использовали mask ребер. Я выбрал второй вариант, так как мы в вершины могли 2+ раз зайти, но не могли использовать ребро дважды. Пришлось немного пописать и получил за эти группы баллы. Первые две группы были проще, как оказалось. Вторая группа была частным случаем задачи со старой респы "Западный поток". А вот на третью группу пришлось подумать. Я придумал решение через ДП. То есть я строил дерево обхода в глубину, тогда есть какие-то ребра наверх. Теперь оставалось определять для вершин минимальную стоимость ребра на каком-либо пути вниз, а потом подняться по ребрам наверх. Придумал хранить ДП для каждой вершины такое, что f[v] - минималное время входа(и ее вершина) такое, что я могу подняться туда, если пойду куда-то вниз в поддерево, либо по обратному ребру. Потом я пихал в эту САМУЮ ВЫСОКУЮ вершину(важный термин, чуть позже объясню почему) минимальное значение ребра на пути от 1 до этой вершины. Потом я говорил, что в ЭТО ПОДДЕРЕВО надо пропихать этот МИНИМУМ. До конца контеста у меня никак не заходило это решение, и я так и не знаю, почему. Иногда, я переключался на задачу В, чтобы попытаться придумать медленное решение через что-то, но ничего не приходило в голову, поэтому возвращался обратно на D. Также была идея на С еще на 20 баллов, но там очень муторно было кодить МО(и так на самом деле было, а не как с D первого дня)

Что пошло не так на контесте?
В решении на В у меня не хватало одного if, который был аналогичен тому, который был уже в коде(то есть просто скопипастить надо было и немного поменять), чтобы решение зашло на фулл. Почему я не подумал об этом на контесте? Потому что я писал топсорт на графе без двусторонних ребер. Я думал, что он исключает факт того, что у меня будет существовать ТОЛЬКО одно ориетнированное ребро от вершины v до предка. А это оказалось не так.
Теперь самое интересное. Задача D. Я не просто так написал фразы капсом, так как они встречались в разборе на полный балл. Для 3ей группы они сжимали граф на компоненты вершинной связности. Соответственно я был близок к полной идее. В третьей группе было сказано, что все пути от 1 имеют фиксированное макс ребро. А в полном мы сортили ребра и фиксировали макс ребро, а потом уже на поддереве в миностове этого графа мы ДОшкой записываем минимум на пути от 1 до этой компоненты.

Мой профиль

Ограничение на колво символов в сообщении сопутсвовало разделению его на два отдельных

Я не просто так позндо отписался, так как подумал, что лучше написать "с высока", когда уже дорешать большинство задач и знаю полные идеи на задачи.
В задачах 1_4, 2_2 и 2_4 я был максимально близок к фулл идеям(в 1_2 она вообще была фулл). Почему я их не придумал? В 1_4 я посчитал, что лучше брать баллы по 1_3, тем самым сделав сеюе хуже. В 2_4 я решал подводку к полной идее, так и не решив ее.
Опять повторюсь, что нужно думать не только о задаче и где больше баллов легче взять, а еще и о том, правильно ли я вообще принимаю решение.

Мой профиль

COI 2021, Россия 2021 (День1,2)

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

Поэтому главная цель таких разборов/анализов – понять, почему не берёшь и что надо делать по-другому на олимпиаде

Какие я вижу проблемы и решения (читая твои отличные описания процессов решения задач)
Особенно для сложных/непонятных задач

1. Чтение условий

Надо читать медленнее, внимательнее, въедливее.
НЕ упускать никаких важных фактов и замечаний
После прочтения переформулировать ПИСЬМЕННО условие
оставив математическую постановку задачи
Затем перечитать условия на предмет пополнения своей постановки задачи упущенными фактами
Подчеркнуть факты, которые должны влиять на решение
Установить сложность (N, NlogN…) полного решения

2. Фиксация потенциальных идей/алгоритмов решения

Сразу после прочтения условия нужно составить список (Андрей Костяной так делал)
Возможных идей, применимых для этой задачи, желательно как можно более полный, чтобы правильная идея в нём точно была

3. Разработка минимального множества тестов, на которых будешь проверять решение
(семплы, основной случай, все возможные особенные/крайние случаи)

4. Мысленная отбраковка идей анализом их применения к зафиксированному множеству тестов, выбор рабочей идеи

5. Медленное вдумчивое кодирование, в идеале исключающее ошибки в коде
(Гена Короткевич практически так и пишет)

6. При необходимости встроенный контроль корректности работы (assertion)

Глобально
Возможно надо больше времени думать и меньше времени писать (тем более отлаживать)

Мой профиль

ВсОШ 2019 Day1:

С А проблем не было, посидел подольше и подумал над деталями реализации. Сдал с плюса.
Прочитал В. Начал думать над разборами случаев в зависимости от того, что мы знаем. Посидел, поразбирал каждый из 8ми случаев и выписал все их на листок. Сначала закодил ДОшку, чтобы потом не забыл, на каком из случаев я остановился и какие уже написал. Когда уже пришла очередь разбирать случаи, я смотрел на их на листочке и попутно проговаривал + писал комменты, что я здесь разбираю и как. К сожалению, без багов не обошлось. Перечитывал код и просматривал/проговаривал случаи, правильно ли я их написал. Все равно ловил WA, поэтому пришлось написать стресс-тесты, подбирая ограничения под генерацию тестов, чтобы с большим шансом словить WA. Нашел багу и исправил - получил АС.
Прочитал C и D. На С я сразу придумал 39 баллов. Подумал, как можно развиться, чтобы взять группу за квадрат, но все безуспешно. Перешел на D. Хотел набрать где-то 30+ баллов, поэтому я не думал над самым банальным решением, а что-то в сторону разделяйки. Тоже не хотело в голову приходить что-то адекватное, поэтому написал штуку с откатами, которая не заходила. Передумал, и решил написать 21 балл на нее и пойти остальное время отдать Сшке.
Решил закодить сначала 39 баллов(на запас, вдруг ничего не придумаю еще). Прочитал третью группу и думал, какой задаче эквивалентно. Так как я подобные задачи, как 3я группа, решал, то в голову быстро пришла мысль про аналогию с карточками. Написал и словил RE. Из-за того, что у меня три абсолютно разных решения были в одном коде, то у меня RE выдала переменная из решения второй группы. А точнее, когда я чистил битсеты, то у меня они и выдавали RE, так как ограничения там стояли под 2ю группу, а я чистил после объявления n. Взял 56 баллов и начал думать над фуллом. В голову пришла мысль, что надо было компактно хранить длины путей в вершине и перебрасывать через блоки(для 5-6 групп) по r. Вектор развития идеи был, а времени не хватало его добить, поэтому решил подумать над 4ой группой(аналог 3ей, но чуть быстрее надо было реализовать). Придумал ДОшку с разделением по весам ребер, но уже не хватало времени, чтобы это все реализовать.

В целом, что получилось на контесте, а чего не получилось:
1) думал больше, чем писал
2) быстро находил ошибки
3) не хватило времени подумать еще больше в С, чтобы дойти до полной идеи

ВсОШ 2019 Day2:

Прочитал А. Подумал над асимптотикой решения + ее погрешностью, так как юзались lower_bound'ы. После подсчетов я решил пойти писать. Пока писал, я попутно проговаривал, что я делал в этом куске кода. Словил WA, получив 70 баллов, что очень странно для такой ошибки. Поделав 5-10 тестов я словил багу, продебажил и нашел ее.
Прочитал В. Написал жадное решение на группу с n = 1 и словил WA. Решил перечитать условие, может где-то не так понял. Да, я тогда подумал, что у нас классы независимо друг от друга покупают себе парты, а на самом деле в начале покупают парты, а потом классы независимо друг от друга их себе распределяют. Начал перебирать медленные жадные решения. Почему я их перебирал? Я не мог как-то математически/логически доказать их правильность. 1-2 жадника не зашли, но с 3его уже зашла группа с m = 1(то есть у нас 1 класс). Решил от него уже отталкиваться. Написал ДП - на 70 не зашло. Написал жадник и получил эти 70 баллов. (ДП не заходило из-за того, что я не сортировал группки как vector <vector <int> > из-за свойства opt[i] <= opt[i + 1], про которое я еще не догадывался). Посидев, подумав над оптимайзами на фулл, я решил лучше набрать 80 баллов на запас. Я развивался в сторону когда m >= sqrt(maxM) и m <= sqrt(maxM), для m >= sqrt(maxM) я умел решать(то есть это группа для 80 баллов), а для второго случая идей не было. Решил отсортить группы pr как vector <vector<int> > и проверить, идут ли оптимальные парты по неубыванию(заслал солв с assert). Оказалось, что это было так(думал, что это было бы +-логично) и написал оптимайз через разделяй-и-властвуй.
Прочитал С и D. Начал думать над D, чтобы потом больше времени уделить Сшке(D на вид + по группам выглядела ужасно). Написал сначала 16 баллов через Кнут-Моррис-Пратта, позже добил еще 10 баллов(все решения зашли с +).
Написал в С сначала брут за O(n * m), чтобы потом анализировать поведение ответа в игре. Подумал над второй группой немного и в голову ничего не приходило. Для 3ей группы я решил сгенерить маленькую матрицу с такими ограничениями, чтобы посмотреть поведение матрицы-ответа. Заметил закономерность и решил ее написать. Постоянно ловил WA. По началу была ошибка в том, когда у нас n = 1, либо m = 1, из-за чего у меня индексы в - уходили. Чуть позже я адаптировал код и, по словам ЯК, я словил RE(на дл не пишет вердикта во время контеста, а на области/респе он выдается). Естественно, я начал стресс-тестить солв на WA, а также на RE. Нигде ничего не падало. Начал читать код и думать, могло ли здесь упасть по RE(тот я пока не знал, в чем прикол

). Так и до конца контеста и не допер, где бага. После переотправки солва в РО я словил WA(опа, нежданчик был). На ЯКе на эту задачу стояли криво группы, а также группировка тестов была неверной

. Сегодня я достал тест, продебажил код и, недодебажив до места с багом, я его нашел. У меня была ошибка ровно в одном символе!!! Для i во втором цикле стояло значение i = m, тем временем это был номер строки, а правильно было поставить i = n. Тем самым я потратил 1,5 часа просто в никуда, когда мог взять эти 14 баллов и развивать ее до полного/частичного с полной идеей(а эта группа была подводкой к фуллу).

Что здесь произошло:
1) правильное решение было в А сделать 5-10 маленьких тестиков
2) перебор +-логичных жадосов в В, а также их попутных оптимайз
3) невнимательное чтение кода при дебаге Сшки. Лучше уже тогда вернуться к случаю, как в первый день, еще медленней писать, но брать баллы ГАРАНТИРОВАННО и с меньшим колвом багов

Мой профиль

Оригинальные результаты Россия 2019

Место	Участник	1	2	3	4	5	6	7	8	Баллы	Диплом
1	Гайнуллин Ильдар Ленарович (Республика Татарстан, 10)	        100	100	56	50	100	100	100	91	697	1	Победитель
2	Морозов Александр Дмитриевич (город Санкт-Петербург, 11)	100	100	100	55	100	100	100	26	681	1	Победитель
3	Ефремов Андрей Павлович (город Санкт-Петербург, 10)	        100	100	100	35	100	88	44	16	583	1	Победитель
4	Шатов Олег Викторович (Московская область, 11)	                 100	100	100	21	100	88	34	36	579	1	Победитель

У тебя
1 Лосев Александр Log Беларусь Гомель СШ 27 11 а 523 100 100 56 21 100 100 20 26

до 4 места 523 -> 579
до 1 места 523 -> 697

Чего тебе не хватает?

Мой профиль

Что, по-моему, очень правильно, надо применять и развивать

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

ВсОШ 2019 Day1:

посидел подольше и подумал над деталями реализации. Сдал с плюса.
Посидел, поразбирал каждый из 8ми случаев и выписал все их на листок.
пришлось написать стресс-тесты. Нашел багу и исправил - получил АС.
Так как я подобные задачи, как 3я группа, решал, то в голову быстро пришла мысль про аналогию с карточками.

1) думал больше, чем писал
2) быстро находил ошибки

ВсОШ 2019 Day2:

Поделав 5-10 тестов я словил багу, продебажил и нашел ее.
Решил перечитать условие, может где-то не так понял.
Решил отсортить группы pr как vector <vector<int> > и проверить, идут ли оптимальные парты по неубыванию(заслал солв с assert). Оказалось, что это было так(думал, что это было бы +-логично)
все решения зашли с +.
Написал в С сначала брут за O(n * m), чтобы потом анализировать поведение ответа в игре.
Для 3ей группы я решил сгенерить маленькую матрицу с такими ограничениями, чтобы посмотреть поведение матрицы-ответа. Заметил закономерность и решил ее написать.
Сегодня я достал тест, продебажил код и, недодебажив до места с багом, я его нашел.

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

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

Мой профиль

ВсОШ 2018 Day1:

Прочитал А. Немного подумал о деталях реализации и решил пока не писать, а подумать над В.
Прочитал В. Начал думать, в каких случаях у нас выживает этот вирус в бактерии. Разобрал пару случаев(они логические, поэтому чертить особо не приходится). Доказал, что это правильно и начал ее писать(кстати, асимптотически решение работало за O(n ^ 4 / 64), а на контесте я на это внимание не обратил, но знал, что зайдет, так как мы это решали 2 года назад и кто-то сдавал ее с такой же асимптотикой). Сдал с плюса и вернулся писать А, чтобы просто на хвосте не весела. Тоже сдал с +.
Прочитал С, придумал 1-2 группы и 4-ую, решил отложить и прочитать D. Придумал 34 балла, на 67 сильно не замахивался, поэтому решил вернуться к С. Написал эти группы и получил свои должные баллы за них. Решил подумать над 5ой группой. Как я люблю делать в таких задачах, так это выписывать сначала формулы для подсчета ответа(после области прошлого года и после контестов с зубренка я так и начал делал, потому что я умел писать CHT/Li Chao Tree, а задачи с этих контестов не решил из-за того, что формулы не выписывал). После выписывания формулы моментально заметил формулу прямой и решил написать Ли Шао, чтобы набрать еще 16 баллов. Решил подумать еще над 16 баллами за 3ю группу(еще более соптимизированный брут). Придумал решение через ordered_set. Написал и получил еще 16 баллов. Дальше был выбор: придумывать С на фулл, либо придумывать D на 67. Выбрал первый вариант.
Итого было 4 часа на придумывание идеи на С. Я перебирал все возможные методы оптимизаций. Основная идея была верной, а надо ее соптимизировать... Перепроверил все методы оптимизаций через разделяй-и-властвуй + CHT. Подумал над ДО + CHT в ее вершине. Все было безуспешно, так как в этих случаях нужно знать для элемента больше информации, чем в есть в нем. За час решил все-таки написать 34 балла на D, чтобы были. За последние полчаса я только догадался, что туда надо использовать корнячку. В следствие чего я не успел додумать ее до конца и остался с 62 баллами.

Что произошло:
1) Хорошо начал. Первый час был, как по мне, без ошибок.
2) Плохо закончил. За 4 часа не решить простую задачу надо еще постараться. Отклонился от тактики. Я не посчитал худшую асимптотику, которая могла зайти на эту задачу

ВсОШ 2018 Day2:
Прочитал А. Немного подумал о том, как мне быстрее ее реализовать(типа надо было брать максимум на отрезке и его самую правую позицию). Подумал о sparse table и решил быстренько закодить ее. Написал и сдал с плюса. Прочитал В. Эту задачу я не забыл, так как помнил, что здесь на фулл были элементы рандома. Соответственно, я сначала думал о 80 баллах, а потом на фулл рандомы додумать. Сначала придумал 50 баллов(самое наивное решение), написал на всякий пожарный. Подумал: "что будет, если делать операции с конца над отсорченным массивом". Придумалось решение, которое почти всегда ставило число на свою позицию за 1 операцию, но в худшем случае за log. Решил написать и получил 80 баллов. Тут уже вернулся к рандомам. Решил порандомить тесты и посмотреть колво операций. Все тесты работали за 2n операций в среднем. Придумал, что если загенерить промежуточную перестановку(ну типа в таком случае должно быть 2n + 2n = 4n операций). Написал и сдал задачу. В С сразу написал 50 баллов. Потом решил подумать еще над баллами за тесты с последней группы(там каждый тест в группе = 1 балл). Подумал над "лучшими" случаями для какого-то определенного элемента. Написал на ласт группу O(n^3 * logn) и получил уже 55 баллов(на dl почему-то не стоит каждый тест последней группы = 1 балл). Начал отсекать лишние случаи. Получилось уже 4 случая, 2 из которых решались отдельно от других 2. Написал O(n^2 * logn) и получил 63 балла. Начал думать над их оптимизацией для фулла. Вторая пара случаев решалась быстро, а вот первая была проблемной. Думал в сторону всяких свойств/зависимостей от какой-то информации при переходе от префикса/суффикса к след префиксу/суффиксу. Но все безуспешно. Решил пойти на D, чтобы там не было нуля и отдать все оставшееся время ей. Сначала написал группы на 12 баллов(6-8 группы). Потом придумал группу 9(просто перебор). Начал думать над группами 1-5. Сначала написал группы 1-2, чтобы понять, какие есть варианты жадностей при данных ограничениях. Получил 20 баллов(1-2, 6-9 группы). Придумал, как написать жадник на 3ю группу. Написал, кое-как я его отдебажил и в последние минуты заслал. Потом до меня доперло, что оно еще должно зайти на 4ую группу, так как там стояли битсеты. Я увеличил ограничения, открыл задачу и время вышло!

Итого вышло: (100 + 100 + 62 + 34) + (100 + 100 + 63 + 24) = 583 балла(как раз не хватило тех 2 баллов, которые не успел заслать)

Что произошло:
1) в задаче С не подумал о том, чтобы ЕЩЕ сократить общее колво случаев, чтобы можно было соптимайзить до фулла. Но в то же время я бы не набрал баллы по D. Даже не знаю, что было бы лучше

Мой профиль

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

ВсОШ 2018 Day1:

Итого было 4 часа на придумывание идеи на С. Я перебирал все возможные методы оптимизаций. Основная идея была верной, а надо ее соптимизировать...
Перепроверил все методы оптимизаций через разделяй-и-властвуй + CHT. Подумал над ДО + CHT в ее вершине. Все было безуспешно, так как в этих случаях нужно знать для элемента больше информации, чем в есть в нем.

За последние полчаса я только догадался, что туда надо использовать корнячку.

Получается перепроверил НЕ ВСЕ методы оптимизаций.
Выпиши и зафиксируй в форуме ВСЕ методы оптимизаций с указанием их области применения

Отклонился от тактики. Я не посчитал худшую асимптотику, которая могла зайти на эту задачу

Надо постараться исключить отклонение от тактики в будущем

ВсОШ 2018 Day2:
Что произошло:

1) в задаче С не подумал о том, чтобы ЕЩЕ сократить общее колво случаев, чтобы можно было соптимайзить до фулла. Но в то же время я бы не набрал баллы по D. Даже не знаю, что было бы лучше

Получается ты более менее устаканил чтение условий, обумывание деталей и кодирование.
И на первый план выходит проблема придумывания?

XXX Всероссийская олимпиада школьников по информатике
Ульяновск, 1 - 7 апреля 2018 года
Результаты

Место	Участник	                                                1	2	3	4	5	6	7	8	Баллы	Диплом
1	Анопренко Михаил Валентинович (город Санкт-Петербург, 11)	100	100	100	67	100	80	100	72	719	1	Победитель
2	Сафонов Иван Андреевич (город Санкт-Петербург, 11)	        100	100	100	67	100	80	78	52	677	1	Победитель
3	Николенко Даниил Юрьевич (Московская область, 11)	        100	100	100	67	100	80	100	26	673	1	Победитель
4	Романов Владимир Олегович (Москва, 10)	                        100	100	69	34	100	100	97	66	666	1	Победитель

твои 583 против 666 - 719

Чего тебе не хватает, чтобы набирать такие баллы?

Мой профиль

ВсОШ 2017 Day1:

Прочитал А и сразу пропустил, так как идея моментально появилась, а писать надо было мало. Прочитал В, придумал решение через битовый бор. Так как я про память редко задумываюсь, а из-за нее было все проблемы, то я решил написать. Долго исправлял баги(около минут 15-20), после получил 80 баллов. Немного подумав, я решил посчитать память и начал придумывать новое решение. За минут 10 придумал и сдал Вшку, а перед тем, как ее придумать, я сдал А с плюса. После прочитал С, немного подумал о разделяйке, но не смог продвинуться дальше брута. Прочитал D. Решал я ее последовательно. Сначала подумал о построении нового графа и смотрел, что будет дальше. Дальше подумал о топсорте, чтобы проходиться без всяких проблем с обратными ребрами. Потом про ДП подумал, выписал формулу, как я люблю, увидел формулу прямой. Я всегда пишу на оптимизации ДП через выпуклую оболочку дерево Ли Шао. Написал медленно и постепенно код. Словил багу в виде неверного написания топсорта

. Получил 92 балла(все группы, кроме последней). Подумал, что лучше добить эти 8 баллов, чем тратить время на придумывание разделяйки в Сшке. Минут 20 посидел, поисправлял "потенциальные баги". Потом я опять посмотрел на память. Два раза за один контест попался в ловушку

. Посмотрел на коэффициенты в прямых и написал CHT через стек за линию памяти. Осталась Сшка, решил написать сначала решение на 32 балла через битмаски. Написал и получил 32 балла. Подумал, зачем хранить многоугольники, если можно их триангулировать и спрашивать каждый по отдельности. Решил перебрать каждый треугольник и спрашивать его(я точно оценить не мог, сколько это было запросов, поэтому я это написал). Получил те же 32 балла. Начал думать над оптимайзом до 41 балла. Придумал решение со страшной асимптотикой, но потенциально с аккуратной реализацией должно было их брать. До конца контеста так и не смог соптимизировать решение(один тест падал).

Что произошло:
1) Два раза попался в ловушку с памятью.
2) Сдал быстро D

Day2:

Быстро придумал А и опять же решил пропустить. Придумал В и начал постепенно реализовывать, со временем выводив промежуточные значения для проверки корректности работы. Сдал В с плюса. В А был баг с неверной проверкой построения строки-ответа. Прочитал С и начал ломать голову. Раз 20 перечитывал условие и не понимал, как вообще ответ получался. Пошел на D. Придумал 50 баллов. Начал думать над большими баллами, подумал про разделяйку, так как остальные темы никак вообще не подходили, но и разделяйку я никак адаптировать не мог, поэтому написал 50 баллов и вернулся на С. Так как куча перечитываний условий не помогли мне, я решил перебирать разные решения на первую группу через ДП(вторая бралась тем же решением). Спустя несколько вариантов и пропихов у меня зашла первая группа. Писал я квадратное ДП по подотрезкам через, опиравшись на пару фактов из условия. С помощью этого ДП я смог проанализировать поведение ответов на разные тесты и интерпретировать условие в подобное задачи о игре. Посмотрел на ограничения для групп. Опять большие ограничения, после первого дня я уже обратил внимание на память и она была нестандартная(обычно 256 МБ ставят, а тут 128 поставили). Посчитал память для решения через rmq с O(A * logA) памяти. По подсчетам брали 80 баллов, решил написать. Дальше думал в сторону фулла с меньшим колвом памяти. Заметил факт, что отрезки запросов постоянно на 1 сдвигаются, а подобное я где-то на командной в прошлом году(или два года назад), Леша сдавал подобное через очередь/дек. Я и подумал, что такое должно брать фулл, так как памяти около линейного. Получил 88 баллов и удивился. Дальше уже я ничего придумать не смог.

Что произошло:
1) не знаю, правильно ли было тратить 20+ минут на перебор всяких ДПшек, чтобы ее проанализировать. Возможно, я бы быстрее понял условие, а возможно и нет. Тут неоднозначно уже
2) Исправил ошибку первого дня и обратил внимание на память

Мой профиль

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

ВсОШ 2017:

Что плохо
Два раза попался в ловушку с памятью
Day2:
В А был баг с неверной проверкой построения строки-ответа.
В C Раз 20 перечитывал условие и не понимал, как вообще ответ получался.

Что хорошо
Быстро придумывал и адаптировал к проблемам решения
Придумал В и начал постепенно реализовывать, со временем выводя промежуточные значения для проверки корректности работы. Сдал В с плюса.
Так как куча перечитываний условий не помогли мне, я решил перебирать разные решения на первую группу через ДП
я уже обратил внимание на память

Приятная статистика

XXIX Всероссийская олимпиада школьников по информатике, Заключительный этап
Иннополис, 26 марта - 1 апреля 2017 года

Место	Участник	1	2	3	4	5	6	7	8	Баллы	Диплом
1 Шпаковский Денис Станиславович (Челябинская область, 10)	100	100	90	100	100	100	64	50	704	1	Победитель
2 Анопренко Михаил Валентинович (город Санкт-Петербург, 10)	100	100	90	73	100	100	76	55	694	1	Победитель
3 Дроздова Александра Алексеевна (город Москва, 11)	        100	80	90	73	100	100	92	55	690	1	Победитель
4 Кассихин Илья Алексеевич (Удмуртская Республика, 11)	        100	100	90	73	100	100	68	50	681	1	Победитель

У тебя 670 у них 681-704
До 4-го всего 11 баллов

Надо искать резервы
В чём они?

Мой профиль

COCI 2021 Round1:

Прочитал А. Делать нечего в ней и пропустил. Прочитал В, сразу придумал решение, начал думать над базой ДП. Продумав В я прочитал остальные задачи и начал реализовывать первые две таски. А сдал быстро, но в В были баги как раз с базой. Минут 10-20 исправлял этот баг. Подумал над С. Сразу придумалось 5мерное ДП, но из-за страшных переходов в нем я решил пропустить. В Dшке решил немного подумать, если дальше не продвинусь, то не буду больше над ней думать, так как там что-то непонятное было. В Ешке изначально думал в сторону каких-либо графов, так как через ДП тут никак нельзя было ответ считать. Никак построение графа и работы с нем не мог придумать, но в голове вертелась жадная идея за квадрат, которую я не мог доказать. Так как идей толковых не было, как раз решил ее проверить. К моему удивлению, этот жадник прошел и начал оптимизировать решение через граф. Придумал решение через граф + односвязные списки, написал и словил баг. Перед тем, как исправлять баги, я придумал более оптимальное и более легкое решение через стек. Написал и сдал на фулл. Решил сначала С написать на 20 баллов, а потом уже может быть писать то решение со страшными переходами. Так как мне было больше страшно за дальнейшее долгое исправление багов в решении с 5мерным ДП, то я воздержался от его написания и решил подумать над более легким в написании. Решил поделать тестов и повыводить ответ, заметил одно свойство, но подумал, что может быть только для маленьких ограничений это свойство работает. Паралелльно придумалось ДП с этим свойтством, но тоже не хотел его писать. Никакие квадратные решения не приходили в голову вообще. Так и до конца контеста не хотел ничего из этого писать.

В авторском решении С решалось через 5мерное ДП, но там оно более умное и с другими состояниями.

Мой профиль

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

COCI 2021 Round1:

Плохо, хотелось бы исключить
в В были баги как раз с базой. Минут 10-20 исправлял этот баг.

Хорошо
- А сдал быстро
- Сдал сложную задачу E "методом последовательных приближений"
- Так как мне было больше страшно за дальнейшее долгое исправление багов в решении с 5мерным ДП, то я воздержался от его написания и решил подумать над более легким в написании.

Резерв для усиления
Подумал над С. Сразу придумалось 5мерное ДП, но из-за страшных переходов в нем я решил пропустить.
В авторском решении С решалось через 5мерное ДП, но там оно более умное и с другими состояниями.

Мой профиль

20.02.2022
COCI 2021 Round2:

Прочитал все задачи и не увидел особой необходимости в написании А и В, так как там писать в принципе нечего. Больше зашла задача Е, но изначально условие мне не поддавалось. Прочитав оригинальное условие(на английском) до меня дошла финальная концепция задачи. Сразу придумал решение на фулл, но решил сначала проверить его более медленную версию за O(Q * n * logn). Написал, семплы работали и словил неожиданный TL. Начал проверять всякие разные мелкие детали через assert'ы и пришел к выводу, что это все из-за лога в асимптотике не заходит(по подсчетам все с запасом должно было брать свои баллы). Поэтому решил написать фулл решение. Быстренько досдал задачу и пошел писать А и В, которые тоже сдал быстро. Решил подумать над D, так как там что-то сильно под ДП косило, а Сшка на лютый Ad Hoc. Сначала появилась идея на 10 баллов, которую я писал долго(ну как писал, баги исправлял). А именно у меня было не до конца продуманные переходы. Из-за чего не все варианты считало. Дальше смог придумать решение на 60 баллов за O(n^4 * l). Не стал это писать, так как там очень много крайних случаев и мерзкой реализации с формулами. Пошел думать над С, чтобы хоть какие-то баллы взять. Придумал абсурдное решение, которое не известно было на сколько вообще зайдет. Решил написать, так как дальше я бы никак не продвинулся. Получил 8 баллов, но это хоть что-то

Что случилось:
1) не до конца продумал переходы в D, мало крайних случаев проверил перед написанием кода
2) быстро сдал Е, что очень неплохо, как по мне

Начались сборы ЗКШ(MWJ2022), 22.02.2022, распределительный контест:

К сожалению, контесты в формате ICPC, а не IOI.
Быстро сдал А, проблем не было.
Быстро придумал жадность в Bшке, но с первого раза не прошло, была немного глупая бага. Решил, что у меня неверный жадник и написал умный перебор, который тоже не зашел. Решил написать стрессы, так как ручные тесты работали все. Пока стрессил, у меня вылезло то, что брут выдал неверный ответ. Загвоздка в том, что я использовал встроенный подсчет битов в числе через __builtin_popcount(), который плохо работал с лонгами, из-за чего мне пришлось потратить время на понятие этого(я не знал, что он с лонгами плохо работает, там можно было дописать ll в конце и было бы ок) и в итоге написал вручную этот метод. С тоже была простой, +3 из-за того, что я брал в ответ сумму, а не максимум, а также неверно искал циклы(через СНМ искал, хотя граф ориентированный был). В D я очень много думал. Не заметил главного факта, из-за чего я начал рыть в задаче еще глубже. Так как все сдавали эту задачу относительно быстро, то я решил просто написать ленивое(рекурсивное) ДП, чтобы не заходить в лишние состояния, в итоге оно зашло и я был удивлен, почему это не ловило TL(позже в группе объяснили прикол). В Ешке думать не надо было, расписал формулы, написал ДО и получил АС. Fка сильно смахивала на задачу с первого командного питерского контеста. Я сразу начал развивать уже готовый кусок идеи, чтобы решить эту задачу. Изначально я делал что-то очень близкое к тому, что было в той задаче. Позже словил WA, начал стрессить и наткнулся на фишку, из-за которой надо было добавить лишний лог в асимптотику, который бы давал TL. Быстро придумал решение с разделяйкой. Написал и словил TL. Прогнал макс тест локально и получил около 6 сек. Убрал локальные вектора - 3,9 сек. Заменил вектора на массивы - 2,9 сек + АС.
На G не оставалось времени подумать, но там задача не особо сложная была на ощущение. Задача Н была геома, которая немного похожа на задачу из ВКОШПа старого.
Думаю, что G я точно дорешаю, а вот над Н уже сомневаюсь, так как геомы на респе не будет.

Что произошло:
1) не знал выходки __builtin_popcount() с лонгами, буду знать
2) сильно гнался за временем сдачи задачи, из-за чего ловил лишние посылки из-за глупых ошибок. Лучше я уже сдам задачу на 10 минут позже с +, чем на 10 минут раньше с +2

Мой профиль

Хорошо
1. Умеешь придумывать
2. Умеешь искать ошибки
3. узнал про __builtin_popcount() с лонгами
4. Борешься, не сдаёшься (3:54 - последнюю задачу сдал за 6 минут до конца)
5. Правильный вывод

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

Причём это для IOI олимпиад тоже важно соблюдать

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