[Logo] Форум DL
  [DL]  Back to home page 
Forum Index ->Олимпиадное программирование ->Методика подготовки к IOI 2007 - ... 1, 2, 3, ... 15, 16, 17
Author Message
Mihail Dolinskiy

Topics: 1805
Messages: 41821

My Profile


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

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

2) в задаче С не увидел задачу о нахождении эйлерова цикла. А точнее, я не знал, что в нем колво исходящих ребер равно колву входящих. А знал только про главное его свойство существования
 
Для цикла это очевидно. Надо научиться придумывать такое!

Прочитал А, подумал над формулами какими-то, которые +- однозначно должны были ответ восстановить, но нет.

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

Вернулся на А. Придумал жадное решение и словил WA. Немного подумал, почему это может быть неправильно, но безуспешно.

Переключился на С. Прочитал, написал бфс и словил WA, подумал, что надо еще два перехода добавить и получил АС.

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


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

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

а то потом не хватает времени и нервов на другие задачи

Aleksandr Losev

Topics: 30
Messages: 142

My Profile
Возвращение блудного попугая!

IOI2021 Day1:

Прочитал первую задачу, посмотрел на группы. Первые три придумались мгновенно. Над 4ой немного подумал. Идей не было, поэтому пошел читать другие задачи. На второй задаче такая же ситуация, но, в отличие от первой, тут даже намеков на дальнейшее развитие решения не было. В третьей сразу в голову пришел какой-то жадник, его нужно было проверить, но решил перейти обратно к А.

Немного подумал, как я буду все решение реализовывать, что и где должно храниться. Сел писать. Основная идея на третью задачу заключалась в классической структуре segment tree beats, которую я знал. Пока я искал ошибки на семплах, я вспомнил, что была задачка, где можно было применить облегченную segment tree beats, не храня кучи лишних элементов, а это можно было сделать из-за того, что у нас было очень много повторяющихся элементов в массиве из-за операций прибавления на отрезке. Перестроил свою структуру, отдебажил и получил на втором часу 38 баллов. Перешел к Вшке, за 20 минут взял 37 баллов(первые три группы). Перешел к Сшке, написал жадник - не прошло. К счастью, был запасной вариант в виде идеи через 2-SAT на все группы, кроме последней. Написал, получил 45 баллов и словил RE по какой-то причине(возможно из-за того, что там при существовании ответа надо было вывести и заретурнить 1, а мой солв мог просто заретурнить 0 из-за несуществования ответа). Немного подумал, поставил побольше ограничения, проанализировал код - и ничего не помогло. Стоял вопрос: подумать над А или остаться на С? Группа на А стоила 29 баллов, одна группа на С стоила 10 баллов, а следующая, в которой я не был на 100% уверен, что она пройдет. Подумал, что лучше перейти на А, так как там есть куда развиваться. За минут 20 придумал решение. Еще минут 20 подумал, как его буду реализовывать. Пока писал второе ДО, я задумался, а зачем оно мне? Ведь когда я сказал факт, что суммарно элементов я обработаю не более n, то я могу и в лоб проходиться вместо поддержки ДО со спуском и массовым присваиванием. Написал решение, суммарно со всеми подгруппами было строк 350, не менее. Заслал и словил TL. Написал стрессы. Вроде все работало. Чуть позже оказалось, что я в стрессах потерял минут, из-за чего не та группа, которая надо, запускалась. Осталось полчаса, а я уже словил WA. Пошел стрессить дальше, попутно находя WA тесты и исправляя баги. Так до конца контеста и не отдебажил решение на 67 баллов на А.

Почему не хватило времени? Когда придумал ST beats, я не подумал о том, можно ли здесь использовать упрощенную версию. Но тут же стоит другой вопрос. Доказал бы я, что упрощенная версия зашла бы по TL? Ведь ST beats сам(и его упрощенные версии) доказываются через то, чего я не знаю. Проверить это можно было через AC на группе или TL. Тем самым я потратил лишние 30 минут на то, как правильно реализовать полную версию ST beats. Чуть позже на той же задаче я потратил около 10-15 минут на ненужную мне ДОшку. Итого потратил лишних 40-45 минут на бесполезные вещи, чего как раз и не хватило для дебага. Когда пришел домой, я за минут 20 смог застрессить все баги в решении и их исправить. Возможно, если бы я отдебажил А на 67, то и смог бы отдебажить С на 55-70 баллов.

Оказалось, что в С у меня RE выдавал assert, про который я забыл. В итоге решение без него и с двумя новыми строчками взяло 55 баллов.

Итого: 38 + 37 + 45 = 120 (еще 39 баллов добил после контеста)

Когда продумываю реализацию идеи, то стоит задаться вопросом "а надо ли мне эта штука вообще в решении? Может и без нее будет все хорошо? Почему?"

На досуге:

1) https://codeforces.com/gym/103652/problem/F красивая идея через оптимизацию брута с помощью неочевидных битсетов, до которых нужно дойти через исследование функции ДП
2) https://codeforces.com/gym/103652/problem/J собираюсь ее сдать авторским разбором через Lyndon tree, про который я впервые услышал.
Aleksandr Losev

Topics: 30
Messages: 142

My Profile
15.05.2022 олимпиада ФПМИ БГУ:

Медленно закодил А, хоть она была одной из самых простых задач. Тем временем уже сдавались другие задачи. Быстро написал B, посмотрел в таблицу - сдали E. Перешел на Е, перечитал раза 2 условие и быстро закодил/сдал. Перешел к С, посмотрел внимательней ограничения, написал перебор - сдал. В это время ничего не сдавали, поэтому решил читать все остальные задачи по порядку. На D было понятно, что нужно какой-то жадос придумать - пропустил. F какая-то математика - пропустил. G уже была похожа на ДО, немного подумал - сделал пометки и перешел читать H. В H я написал перебор для обратной задачи, заметил важную деталь, что всего плохих троек не очень много, где их хранить и отвечать на вопросы придумать не смог. Сдали G, поэтому перешел на нее. Придумал что-то в роде разделяйки, выписал несколько условий и вывел итоговую идею решения. Написал + отдебажил семплы и словил WA. Искал ошибку в разделяйке с ДОшкой, но никак ничего не нашлось. Перечитал условие и оказалось, я не так сортил в сете элементы. Оставалось 2 часа и уже много людей сдало F. Я начал думать над ней, написал брут и анализировал поведение ответов. Пытался найти закономерность с использованием степеней двоек, но все ловило WA. На последнем часу нашел решение, которое работало для n <= 50, но оно упало по WA, но дальше, чем в прошлые разы. В последние 5 минут я осознал, что были еще и другие задачи0 в которых были пометки. Перешел на D. Придумал очевидный жадник, но не успел написать.

Ошибки:

Надо было чаще переключаться между задачами и не оценивать сложность задачи по таблице. Если бы не трогал F, то сдал бы как минимум D и мог бы додумать H.

IOI 2021 Day2:

Прочитал А и придумал очевидное жадное решение. Написал и получил 56 баллов. Относительно быстро нашел тест, на котором падает. Немного добавил в код новых фич и зашло на фулл.
Прочитал В. Цель была взять 62 балла на нее. Придумал бинарные подъемы на 1, 3 и 4ую группы. Думал над решением на вторую группу. Пытался что-то придумать с намеком на полное решение, но ничего не выходило, поэтому решил написать решение на те три группы и подумал, что вдруг там я что-то не доказал и мое решение должно туда зайти. Написал, получил 50 баллов, зашла 2ая группа, но не 4ая. Изначально менял высоту подъемов, но не прокатывало(суммарно меньше 2 минут заняло, это не особо критично было, тк просто меня ограничения). Написал пару ассертов, которые помогли мне понять, где именно и почему у меня TL. Смог придумать тест, который легко ломает мое решение. Также придумал костыль для обхода этого случая. Написал и словил все равно TL. Мне нужно было как-то избежать обхода цикла длиной в ~1е6. Написал проверку, которая смотрит, нахожусь ли я в этом цикле или нет, написал прыжок мимо все полные повторы цикла. Не сработало. Значит ошибка была в том, что я неверно считаю прыжок. Дальше ничего в голову не приходило, поэтому я переключился на С.
Тут задача чисто коструктивная, поэтому пришлось вспомнить пару свойств битовых операций и перебирать варианты решения ручками. Где-то за 15 минут до конца смог отдебажить решение на 21 балл. Добил еще 12 баллов, тк там просто цикл добавить и поменять запросы местами.

Итого: 100 + 50 + 33

Если бы не тратил время на Bшке на 4ую группу, то смог бы добить еще 13 баллов на С, где нужно было додумать поиск максимума двух чисел и написать любую сортировку элементов. А в целом, остальное пошло по плану. Набрал по каждой задаче среднее колво баллов.

За все два дня: 120 + 183 = 303 = серебро

Что дорешивать:

1) полностью первый день. Идею на 1_3 я знаю, осталось ее реализовать
2) 2_2 интересная задача, какой-то прием может не знаю. Или что-то идейное надо было сделать
3) 2_3 просто почитаю идею, задача точно не из тех, которую стоит реализовывать.
 
Forum Index ->Олимпиадное программирование ->Методика подготовки к IOI 2007 - ... 1, 2, 3, ... 15, 16, 17
Time:0,188