Форум DL

Мой профиль

20 мая ср, COI-2019

результат: 0 100 100 51

лог:

- прочитал 1, ужаснулся, т к на самую лёгкую в контесте не было похоже
- прочитал 2, подумал о длинке, увидел модуль, огорчился, пошёл читать дальше
- прочитал 3, придумал реализацию, писать пока не стал
- прочитал 4, испугался, вернулся к 2
- придумал дп по числу, написал (не без мучений с отладкой), прошло, 1:19
- реализация на 3 заняла аж под 40 минут, но в конце зашло, 1:58
- перечитал 4, каким-то местом придумал решение через пересечение префиксов
- долго писал и отлаживал фенвик из сжатых фенвиков из сетов (это вместо трёхмерного неявного ДО, которое бы успешно свалилось по памяти и времени)
- в конце концов дописал, оно вроде даже работало, пока я не запустил первый сэмпл
- где-то в 4:05 осознал, всё это время решал не ту задачу, и пересечением префиксов тут ничо не найти
- переосознал условие (теперь уже правильно), придумал и сдал в 4:40 на 51 через очередь

о выводах: надо было сразу разобрать сэмплы

Мой профиль

20.05.2020

Решал 19COCI7_apr:

1) Прочитал, что-то придумал, очевидно конструктив

2) ДП по числу

3) Реализация

4) Так и не разобрался

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

В первые 2 часа у меня было 0 баллов.

Затем сел за вторую. Там увидел ДП по числу, но на фулл не смог придумать. Вначале сдал на первую подгруппу, а на вторую написал реккурсию. За 1 час я получил 30 баллов.

За третью я сел, чуть подумал и сразу придумал решение на 45, начал писать. Писал где-то минут 30, а потом ещё 30 минут дебага и по этой задаче у меня было 45.Потом пробовал добить задачу до фулла, но что-то пошло не так и я потерял 20 минут.

На 13:09 у меня было 75 баллов.

Затем опять сел за первую, вроде-бы придумал за O(n^2) на подгруппу, где дерево в виде цепочки. Начал писать, написал к 13:30, и затем пошёл дебажить, и так до конца контеста.

В итоге у меня 75 баллов, и 0 отсылок по одной задаче.

Ошибки:

1.Слишком долго сидел над первой, и в итоге потерял час

2.Не добил третью, хотя там немного оставалось

3.Вообще не думал над 4, потому-что сразу не понял, хотя первые подгруппы были лёгкие

Мой профиль

20.05.2020

Сегодня решали тренировку COI-2019.

По-классике первые впечатления о задачх:
1) конструктив, ничего сходу не придумал;
2) сразу же идея о ДП, потом докрутил;
3) симуляция, это понятно с первого прочтения;
4) похоже на ССД, но сходу нет идей, как прикрутить сюда ДО.

После прочтения всех условий я пошел думать 2-ую, довольно быстро придумалась и за минут 20 у меня был перый фулл. После этого мне больше всех симпатизировала 4-ая. Пошел написать на нее подгруппы, чтобы проверить, правильно ли я понял условие и придумал решение. Первая посылка - WA, немного покапавшись исправил на 17, а потом добавил несколько оптимайзов и докрутил до 30. Начал думать над подгруппой без апдейтов. У нас были зависимости между людьми, как изображаем зависимости? Правильно, графы. Ну и подумав про графы я легко докрутил до конденсации графа и "истока". Так к +- 2,5 часу я получил 51 балл по 4-ой и решил переключиться. Решил все-таки взяться за реализуху-третью. Немного обдумал фулл и накатал решение на 1-ую подгруппу, чтобы проверить, правильно ли я понял условие. Подгруппа зашла, поэтому я начал печатать частичное на 45 (так как я думал, что его будет легко исправить на 100). За полчаса набрал еще 40, а потом только (!) через час, я получил фулл. К концу контеста имел 0 100 100 51.

Какие выводы? Я очень долго писал 3-ю. Как было этого избежать? Во-первых, нужно было выспаться, начало контеста для меня вообще было как в тумане. Во-вторых не нужно было писать частичное на 40, так как я просто выбросил 30 минут (похожая ошибка была на зеркале 1-ого тура респы 2020). Почему же я наступил опять на эти грабли? А это уже третья ошибка, я не очень хорошо продумал реализацию и думал, что будет легко обобщить до полного мое частичное. Вывод: лучше продумывать реализацию, ставить "таймеры" (то есть в какой момент я начинаю писать то, что есть, а до этого додумывать до лучших баллов) и больше спать

. Про таймеры я уже писал, но думаю, что лишним не будет себе об этом напоминать.

Мой профиль

21 мая чт, BY-2020-1

результат: 100 100 100 64

лог:
- решать начал с 10 утра, т к проснулся в 8, а потом ел
- прочитал 1, написал две тактики, зашло 0:08
- прочитал 2, идея придумалась мгновенно (ДО по LCA с помощью разрежек, чтобы было O(N * log N))
- кодил и отлаживал эти 90 строк радости до 0:49
- прочитал 3, придумал и сдал на 47 поиском с трисекцией O(N * log3 N) в 1:41
- думал над фуллом на 3 где-то до 2:05, придумалось только частичное на 87 за 2 * N запросов, писать пока не стал
- прочитал 4, выглядело страшно, но быстро обнаружилось короткое решение на 64, которое я и сдал в 2:25
- вернулся к 3, долго тупил
- дотупил до 100 баллов (за 1.5 * N), пошёл писать, закончил в 3:55 и отослал
- оно упало
- т к упало по времени, начал стараться соптимайзить, по пути нашёл одну незначительную багу
- дооптимайзился до 4:41
- осознал, что у меня в коде один отладочный вывод (cerr), и я с ним отсылал всё это время
- убрал отладку, зашло

о выводах: на будущее попытаюсь сделать заглушку на cerr, т к отсылаю такую лажу на интерактивку уже второй раз

Мой профиль

21.05.2020-22.05.2020

Сегодня-вчера было много всяких бытовых дел, поэтому не так много мог решать. Вот что я дорешал за два дня:
1) https://codeforces.com/contest/1354/problem/G, задача с последнего educ-а, придумал дих и как рандомами определять, есть ли в коробке камни, но не додумался, в чем фишка узнавать, есть ли камни в 1-ой коробке.
2)https://open.kattis.com/problems/rainbowgraph, задача на пересечение матроидов (взвешенное), придумал полностью сам, зная только, что там пересечение. Кроме того, нужно было еще всякие прикольные штуки написать, например проверку, будет ли граф связен, если мы удалим одно ребро и вместо него впишем другое (предподсчет за линию, запрос за O(1), иначе TL). Написал код еще вчера, но он выдавал RE 7 (это из-за assert-а, так что я знал, где у меня проблема), но было поздно, поэтому я пошел спать. Сегодня утром были дела, так что за эту задачу я засел +- в 15.00 и очень долго разбирался, что не так. Зато теперь я полностью разобрался в матроидах (даже взвешенных, это более сложный случай) и владею новой техникой. Нашел еще несколько задач на эту тему, планирую в ближайшее время решить для закрепления. Почему я вообще дорешиваю задачи на эту тему, если она не оч распространенная? Потому, что написать пересечение - обычно самое простое (с той точки зрения, что алгоритм известен) и в этих задачах нужно думать всякие другие интересные вещи (например, как я говорил про графы и это далеко не все), чтобы обобщить это пересечение для твоей конкретной задачи.

Мой профиль

22 мая пт, BY-2020-2

результат: 100 100 54 0

лог:
- начал опять в 10
- 1 и 2 задачи оказались простыми и были сданы уже в 0:36
- потом я прочитал 2 и 3 и понял, что всё плохо
- до 2:30 я думал над решениями на 3, пытался придумать хотя бы 70
- не получилось, написал на 54 (в дльке беды с часичной оценкой, поэтому отображает 0)
- закончил в 2:59, начал продумывать рандомный генератор на открытые тесты
- хотя первые 3 теста были решабельны более простым способом, я примерно в 3:20 начал кодить генератор
- задумка оказалась слишком грандиозной для тупого меня, поэтому генератор в 200 строк я дописал в 4:50 и она не работала
- до конца контеста так и не плоучил ни балла по 4, печалька

о выводах: слишком много времени потратил на обдумывание странных идей + очень медленно кодил 4

Мой профиль

23.05.2020

Сегодня дорешивал (кодил я вообще больше, но меня попросили помочь с ДЗ по html, на это много времени потратил). И так, сами задачи:
1) https://oj.uz/problem/view/COI19_izlet, задачи с COI_2019. На DL пока не установили чекер (Виталик уже отослал), так что заслал только на oj, пока что. Сам придумал на 43 (на 25 я еще на контесте писал, но не смог найти ошибку, которую сегодня нашел во время дебага, еще на 18 сегодня додумал), а фулл уже подсмотрел. Очень интересная идея про 2-компоненты, я даже доказал для себя, почему можно в любом порядке соединять. В принципе, если смотреть на задачу с той точки зрения, что если мы знаем дерево = мы решили задачу, то можно додуматься до 2-компонент (потому что это способ восставновить дерево);
2)https://codeforces.com/gym/102156/problem/D, как и обещал, еще одна задача на пересечение матроидов. Кроме матроидов тут нужно было поиграть с базисами (если точно, то нужно было предподсчитать несколько базисов, чтобы ускорить решение) и еще несколько мелочей. В принципе, если знать, что такое базис линейного пространства над полем Z2 и пересечение матроидов, то придумать не очень сложно.

Мой профиль

24.05.2020

Сегодня решали тренировку COCI_2017_R1

Первые впечатления о задачах:
1) реализация, думать не о чем;
2) реализация, немного подумал, как распознавать фигуры;
3) строки и ограничения под O(N * L^2), почти сразу придумал бор;
4) что-то неприятное, скорее всего нужно будет брать максимумы;
5) задача - напишите ДО;
6) что-то интересное на ССД.

После прочтения всех условий написал A и C. Еще через минут 10 сдал E. Итого к первому часу я имел 3 задачи. После этого я решил подумать над 4,6. Попробовал написать бруты на 6, но там не было подгрупп на маленькие ограничения. Еще немного подумал на 4, 6 и решил, что нужно сдать 2-ую, чтобы просто о ней забыть. Так и поступил и к 1.45 сдал еще и 2-ую. После этого я решил перечитать на всякий случай условие 4-ой. Пока перечитывал, вспомнил, что можно сплитовать. После этого быстро придумалось решение, где-то за минут +- 25 я его написал еще за 15 отдебажил и получил полный балл. Итого за 3 часа у меня было 5 решенных задач. Решил перечитать условие 6-ой. Вспомнилось условие, что стороны не пересекаются. При первом прочтении я не особо обратил на это внимание, а теперь меня осенило. Это же намек на лес! После этого задача разбилась на две: построить лес и насчитать на нем ответ. Про ответ были идея с битсетами, но я их быстро отмел, так как они словили бы ML. Стал думать над построением леса. Поставил основные критерии, попробовал прикрутить sweep line. Но я его как-то не до конца докрутил (я обрабатывал моменты, когда касаюсь левой границы, но забыл, что можно удалять из рассмотрения, когда обработана правая граница, из-за этого пришлось писать лишнюю проверку) и придумал как решать эту часть за O(n log^2 n) со сжатым двумерным ДО. Окей, нужно было решить вторую задачу. Придумал идею с прибавлением на пути и соседними lca за O(n log n). Потом придумал идею с переливанием от меньшего к большему, но она была асимптотически медленнее и я решил не рисковать. И так, к +- 4.20 я полностью придумал решение и начал печатать. К сожалению, печатать было много (когда в дорешке сдал, получилось 290 строк) и я не успел к концу контеста.

Отрешал в принципе неплохо, жалко только, что не успел закодить 6-ую. Как я уже говорил, я ее досдал в дорешке и решил разобрать авторское решение. Там я уже прочитал и понял, что не до конца докрутил sweep line и если бы докрутил, то все решение было бы и короче, и за O(n log n). После этого я решил разобрать код Benq, так как он был очень коротким. Он пошел дальше авторов и вообще не использовал ДО для построения леса (та же идея со sweep line, только с помощью set-а). Я немного исправил код с таким построением и, таким образом, дорешал задачу еще и за O(n log n) (и кода только 168 строк).

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

Мой профиль

25 мая

Долги по теории

21 апреля (все задачи BY) - до 13 мая
                                                                    
 2012_1_3. Цифровая строка            ( 2 / 976)   Костяной 
 2010_1_4. Видео сервис               (16 / 215)   Ситников                  
 2017_2_2. Новый факультатив          (17 /  61)   Горбатовский

Текущее состояние в теории (Задано 26 задач)

Решено

             Задачи    ДП 1     ДП 2    Графы   BY_2020
Костяной       19        4        2       6        7
Лосев          18        5        3       4        6
Ситников       14        4        1       4        5
Харрасов       12        5        2                5
Попович        10        6                2        2 
Горбатовский    9        3        0       3        3


 ... дорешать все задачи  – до 17 июня. 

Кроме того, просьба описать решения задач

 Костяной      1_4. Ракета на нейтринной тяге 
 Харрасов      2_4. Ускоритель частиц   Костяной 
 Лосев         1_3. Любимые игрушки - интерактивная 
 Попович       2_3. Марсианские Игры  Лосев 
 Горбатовский  1_2. Вулканы на Венере 
 Ситников      2_2. Очаровательные нейтрино 

BY_2020
День 1  Авторский видео-разбор,   Костяной 
День 2  Авторский видео-разбор,   Костяной

Задания по теории

11 апреля, Тема первого занятия – ДП - до 22 апреля
BY_13_1_3. Бомбардировка ( 5 / 427) Костяной BY_11_1_3. Конькобежная трасса (24 / 131) Харрасов (+Костяной) BY_15_2_3. Космический корабль (13 / 131) Ситников (+Лосев, Коробейников) BY_13_2_3. Турнир ораторов (49 / 51) Лосев (+Харрасов) GO_16_1_4. Диск (33 / 47) Попович GO_11_1_4. RSA++ (87 / 38) Горбатовский

21 апреля (все задачи BY) - до 13 мая
2012_1_3. Цифровая строка ( 2 / 976) Костяной 2011_2_4. Reverse 2D (10 / 297) Харрасов 2010_1_4. Видео сервис (16 / 215) Ситников 2012_2_2. Лазер (17 / 163) Лосев 2011_2_3. Арифметический показатель (50 / 64) Попович Горбатовский 2017_2_2. Новый факультатив (17 / 61) Горбатовский

Графы до 3 июня
BY_2012_2_3. Диверсия ( 4 / 586) Костяной BY_2015_1_4. Служба спасения (11 / 153) Харрасов Костяной (+Коробейников) BY_2013_1_4. Западный поток (17 / 143) Ситников (+Костяной, Лосев) BY_2015_1_3. Путешественник (26 / 68) Лосев (+Костяной) BY_2016_2_3. Праздничное украшение (76 / 19) Попович Горбатовский, Лосев, Кадушко BY_2014_2_3. Дороги (184 / 12) Горбатовский Лосев

Текущее состояние в дорешивании воскресных олимпиад (50 задач к дорешиванию)

Решено
Костяной 49 Попович 49 Лосев 34 Ситников 33 Горбатовский 19 Харрасов 6

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

Мой профиль

28-29.05.2020

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

Тренировка COCI

Вот первые впечатления о задачах:
1) просто изик, совсем изик. Написал как только прочитал за 1-2 минуты;
2) тоже изик;
3) подозреваю, что изик, но в голову сходу ничего не пришло, потом пришла идея про середины;
4) сразу же идея про meet-in-the-middle;
5) частный случай задачи с открытки этого года. Помнил, что там как-то к проверке графа на двудольность сводилось;
6) Сразу же придумалось ДО с хранением преф/суф gcd;

Так как 1-ую я уже сдал, то пошел писать 2-ую и оч быстро с этим справился. Про 3-ю начал думать, додумал до середин, но сходу не придумал, как считать тех, кто испортится после поворота, поэтому решил временно оставить. Пошел писать 4-ую. Я писал ее до сдачи на oj целый час!!! Думаю, что я слишком расслабленно решал. Нужно настраиваться на контест, а не просто на "дорешку", где можно решать почти в свободном темпе (хотя я стараюсь обычно как можно быстрее). И я думаю, что из-за этого я и не успел закрыть контест. Но вернемся к контесту. И так, спустя час, я сдал 4-ую на oj, но на DL мне выдало только 96 +- и я даже не знал вердикта. Решил оставить на время и перешел к 6-ой. Сдал ее за +- 1 час 20 минут, что терпимо, но нужно быстрее (опять-таки, я думаю, что был слишком расслаблен). После этого решил вернуться к 3-ей. Додума идею и через +- 20 минут сдал ее. Оставалась странная ошибка в 4-ой и 5-ая. Решил добить 4-ую, так как на это нужно было не много времени. И за 10 минут получил полный балл на DL. Оставалась 5-ая. Написал подгруппу, чтобы проверить, правильно ли я понял условие. Она зашла, так что я начал думать. У меня оставался +- час. Через какое-то время я решил просто написать одну штуку, которую рассчитывал использовать в полном решении, так как в голову вообще ничего не шло. Когда я ее дописал оставалось 30 минут до конца. Через 10 минут я все-таки родил полную идею, оставалось 20 минут, но я начал очень быстро печатать. Не знаю как, но за 18 минут я дописал, но, к сожалению, где-то набагал, поэтому не успел получить полный балл.

И так, я уже несколько раз сказал и еще раз повторю, что я был очень расслаблен. Не знаю почему, но мне казалось, что контест будет простым и нет смысла напрягаться. И это сыграло злую шутку. Так уже было на области 2020, когда я получил относительно быстро 328 баллов и решил, что этого хватит.

Что касается 5-ой задаче, то в дорешке я нашел небольшую ошибку в идее которую смог исправить и добил свое решение до полного балла. Но я подозревал, что слишком сильно все усложнил и так и оказалось. Спросил решение Антона (оно похоже на автороское) и там была красивая идея с раскраской графа. Ее я тоже дорешал. Почему я не написал это, хотя знал, что там раскраска графа? Если честно - не знаю. Я думал над раскраской, но на контесте ничего в голову не пришло.

Educational round #88

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

Ну и дорешал еще одну задачу на пересечение матроидов (https://www.urionlinejudge.com.br/judge/en/problems/view/2128), эта более простая по сравнению с теми, которые я уже решал, но все равно неплохо было попрактиковаться в графах.

Мой профиль

30-31.05.2020

И так, вот то, что я успел сделать за 2 дня.

Codechef May Lunchtime 2020.

На контест опоздал на 20 минут, так как узнал о нем очень поздно. Это мой первый рейт контест на codechef. Формат был наподобие IOI-style. И так, сам контест.

Первые задачи 2 просто изики, быстро сдал. Над 3-ей немного подумал и тоже сдал. 4-ая сразу показалась оч сложной, потом заметил, что числа маленькие и придумался принцип Дирихле, так что ее я тоже относительно быстро сдал. И так, оставалась последняя 5-ая задача. Вот тут было поинтереснее. Сразу же придумалась идея, про группы по 2, попытался ее реализовать на частичный балл, получил WA. Искал ошибки, а потом осознал, что можно еще группировать по 3, и что можно написать ДП за O(n^2) на частичный и O(3*n) на фулл. Написал частичное для начала (от полного решения отличается одним символом), отправил - WA. Я абсолютно не понимал, в чем проблема. Пытался по всякому выкрутиться и только под конец контеста увидел баг, что у меня при обработке частного случая не стоит continue. Оч быстро это исправил, отправил - фулл. Таким образом я закрыл контест и стал топ-6 по итогу (так как среди всех, кто закрыл, я был последним).

А теперь перейдем к проблеме, из-за которой я чуть не лишился задачи. Я не проверил частный случай (я его написал в коде, но не проверил тестом). Думаю, что это хороший урок больше не допускать такой ошибки.

Так в принципе доволен 1-ым раундом. Конечно, это только Div-2, но если буду так продолжать, то и в Div-1 спокойно смогу удержаться минимум в мастерах.

Кроме того начал дорешивать задачи с этого же раунда, тольк Div-1 (как и на CF, задачи в основном похожи). Одну придумал и дорешал сам. Еще одну начал разбирать и, вроде как, сегодня уже разобрал. Довольно интересная задача на интерполяцию Лагранжа и еще несколько красивых идей было. В ближайшее время постараюсь дорешать.

Тренировка COCI_2017_R3

Первые впечатления о задачах:
1) изик, сразу написал;
2) изик, сразу написал;
3) какое-то ДП;
4) баянистая задача, были похожие на BOI и на отборе MWJ;
5) нужно будет поисследовать;
6) какая-то математика.

Так как первые две я написал, то я решил немного подумать. На 3-ю придумал ДП за 4-ую степень. Решил пока не писать, а сдать 4-ую. +- через час от начала я с этим справился. Решил пока что не ломиться и еще подумать. На всякий случай перечитал условия задач. В 3-ей не было особых продвижений, а в 5-ой придумал что-то за куб. Решил проверить и получил 42 балла. Еще немного подумал над задачами и решил написать то, что есть в 3-ей. Закончил писать я где-то к середине контеста, отправил - 5 баллов (должно быть 50). Я воевал с этой ошибкой где-то полчаса, пока не понял, что неправильно несколько переходов ДП реализовал. Исправил - 50 баллов. Еще через 10 минут добил до 70. Теперь я уже ушел думать очень на долго. Начал разбирать сэмплы в 5-ой, искать закономерности. О 6-ой тоже не забывал и сделал замечание, как можно узнать некоторые элементы. Потом я осознал, что таким образом узнаю не некоторые, а все элементы и тогда уже я написал частичное на 64 балла. У меня оставалось +- 30 минут и я решил переключиться на 5-ую. Понял, что неправильно разобрал сэмпл. Понял, что нашел закономерность, сдал частичное на 70 баллов. После этого я до конца контеста никаких баллов не набрал.

Еще на контесте я успел придумать фулл по 5-ой, но не успел его реализовать. В дорешке досдал свою идею. На контесте не успел потому, что неправильно разобрал сэмпл. Думаю, что если бы я это заметил раньше, то успел бы сдать на контесте. Конечно, от всех ошибок нельзя уберечься, но конкретно от этой можно было. Я решил посчитать xor-сумму руками. Можно было это сделать например с помощью калькулятора или код написать. Это не заняло бы много времени, но я бы не потратил столько времени впустую на поиск ошибки.

Кроме того дорешал 3-ю COCI на 100. В обсуждении на CF прочитал только "BFS" и сразу в голову пришла идея, как оптимайзнуть мое ДП на фулл.

Мой профиль

1 июня

Долги по теории

 Решить и описать решения                                                                   

 2012_1_3. Цифровая строка            ( 2 / 976)   Костяной 
 2010_1_4. Видео сервис               (16 / 215)   Ситников                  
 2017_2_2. Новый факультатив          (17 /  61)   Горбатовский

Текущее состояние в теории (Задано 26 задач)
... дорешать все задачи – до 17 июня.

Решено

             Задачи    ДП 1     ДП 2    Графы   BY_2020
Костяной       19        4        2       6        7
Лосев          18        5        3       4        6
Ситников       14        4        1       4        5
Харрасов       13(+1)    5        2                5
Попович        12(+2)    6                2        2 
Горбатовский   12(+3)    3        0       3        3

Текущее состояние в дорешивании воскресных олимпиад (62 задачи к дорешиванию)

Решено

Костяной      60
Попович       54
Ситников      42
Лосев         40
Горбатовский  25
Харрасов       6

Мой профиль

1-3.06.2020

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

И так, дорешка:
1)https://www.codechef.com/LTIME84A/problems/GCDMASK, интересная задача. Во-первых интересное замечание про ф-цию G. Во-вторых св-во, что степенная сумма (степень p) может быть представлена как многочлен степени p + 1, а значит если мы знаем значения в p + 2 точках, то мы можем восстановить многочлен с помощью интерполяции Лагранжа. Это св-во в принципе оч интересное, потому что можно будет в некоторых случаях не выводить формулу, а лишь вычислить значения несколько точек и подставить в формулу интерполяции Лагранжа. Короче, оч интересная задача;
2)https://oj.uz/problem/view/COCI17_sazetak, 6-ая задача с воскресной тренировки COCI. На нее не было авторского разбора, но я догадывался, что там включения-исключения. Потом посмотрел код Benq, он зачем-то использовал обратное по модулю. Сразу я не догадался зачем, а потом все сложилось и остальное я сам додумал.

Теперь сегодняшняя тренировка. Мы писали COCI_2017_R4.

Первые впечатления о задачах:
1) изик;
2) изик, потом еще оказалось, что можно маски сдавать;
3) чет более интересное, подозревал, что изик;
4) ДП по теории игр, вроде ничего необычного;
5) сразу в голову пришел трих;
6) Очень напомнила 2_3 респы этого года (об этом чуть позже).

Начал сдавать изики. Сдал первую, еще через минут 8 вторую. Потом над третей немного подумал и написал фулл. Написал минут за 15, отправляю - RE. Не мог понять, в чем дело, потом решил перечитать условие. Не знаю почему, но ограничения на M были так написаны, что три дополнительных нуля было на следующей строке. И я этого не заметил. Немного подумал и через минут 7 сдал на 100. Потом решил проверить идею с трихом на 5-ую. Получил свои 50% и решил разобраться с 4-ой. Вот тут было все очень плохо. Решил проверить брут. Через минут 20 получил свои 72 балла. Потом я решил, что n ^ 2 log зайдет. И начал исправлять свое решение. На это потребовалось минут 40, так как я очень долго искал баг. И, печальны результат - TL. И столько же баллов, как и за брут. Еще минут 10 я пытался что-то ускорить, но все безуспешно. Я решил, что нужно просто другое решение, сел и минут за 10 придумал n^2 и через минут 15 сдал его. После этого я немного подумал над 5-ой и 6-ой, решил написать частичное на 6-ую. После этого еще немного подумал и придумал полное по 5-ой, но с большой константой. Уже наученный опытом 4-ой задачи, я решил еще подумать. И придумал решение с более коротким кодом, меньшей константой и памятью. Писал и дебажил минут 30 и сдал с первой попытки. Остальное время пытался придумать на 6-ую что-нибудь, но так как я еще нормально не разбирал 2_3 респы, то ничего не придумал.

Самая главная ошибка была в том, что я долго решал 4-ую. Я сразу предполагал, что решение ненадежное, но пошел писать его. Не знаю, куда я спешил. Как я уже и говорил, нужно было поставить рамки, что если до такого-то момента не придумаю, то напишу то, что есть. И на примере 5-ой задачи видно, что такая стратегия действительно выигрышная.

По поводу 6-ой задачи. В обсуждении на CF было сказано, что она похожа на эту задачу https://oj.uz/problem/view/balkan11_timeismoney (на нее есть разбор, так что я надеюсь, что смогу ее дорешать). Я спросил у ребят, которые готовили задачу на респу и оказалось, что этой задачей они вдохновились, когда придумывали 2_3.

Мой профиль

04.06.2020

Сегодня разбирался с timeismoney и решал раунд на CF.

Сначала по поводу timeismoney. Я уже начал многое понимать, например почему точки лежат на гиперболе и почему они должны быть на выпуклой оболочке. Но еще некоторые моменты нужно обдумать. Думаю, что скоро совсем ее добью.

Теперь раунд.

Начал неплохо. Сдал A за 8 минут, потом очень быстро сдал B еще за 15 минут. Прочитал C, сразу пришла в голову идея перебирать ответ, но больше ничего пока что не придумал. Прочитал D и решил, что нужно вернуться к C. Решил разобрать сэмплы, но это не особо помогло. Потом стал думать, что мне даст перебор ответа. Пришла в голову идея про последние биты. Потом понял, что мы рядом ставим только одинаковых, а значит задача свелась к задаче о доминошках, которая решается с помощью Эйлерова цикла. Я все это придумал +- к 45-ой минуте и сразу же начал печатать. Пока я все написал и отдебажил прошло примерно 50 минут. Отправил - WA 12. Я понимал, что в идее ошибки нет и стал искать баги в коде. За минут 5 нашел ошибку, исправил - AC. Остальное время я пытался что-нибудь придумать на D,E, но ничего толкового в голову не пришло.

В принципе контестом доволен, это мой первый топ-100 результат в Div 1, еще и международного мастера поднял. Но, правда, не доволен, что так долго писал C.

Мой профиль

5-7.06.2020

В эти дни в основном решал codechef long challenge (задачи еще не могу обсуждать, так как он не закончился). Сдал все задачи кроме открытых тестов и задачи на странную дихотомию. Но еще почти неделя, постараюсь их добить.

Теперь тренировка COCI_2017_R5

Впечатления о задачах:
1) изик, сразу написал
2) изик, не хочется сразу писать;
3) изик, сразу написал
4) жадос какой-нибудь
5) сразу же в голову пришел параллельный дих;
6) что-то интересно на двудольном графе.

1-ую и 3-ю я сдал в первые минут 18 +-. Потом я дочитал все задачи и немного отшлифовав идею на 5-ую сдал ее чуть позже, чем через час от начала. Потом решил проверить жадос на 4-ую за квадрат. Он зашел, поэтому я стал чуть глубже думать 4-ую, а потом решил, что лучше сдам 2-ую. Справился с этим я через +- 2 часа от начала. Еще немного подумал над 4-ой, додумал в ней дих и еще через 30 минут сдал 4-ую. Оставалась только 6-ая. Я пытался как-то использовать то, что у нас двудольный граф. Например то, что циклы только четной длины. Еще думал о парсоче и связанных с ним задачах. Но за часа 1,5 раздумий ничего хорошего в голову не пришло. Поэтому я решил написать легкие подгруппы на 50% и справился с этим за минут 30 +-. После этого до конца контеста никаких продвижений в баллах у меня не было.

После контеста я как обычно стал искать обсуждения на CF. На этот раз мне повезло, так как bmerry написал разбор на все задачи, включая 6-ую (http://blog.brucemerry.org.za/2018/01/coci-20172018-r5-analysis.html вот ссылка на этот разбор). Все-таки в 6-ой оказался парсоч. Хорошо, что у меня были такие мысли, но плохо, что я не смог додумать до полного решения. Там была буквально одна идея до полного решения, но эта идея была очень нетривиальна.

Кроме того разобрал решение на задачу https://oj.uz/problem/view/balkan11_timeismoney. Написал полное (по-моему) решение, но оно почему-то берет 40/100. Но уже поздно, поэтому с этим разбираться я буду уже завтра.