Форум DL

Мой профиль

Сборы
16.12.2021-17.12-2021

Day3:

Прочитал А, быстро придумал и написал. Словил WA и нашел несколько тестов, которые падают. Исправил так, что мои тесты зашли, но все равно ловил WA. Введя макс тест у меня размер ответа превышал размер максимально возможный по условию(30000 максимум, а выводило 40000). Пришлось убрать лишние операции(я сначала шел вверх по диагонали, потом по этой же диагонали вниз, перешел на некст диагональ и тд, а надо было вверх по диагонали, на следующую, вниз по диагонали, на следующую и тд). Исправил и словил WA. Подумал, ну ладно, переключусь, чтобы не зацикливаться на одной задаче. Сдал быстро В и С без всяких проблем и вернулся на А. Написал в коде чекер для ответа, то есть правильно ли у меня ходит по матрице или нет. Были подозрения на некоторые случаи в тестах(n > m или n < m). Потыкал пару тестов и словил WA на маленьком тесте в следствие чего я исправил ошибку и дальше начал тыкать около 15-20 тестов -- все работали и я сдал А. Прочитав D, я сразу придумал решение, написал и сдал.

В такого рода задачах, где можно написать чекер на ответ, после ловли WA стоит его написать и тестить через него

Day4:
Прочитав задачу А, я сразу начал разбирать случаи. На самом деле я их не разбирал сам, так как в семплах уже были даны ВСЕ нужные нам случаи, только надо было приписать три строчки для пересчета кратчайшего расстояния до какого-то центра.
Прочитал В и сильно испугался ее, так как я сначала понял условие как "найти подмножество в массиве с размером не более 100 и ксором (A ^ B)". Внимательно перечитав задачу , я осознал, что там надо не ксор, а или, поэтому быстро написал и сдал В.
Прочитал С и D, подумал, что C легкая и написал ДП f[i][j], которое искало кратчайшее расстояние до клетки (i; j). Много времени потратил на исправление багов(правильное расставление ребер). Словив WA, я начал задумываться над правильностью идеи, в следствие чего я доказал, что идея неверная, через существование теста, который позволял проходить через не минимальные клетки и получать итоговый минимальный результат. На задачу С, к сожалению, потратил много времени впустую на неверную идею(около часа), что скажется чуть позже.
Переключился на D. Начал думать что-то с бором(ну тут было очевидно, что надо с бором делать что-то). Посмотрел на то, как у нас строится ответ и придумал HLD на боре. Но я не спешил его писать, тк тут запросы на дереве были в виде "посчитать сумму на пути от корня до вершины", вспомнил, что можно такое решать через Эйлеров обход на дереве и ДФ. Заслав код, я словил WA. Начал думать над случаями, когда в вершине не просто двойка стоит. Придумал тест, что мы должны ставить 2 в две последовательные вершины, что не выгодно по условию задачи, поэтому я исправил баг и сдал задачу.
Вернулся на С и написал очевиднейший брут на нее через очередь. Построил граф и просто прошелся по всем возможным состояниям в матрице(их не более (n * m) ^ 2). На группе, где n, m <= 100 у меня маркировка ловила ML, тк состояний же (n * m) ^ 2, поэтому я придумал оптимайз на 91 балл через обработку графа по слоям(такое можно было писать, так как мы всегда идем в матрице вниз по строкам, а вверх не можем подниматься). Сдал на 91 и думал над фуллом. Начал думать в сторону ДП, так как с очередью уже делать по сути нечего. За 15 минут до конца контеста придумал ДП с переходами через битсеты, но не успел реализовать(вот и сказался тот час, потерянный в пустую).

По поводу дорешки на досуге:
1) http://codeforces.com/contest/1608/problem/G (отличная, по-моему мнению, задачка на HLD и суффмассы на путях HLD, тренировка "силы рук")
2) задачка со старой республики на HLD(http://dl.gsu.by/task.jsp?nid=1116349&cid=19), которую можно решить через Эйлеров обход, но для тренировки сойдет

Мой профиль

Еще забыл добавить:
Перед тем, как сесть писать впервые С, я доказывал свое решение через меньших матриц к большим
То есть допустим я решил задачу для матрицы (1; m), то при решении для матрицы (2; m) добавляется последняя вторая строка и комбинируется решение через решение для (n - 1; m) и (1; m), но я не учел момент, когда у нас ответ переходит через начало координат(через x = 0), поэтому у нас может ответ измениться, аналогично задаче с отбора на ВКОШП, где при одном запросе мы могли перейти через 0 и улучшить ответ

Мой профиль

Было бы хорошо явно выделить в конце сообщения

1. Что сделано неверно, что надо делать по-другому и как в аналогичной ситуации в будущем.
2. Зафиксировать полезные приёмы, которые надо применять.

Мой профиль

Сборы
20.12.2021-21.12-2021

Day5:
А сдал за 5 минут, проблем не было.
Прочитал задачу D и придумал на нее решение через ДО на эйлеровом обходе дерева. Словил WA на последней группе и подумал, что ошибка может быть в проталкивании. Переписав проталкивание я все равно словил WA на той же группе и подумал, что зачем мне еще и времена выхода инкрементировать, если они никак не влияют на спуск ДО(но из-за WA они как-то повлияли). Убрал инкремент на временах выхода из вершины и словил ОК.
Дальше я пошел думать над В. Придумал жадную идею, которая должна была брать 60 баллов. Когда заслал свою идею, я словил баллы на группах, где массив был из различных элементов. Так как у меня падала даже первая группа, то я начал искать маленький тест, который будет падать. Минут через 20 я его смог найти. Изначально я не понимал, почему у меня не работает этот тест, но ,немного внимательнее просмотрев код, я осознал, что так как у меня неразличные элементы, то я не все варианты ответов перебираю(типа я перебирал штуку, с помощью которой жадно набирал ответ). Сначала хотел исправить ошибку в текущем кодее, но было безуспешно и решил его переписать под более общий случай(ну и занимало это строк 30 кода вместо 70). Когда словил 60 баллов(обычный квадрат), я быстро придумал оптимайз на него и сдать задачу.
Оставалось мало времени, а если точнее, то полтора часа, я быстро написал 30 баллов через битмаски(не какими-то странными жадосоми, как набирали 30 баллов другие ребята, а доказав, что для количества центральных элементов не более 5, будет мало неоднозначных клеток). На все следующее время я думал в этой задачу в сторону потоков или паросочетаний, так как я уже решал много задач подобного видна(где есть матрица, там надо что-то сделать, чтобы для каждой клетки выполнялось какое-то условие), которые и решались потоками/парсочами

Day6:
Быстро сдал А и С без всяких проблем.
Так как B словила WA на третьей группе, я искал тест именно под эту группу, который будет падать. Найти его не смог, но параллельно я просматривал код и переписал небольшой кусочек кода, в котором и оказалась бага.
Остались 4 с половиной часа и осталась задача, в которой нечего было делать, кроме как пихать. Я написал рекурсию на все операции. Так как цифр всего 6, то у нас 5 перегородок, в которые я могу всунуть один из 12 вариантов сочетаний символов операций(либо пустой символ, то есть слить прошлое число и цифру). Много времени занял метод, в котором надо было решать этот пример, который сгенерили, а вся проблема была из-за скобок. Наконец дописав решение примера, я начал писать еще несколько проектов следующего типа:
1) слить файл с общим ответом и ответом генератора этих самих ответов(рекурсии)
2) преобразовать ответ в константный массив
3) код с конечным ответом и константным массивом

После генерации около двухсот вариантов ответов, я начал убирать поочередно некоторые операции, которые бы сократили время работы рекурсии, тем самым быстрее говорить "No solution", либо доставать ответ.
К концу 4ого часа было сгенерено около 40000 ответов, что очень мало. Я оставил операции вида "слить", "+", "-", "*" и до конца часа догенерилось еще где-то около 7000. Итого оказалось 24 балла. А я рассчитывал где-то на баллов 50-60 через такой метод генерации ответов

Выводы:

Day1:
Из-за того, что я посчитал свою интерпретацию задачи верной, я поздно заметил ключевой факт в задаче, который я пытался исправлять в последние минуты. Надо задаваться вопросом:"точно ли эта интерпретация верная? Не будет ли она хуже какой-то другой?"

Day2:
Внимательней читать задачи

Day3:
Когда надо писать такого рода реализации, стоит попутно задавать себе вопрос "что я здесь делаю? Правильно ли я это делаю? Где здесь я смогу словить багу"

Day4:
Так как я придумал жадную идею на С, я поспешил ее писать, не доказав ее верность.
Перед тем, как засылать код, нужно закинуть в текстовый документ несколько тестов и запустить свой код на них

Day5:
Надо изучить подробнее возможности 2-SAT и дорешать Сшку через него

Day6:
Дома стоит писать контесты вида challenge, где дают NP-полную задачу и надо на ней набрать как можно больше баллов(по какой-то формуле они вычисляют), тем самым тренируясь придумывать, где надо, пропихи

Мой профиль

Сборы
23.12.2021-24.12.2021

Day7:
Прочитал А и начал ручками разбирать несколько случаев. Закодил их и словил 68 баллов. Немного подумал и переключился на В. На В сразу пришла идея в голову, но я долго исправлял баги на семплах и сдал с плюса. Ошибка была в том, что я не в том порядке дихал моменты. То есть надо было дихать сначала момент, когда граница второго отрезка упрется в границу первого, а я его в последнюю очередь дихал. Прочитал С и D, решил, что D легче, так как из-за D <= 12 было очевидно, что надо писать маски. Немного подумал, посчитал на калькуляторе асимптотику, увидел большое число и немного испугался. Начал думать над линейным через комбинаторные формулы, но ничего в голову не пришло с этой идеей, поэтому начал писать ДП по маскам хотя бы на 87 баллов. По хожу написания кода у меня в голове параллельно придумалось доказательство того, что это будет фулл, поэтому быстро закодил и сдал D.
Вернулся на А. Придумал перебор всех перестановок и разобрал немного больше случаев ручками. Быстро закодил и сдал.
Осталась С. Сначала думал в сторону ДП. Придумал жадное ДП и знал, как его соптимайзить до n * logn, если надо. Закодил его и заслал, словив 27 баллов, вместо 60 для квадрата. Поэтому решил думать уже над жадным решением. Перебирал варианты жадности, собирая как-то набор ответов последовательно, отсортировав t(ну это было самое логичное, так как если писать брут, то для каждого элемента i в ответе нужно было, чтобы выполнялось условие t * c >= pref_sum, то есть суммарно съеденных продуктов до данного момента времени меньше либо равно доступного количества). Начал шаманить со вторым семплом(он был относительно хороший), добрался до такого решения: пока в ответ нельзя запихнуть элемент i, то будем удалять из ответа такой элемент, что его количество больше, чем k[i]. На втором семпле сработало, закодил решение и сдал С
Как по мне, этот день прошел +-гладко и по тактике. На данный момент у меня 0 претензий к моим действиям в этот день

Day8:
За 5 минут сдал АВ.
На С сразу в голову пришли маски из-за ограничений, но воздержался сразу их писать, так как не всегда мы бы хранили в состоянии mask верную строку. Поэтому я немножко подумал и доказал, что надо сортить массив по возрастанию, а потом уже писать маски. Тем самым мы в последнюю очередь в ДПшку будем пихать то состояние, которое последним включало пару с большим a. Это я проверил брутом за O(2^n * n^3), который я потом быстро соптимайзил до O(2^n * n^2), но можно было еще без одного n, но оно и так в ограничение вкладывалось.
Оставалось 4 с половиной часа на D. Я сразу написал на 25 баллов конструктивное решение. Начал думать на фулл, исходя из третьей группы. Думал, что в случае, когда a[i] * 2 + 1 < a[i + 1] будет всегда "NO", но это, к моему сожалению, оказалось не так из-за чего мой "фулл" взял 40 баллов. Думал я над конструктивным решением. Сидел ручками над тестоми с n = 2, потому что для n > 2 решение вообще никак не меняется, просто левую часть не надо трогать. Ручками перебирал какой-то алгоритм, который МОЖНО написать за квадрат. В итоге нашел метод, который заработал на 4-7 моих тестах и начал его кодить. Словив 40 баллов, я сильно разочаровался, так как по-моему мнению для остальных случаев ответ был бы No. Я до конца был уверен, что здесь будет конструктивное решение, поэтому остальные два часа я также продолжал перебирать алгоритм руками, тем самым исписав около 5 страниц блокнота и полностью ручку.
Как оказалось It's a trap
Я попался в свою же ловушку. А если точнее, то совершил ошибку на моменте взятия 25 баллов. Я не подумал о другом и самом важном варианте. Я ранее уже писал, что когда надо построить матрицу, то иногда задачи решаются через потоки/парсочи. И в этой задаче так и оказалось, что она решается парсочами/потоками!!!! В следующие разы в таких задачах я буду уже выбирать один их трех вариантов развития идей: 2-sat, конструктивное решение и потоки/парсочи

Мои планы на каникулы:
1) Все еще дорешать ту задачу на HLD + суффмассы (http://codeforces.com/contest/1608/problem/G)
Я продвинулся дальше семплов, но не дальше первого теста после семплов

Стало очень сложно искать ошибку в коде с 440 строками кода. Я уже не смог и взял тест(он большой, поэтому взял дерево из тесто, оно было маленькое) и начал шаманить над строками и запросами уже вручную
2) поботать задачи на 2-sat, чтобы закрепить полученный прием
3) Порешать виртуалки BOI(как минимум 2 дня, а может даже и 4)

Мой профиль

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

Мои планы на каникулы:
...
Стало очень сложно искать ошибку в коде с 440 строками кода. Я уже не смог

Надо разработать отдельно тактику поиска ошибок.
Например
1. Системное, структурированное, модульное кодирование.
2. Перечитывание кода (помодульно)
3. Автономное тестирование модулей (функций)
4. Интеграция решения, брутового решения и генератора тестов/считывателя тестов, подготовленных вручную
с автоматической сверкой результатов (по итогу и на отдельных модулях/функциях)

2) поботать задачи на 2-sat, чтобы закрепить полученный прием

Согласен.

3) Порешать виртуалки BOI(как минимум 2 дня, а может даже и 4)

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

http://octobronze.pythonanywhere.com/

Рейтинг	Город	Фамилия и Имя	Последний раунд	Дата
2157	Гомель	Галух Никита	Codeforces Round #758 (Div.1 + Div. 2)	11.12.2021
2124	Мозырь	Полынь Станислав	Deltix Round, Autumn 2021 (open for everyone, rated, Div. 1 + Div. 2)	28.11.2021
2119	Гомель	Кругликов Игорь	Codeforces Round #759 (Div. 2, based on Technocup 2022 Elimination Round 3)	12.12.2021
2100	Гомель	Лосев Александр	Educational Codeforces Round 117 (Rated for Div. 2)	22.11.2021

Мне кажется более полезной как минимум до областной олимпиады такая работа:

1. Дорешивание наших олимпиад
2. То, что ты делал со сложными Codeforces-задачами.
3. Решение сложных задач BY/GO (2021, 2020, ...) в режиме дорешивания

Мой профиль

27.12.2021 ИОИП2020:

Над АВС я сильно не парился и быстро сдавал, багов не ловил
В Dшке идея сразу в голову пришла, но пришлось подумать о том, как аккуратно реализовать идею. Подумал, что можно же просто только в две стороны(вправо, вниз) в лоб проходится и помечать клетки вместо проходки рекурсией.
В Е сразу пришло в голову, что на фулл тут разделяйка, начал искать свойства операции из условия. Изначально заметил, что когда мы пытаемся сказать, что отрезок [l; r] хороший, то у нас останется число, которое не превосходит максимума на этом отрезке +15, так как у нас сказано, что на операцию тратится два числа, а log2(10^5) ? 15. Ну тогда понятно, что надо фиксировать максимум на отрезке и что-то дальше делать. Я примдумал какую-то странную штуку и начал ее реализовывать. После того, как я написал 50% кода, у меня вылезла страшная асимптотика, которая почти хуже квадрата и начал думать над квадратом.
Прошло минут 20 и проанализировав группы и операцию, то можно было сделать a[i] = 2^a[i] и рассматривать операцию, как сумму всех чисел на отрезке, которая должна равняться степени двойки. Написал разделяйку на группы, где a[i] <= 30 и получил свои баллы. Начал думать над квадратом под общий случай(a[i] <= 1e9) и придумал просто в лоб все обрабатывать без шаманством над степенями двойки. Еле-еле допихал решение на 66 баллов и оставалось 15 минут до конца и ничего не смог придумать.
Оказалось, что надо было считать степени двойки по большому модулю и писать разделяйку. Такой способ можно использовать, но надо уметь оценивать шанс коллизий с модулями.

Я эту задачу до сих пор не дорешал на dl, но на кф за 1,7 сек заходит. Пытался писать абсолютно все. Использовал и unordered_map, и ordered_map, и gp_hash_table, и просто map, но ничего не хочет заходить. А реализация авторов почему-то заходит на фулл за 0,9. Пока что вообще не замечаю подвоха в их решении.

02.01.2022 21_rui1:

С первыми двумя проблем не возникло.
Прочитал C и D и начал думать над D, так как там пахло оптимизацией ДП, в чем я очень хорош.
Придумал квадрат и моментально заметил в формуле пересчета ДП функцию прямой и сразу пошел писать Ли Шао.
Когда написал я словил WA не на семплах и минут 10 в коде искал ошибки, но все безуспешно. Написал брут, чтобы получить баллы за квадрат и начал стресс-тестить Ли Шао на тестах с n = 1000. Словил WA и начал дебажить. Понял, что надо еще в три раза больше завести деревьев Ли Шао, чтобы уже точно зашло. Исправил - сдал
Подумав немного над Сшкой я понял, что это классическая задача на ретроспективный анализ в играх, которые можно представить как граф.
Я изначально неверно представил граф, на котором надо запускать анализ. Я сначала начал за квадрат перебирать ребра с одинаковыми цветами и эту пару ребер представлял как ребро. Потом пытался вместо анализа проверять через ССК, но все пошло не по плану и я не мог найти даже ниодного теста, в котором бы ломалось. Под конец от безысходности я написал самый тупой брут, чтобы были баллы, а не 0.

Оказывается, мне не надо было мудрить и переделывать граф, на котором идет игра. Нужно было на текущем просто в лоб запустить анализ и все бы зашло

Ошибки:
Не могу во время контеста автоматизировать проверку идеи до написания кода. Когда у меня приходит идея, а потом передумываю, что она неверная, у меня зачастую бывает наоборот, что первая идея верная, а вторая - нет

По другим задачам:
1) https://codeforces.com/contest/1215/problem/F
Задача на 2сат
Быстро придумал на него решение за квадрат через 2сат и получил ожидаемый TL на большом тесте. Думал, как сделать меньше ребер
Заглянув в разбор, я увидел гениальную мысль в виде того, что можно было определить значение в вершине, как какое-то выражение.
2) За неделю руки не дотянулись найти тест на задачу с HLD + suffarr(https://codeforces.com/contest/1608/problem/G), но в ближайшее время буду писать на него брут и стресс-тестить
3) Достал интересную задачу с каким-то умным приемом - https://codeforces.com/contest/665/problem/F. Пока что не читал разбор, но там надо уметь считать pi(n) при n <= 1e11 по мере проходки по элементам до какого-то определенного значения, зная, что pi(n / x) убывает с увеличением x

Мой профиль

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

Оказалось, что надо было считать степени двойки по большому модулю.
Такой способ можно использовать, но надо уметь оценивать шанс коллизий с модулями.

Пожалуйста, подробнее зафиксируй КАКИЕ проблемы решаются таким способом.
Коллизии с модулями решаются использованием нескольких модулей (2, 3 ...)

Я эту задачу до сих пор не дорешал на dl, но на кф за 1,7 сек заходит. Пытался писать абсолютно все. Использовал и unordered_map, и ordered_map, и gp_hash_table, и просто map, но ничего не хочет заходить. А реализация авторов почему-то заходит на фулл за 0,9. Пока что вообще не замечаю подвоха в их решении.

Надо обязательно разобраться

Оказывается, мне не надо было мудрить и переделывать граф, на котором идет игра. Нужно было на текущем просто в лоб запустить анализ и все бы зашло

Надо научиться ДОКАЗЫВАТЬ самому себе правильность идей.

Ошибки:
Не могу во время контеста автоматизировать проверку идеи до написания кода. Когда у меня приходит идея, а потом передумываю, что она неверная, у меня зачастую бывает наоборот, что первая идея верная, а вторая - нет

Неважно какая идея первая, какая вторая. Повторюсь:
Надо научиться ДОКАЗЫВАТЬ самому себе правильность идей

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

Хорошо бы ОБОБЩИТЬ в каких случаях так надо поступать.

Мой профиль

Дорешал задачу Е с ИОИП2020:
Почему не заходил gp_hash_table, а потом начал заходить?
Увидел в авторском коде три строки с рандомами:

mt19937 tw(chrono::high_resolution_clock::now().time_since_epoch().count());
uniform_int_distribution<ll> ll_distr;
ll rnd(ll a, ll b) { return ll_distr(tw) % (b - a + 1) + a; }

Спросил у одного человека про структуру. Он скинул доку, где написано, что некоторые операции работают рандомно внутри структуры. А также сказал, что там с хешами есть проблемы и скинул документацию на них.

Сдал задачу 3500 HLD + suffarray:
Почему брало WA3 и как я нашел ошибку?
Написал стресс-тесты на свое решение и встроил туда брут через Кнута-Морриса-Пратта. С первым рандомным тестом у меня слетело. Начал дебажить код и, как оказалось, у меня неверно строилось HLD, чего я вообще не ожидал. Когда я прохожусь по топологически отсортированным вершинам и строю пути, я помечаю, какие посетил, и вот когда я захожу в вершину, которую уже посещал, я выходил из метода, а не переходил к следующей вершине.
Далее я уже словил не WA3, а TL11. Я сгенерил большой тест и начал смотреть, где у меня работает слишком медленно. В данном случае у меня работало медленно построение суффмассов. Я писал построение суффмассов за O(|s|*(log2(|s|)^2)) при s <= 5 * 10^5 без дополнительной памяти для подсчета lcp соседних суффиксов. Я переписал этот метод под способ с дополнительной памятью и работой в O(|s|*log2(|s|)) и потом слетел 107ой тест по RE. Дальше мои предположения просто иссякли, но я начал думать, где могло выходить за границы. Проходился по коду в том порядке, как он выполняется, и думал, что может тут пойти не так и какие случаи этому способствуют. Минут 30 поперечитывал код и придумал, что когда я нашел новые границы в суффиксном массиве и словил уже ответ 0, то есть l > r, то при дальнейшем спуске/подъеме по дереву у меня либо r уменьшается(стоит if(bad(r)) r--;), либо l увеличивается, соответственно при маленьком r у меня индекс становится отрицательный и выдает RE.

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

Мой профиль

Сначала напомню про вопросы без твоего ответа

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

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

Оказалось, что надо было считать степени двойки по большому модулю.
Такой способ можно использовать, но надо уметь оценивать шанс коллизий с модулями.

Пожалуйста, подробнее зафиксируй КАКИЕ проблемы решаются таким способом.
Коллизии с модулями решаются использованием нескольких модулей (2, 3 ...)

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

Хорошо бы ОБОБЩИТЬ в каких случаях так надо поступать.

Как ДОКАЗЫВАТЬ самому себе правильность идей

Далее про последний разбор, он очень хорош, но снова не хватает акцентированных выводов

Как сдать сложную задачу

1. Рандомный тест + брут (поиск теста с ошибкой)
2. Дебаг для локализации и исправления ошибки
3. Большой тест (для борьбы c TL), анализ времени выполнения фрагментов кода
4. Вдумчивое перечитывание кода для поиска "мест с ошибками".

Мой профиль

Область 2022:

Day1:
С первыми двумя задачами особых проблем не испытывал. Их я сдал минут за 10-20.
Прочитал С и решил дальше прочитать D, так как на С сразу идеи никакие не возникли.
D оказалась классической задачей на раскрытие формулы и поддержку нужных сумм в вершине ДО. Написал и словил WA на первой группе. Как оказалось, ошибка у меня была в формулах при проталкивании(надо было ставить D[v], а не t[v].sum, которая является суммой всех чисел на отрезке. D[v] - значение, которому будут равны все элементы на отрезке). В 10 часов уже сдал D на фулл.
Осталась С и я думал над темами, которые подойдут на эту задачу. Сразу отсек вариант с ДП, так как там никакого ДП быстрее, чем за O(2^n), не напишешь. Если не ДП, то тогда что? Правильно, жадник. После выставления темы я начал думать над вариантами взятия элементов массива жадно. Обычно, если в задаче есть ксоры, то задача на бор. Я и подумал о боре и начал думать, как ведут себя элементы из ответа в боре. Придумал жадность, немножко подумал, правильно ли это, и начал писать. После того, как я написал решение и словил ВА3, но с группой, где в числе k ровно один бит, я начал писать стресс-тесты.
Всего были две ошибки в решении: я неправильно брал пару индексов, когда я встретил в боре старший бит из k, и я неправильно выводил ответ, когда k = 0. Первую ошибку я заметил на стресс-тестах. Я открыл калькулятор и перевел пару чисел, которые у меня неверно брало в ответ(лишние), и k в двоичку и смотрел, как у меня спускалось по бору. Как оказалось, надо было написать еще одну функцию, которая параллельно спускалась в боре по двум вершинам так, чтобы ксор был больше либо равен(асимптотику я заранее доказал). Заслал и закрыл контест

Какие выводы?
Я считаю, что в Dшке ошибился из-за невнимательности. А в Сшке я мало подумал о том, правильно у меня будет брать пару индексов, когда я встретил старший бит из k. Соответственно в таких моментах стоит побольше выделить времени на исследование плохих случаев.

Day2:
С первыми двумя задачами проблем не было. Сдал их за 10 минут.
Прочитал С и начал думать над жадностью за квадрат, так как в такого рода задачах придумывается сначала жадность и оптимизируется какими-либо структурами. Перебрал и написал жадных решений штук 5, наверное, но никакое не было верным. Решил написать решение на 33 балла и перейти к D.
В D не было групп на маленькие ограничения за приличные баллы, поэтому начал думать над решением, когда у нас нет запросов удаления, а просто запросы кол-ва ПСП на отрезке. Отталкиваясь от ограничений, я вычислил максимальную асимптотику, которую я мог бы использовать в задаче. Получилось O(n * sqrt(n) * log2(n)). Я посчитал это не просто так, а чтобы знать, какие алгоритмы можно юзать и что вообще дальше делать. Изначально надо было найти все парные скобки и сказать, является ли этот отрезок ПСП. Дальше у нас запрос колва ПСП на отрезке преобразовался в фромулу суммы k * (k + 1) / 2 по всем "цепочкам" из ПСП. Цепочка - это ПСП, которая является конкатенацией нескольких других ПСП, то есть выглядит это так: (...)(...)(...) и тд. Над чем дальше я думал? Я подумал про преобразование всех ПСП в дерево и какими-то запросами на поддереве, но я не придумал, как правильно считать те цепочки, которые не входят полностью в отрезок запроса. Потом я посмотрел на худшую асимптотику для задачи и подумал над корневой оптимизацией. Сразу отсек вариант с разбиением строки на блоки по корень, ибо дальше неизвестно было, что вообще надо делать и как считать. Потом было два варианта: либо разбить случай, когда колво цепочек было больше/меньше корня, и решать каждую из двух задач отдельно, доказав асимптотику, либо разбить цепочки на тяжелые и легкие, и также их решать отдельно. Я выбрал второй вариант, написал код и словил WA. Решил написать стресс-тесты и группу, когда колво запросов равно 1(то есть ответ на запрос не хуже линии). После стресс-тестов оказалось, что я не обновлял одну переменную в случае с легкими цепочками. Заслал и получил свои 63 балла(все группы без обновлений зашли).
Оставался час до контеста и я решил все равно подумать над квадратным жадником в С. Спустя полчаса не было идей и решил попытаться добить хотя бы 5 баллов, где n <= 40, через рандом шафлы + ДП. Никакие оптимизации и константы не брали более 33 баллов(то есть столько же, как и просто решение за O(2^n)).

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

COCI 2021 Round 5:
Первая обычная реализация. Во второй у меня была бага с подсчетом ответа, но все равно сдал быстро.
Прочитал дальше остальные 3 задачи и меня больше привлекала Eшка, так как там задача на запросы

Решил подумать над квадратным решением на Е. Спустя полчаса-час я смог подумать только о разделяй-и-властвуй для оптимизации ДП(не той, где opt[i] <= opt[i + 1], а такой, что мы сначала считаем все переходы в левой части, потом считаем все переходы для правых элементов, пересекающих центральный элемент, а потом подсчет, когда все переходы в правой части). Но это решение было за O(q * n * log^2(n)), чего не хватало для решения при n <= 3000. Плюс тут вообще не понятно было, как считать ответ за лог, если отталкиваться от этого решения.
Дальше решил думать над С. Похожую задачу давали на отборе на Шумен, на контесте которой я взял по ней 0 баллов, но позже я ее дорешал. Решил взять похожую идею для Сшки(то есть в каких случаях у нас будет убегать первый игрок и выходить в ничью, а в каких второй). Придумал пару доказанных на примерах фактов, которые я уже позже решил закодить. Зашла группа, где все ребра были общего цвета, значит уже факты верные. Оставалось посмотреть места, где у меня решали ребра первого цвета или второго. Решил сделать несколько ручных тестов и сверить мой ответ и программный. Сделал около 5-7 тестов на дереве с 10+ вершинами, и сделал тестов 10 на маленьком дереве. Все работало. Решил написать решение для маленьких ограничений, то есть написать ретроспективный анализ игры на графе. Написал и получил 30 баллов для n <= 100. Начал стресс-тестить и все работало. Решил заслать объединенное решение, чтобы получить 60 баллов и не ломать голову дальше над задачей, но, неожиданно для меня, оно зашло на фулл. Дальше я решил подумать над группами в Dшке, но внезапно придумал фулл, который я не успел отдебажить.

Какие ошибки? Думаю, что стоило бы выделить больше времени на исследование задачи Е, так как там решал всю задачу единственный факт, который либо можно было доказать, либо заметить его при помощи квадратного ДП с выводом оптимального ответа на разных тестах.

Мой профиль

Дорешал область на фулл
Задача 2_4:
Я на контесте изначально правильно прочитал условие, то есть в голове держалось то, что у нас всегда ПСП в двух запросах, но в последствии придумывания идеи для групп без обновлений, я забыл, что отрезок запроса ВСЕГДА будет являться ПСП. То есть после придумывания идеи моя интерпретация задачи выглядела следующим образом:
Есть строка из открывающихся и закрывающихся скобок и q запросов вида "l r". На каждый запрос надо ответить количество подстрок [l'; r'] (l <= l' <= r' <= r) таких, что эта подстрока является ПСП.
А на самом деле, в конце должно быть еще приписано "ГАРАНТИРУЕТСЯ, что подстрока запроса является ПСП"
Именно поэтому я отказался от идеи с деревом, так как мне не было понятно, как считать для подстроки "())(()())(" запроса [l; r]. То есть тут для запроса не ГАРАНТИРОВАННО одна цепочка, а уже целых две, которые пришлось бы по отдельности считать.
Почему я забыл самое важное условие в задаче?
Я привык на контестах из codeforces пропускать легенду и разные лишние моменты из условия, чтобы быстрее прочитать и сдать задачу, то есть получить как можно больше баллов за задачу. На тех контестах может и правильно так поступать, но точно не на 5часовых, где от времени вообще ничего не зависит. На тренировках буду переучиваться читать вдумчиво условие задачи, чтобы таких глупых ошибок не совершать.

Задача 2_3:
Прочитав разбор, я увидел, что надо сортировать по m[i] + p[i]. Я такое на контесте придумал и доказал, но у меня не заходило из-за того, что я при моменте, когда не могу добавить элемент в конец списка, не пытался уменьшить текущую массу списка для того, чтобы можно было бы взять какой-то из следующих блоков и улучшить ответ.
В этом моменте, я думаю, что переволновался из-за того, что у меня долго багалась Dшка и оставалось мало времени на придумывание идеи. Обычно, я смотрю время только для того, чтобы сказать для определенных(-ой) групп(ы), смогу ли я успеть что-нибудь придумать или нет, тут я как раз-таки и оценил, что лучше придумать хотя бы квадрат на С, чем фулл(на тот момент очень сложный фулл с моей интерпретацией задачи) на D. Переволновался я из-за того, что я:
1) долго искал багу в Dшке
2) ниодин жадос не зашел в начале контеста на С
3) никаких домыслов для фуллов(либо частичек, которые оптимайзятся до фулла, но с фулл идеей

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

Мой профиль

21_COCI_6_Mar

С задачами АВС не было проблем.
Прочитал D и Е, начал думать над Е, так как там не геометрия. Изначально было очевидно, что надо дихать ответ. Как надо было проверять? Я подумал о segment tree beats с откатами, так как когда мы дихнули x, мы можем сделать операцию на отрезке a[i] = min(a[i], x) и посчитать колво элементов, равные x(то есть максимуму). А потом откатить обновленные значения.
От этой идеи я отказался по двум причинам:
1) Асимптотика обновлений в segment tree beats суммарно работает за O(log^2(n))
2) Так как мы делаем откаты, то может быть тест, где постоянно задают один и тот же отрезок, который работает за худшее время

Придумал ПДО и сдал быстро задачу.
Оставались 4 часа на D. Я решил взять сначала 50 баллов не брутом(тогда я не знал, что брут берет 50).
Вот допустим мы перебрали отрезок ab и взяли точку c с левой стороны от прямой ab. Тогда надо было быстро проверять, есть ли точка внутри двух лучей ca и cb. Как это проверять я не придумал, но если бы придумал, то была бы подводка к полному решению(в разборе тот же рисунок, как я и описал). Я придумал решение за O(n ^ 3 * log2(n)), которое должно было заходить на 50 баллов, но из-за медленной функции acos оно не брало должные баллы. Я считал два угла при отрезке ab для треугольника abc. Потом надо было узнать, есть ли выпуклый четырехугольник cabd.
Как это проверить?
1) все углы < 180
2) точка c находится слева от прямой ab, а точка d справа
3) исходя из первого пункта, то cab + dab < 180 и cba + dba < 180, углы acb и adb всегда меньше 180. Соответственно отсортим по углу cab и будем проходиться двумя указателями и проверять.

Под конец контеста я ничего не придумал, кроме этого решения(оно брало 20) и брута.
Брут я реализовал как "переберем точку слева от ab и справа от ab и проверим на выпуклость через векторное произведение".
Брут брал 50

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

), контест был для начинающих, но так как я был новорегом, то надо было и написать. Нарешал на топ3 среди рейтед участников, сразу дали мне желтого по меркам TC.
2) Придумал и решил задачу на 3000 рейтинга на кф(http://codeforces.com/contest/1616/problem/H). Задача очень похожа на 1_3 области, но авторское с 1_3 не подходит под нее. Но я на самой области решал не как авторы, а через жадное решение с параллельным спуском по бору. В этой задаче решение такое же, как я и писал на области, только еще с элементами комбинаторики.
3) собираюсь дорешать вот эту задачу http://codeforces.com/contest/1628/problem/E. Что-то интересное, чего я раньше не видел. Минут 30-40 думал и не было идей, как вообще переделать запросы 1 и 2 так, чтобы можно было спокойно их обновлять и отвечать на 3ий запрос, но думал в сторону перестройки дерева для удобных обновлений. Залез в разбор, почитал первые пару предложений. Они там перестраивали дерево под двоичное дерево максимальных ребер(типа найдем максимальное ребро и разделим на две компоненты и строить дальше рекурсивно). Пока что не знаю, как это может помочь для решения задачи, но попытаюсь придумать хотя бы для запросов обновлений до запросов 3его вида(то есть быстро отвечать на 3ий запрос, зная какие элементы включены/выключены)

Мой профиль

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

21_COCI_6_Mar

От этой идеи я отказался по двум причинам:
..
Придумал ПДО и сдал быстро задачу.
[MD] Вот это то что надо - осмысленно принимать правильное решение, а не первое которое в голову придёт.

Замечательно

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

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

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

Мои поздравления

2) Придумал и решил задачу на 3000 рейтинга на кф(http://codeforces.com/contest/1616/problem/H).

Круто.

3) собираюсь дорешать вот эту задачу http://codeforces.com/contest/1628/problem/E. Что-то интересное, чего я раньше не видел. Минут 30-40 думал и не было идей,
...
Залез в разбор, почитал первые пару предложений
...
Пока что не знаю, как это может помочь для решения задачи, но попытаюсь придумать хотя бы для запросов обновлений до запросов 3его вида

Ну или надо было дочитать разбор до конца.
Здорово!!!

Мой профиль

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

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

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

Пожалуйста!

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