[Logo] Форум DL
  [DL]  На главную страницу 
Индекс форума ->Олимпиадное программирование ->Методика подготовки к IOI 2007 - ... 1, 2, 3, ... 11, 12, 13, 14, 15, 16, 17, 18
Автор Сообщение
Слава Ермаков

Темы: 1
Сообщений: 12

Мой профиль
3 марта
1 - 100
2 - 100
3 - 100
4 - 14
Все так и писал
Дорешать 4 на 100

23 ферваля
1 - 100
2 - 100
3 - 37 (так и хотел)
4 - 1 (должно 38)
Глупая ошибка - количество битов числа записал в n, а она была глобальной переменной и затерлась
Ошибкой было не тестировать - даже если бы сделал два теста нашел бы проблему



[MD]А тебе надо это дорешать?


Андрей Костяной:

Дорешать из COCI:
11_COCI_5: 6 (СНМ | tournament tree);
11_COCI_4: 6 (ДП, теория игр);
10_COCI_3: 6 (геометрия, принцип включения-исключения);
10_COCI_2: 6 (ДП, принцип включения-исключения);
10_COCI_1: 6 (теория чисел);
12_COCI_5: 5 (ДП);
11_COCI_2: 5 (ДП на графе);
11_COCI_1: 6 (ЭТЧ: битовая обработка, простые);
 


17 февраля Питерская вторая
1 - 91
Сначала начал писать рекурсию, боялся что не учту какие-то случаи но оказалось долго писать (для 1 задачи), в итогу написал формулы и что-то не учел. Надо потратить 5 минут и спокойно подумать что писать.
2 - 100
3 - 21(должно 100)
Думал что в матрице только буквы А и В
(Нужно читать вдумчиво все условие включая формат ввода)
4 - 50(должно 100)
Ошибка в реализации
Надо было придумать более хитрые тесты(или писать брут)

10 февраля Питерская первая
все на 100
Владислав Бортенко

Темы: 0
Сообщений: 2

Мой профиль
19_SPb (Ru_Reg)(Day 2) (03.03.2019)
5)Неисправный марсоход - Планировал (100 из 100). Взял 54
Ошибки: Медленный алгоритм
Дорешал на полный балл
6)Интервальные тренировки - Планировал (40 из 100). Взял 7
Ошибки: Неверная идея
7)Экспедиция - Планировал (20 из 100). Взял 8
Ошибки: Неверная идея.
8)Разбиение на пары - ничего не придумал

19_SPb (Ru_Reg) (27.02.2019)
1)Два измерения(100)
2)Полные квадраты - Планировал (50 из 100). Взял 19.
Ошибки: Неверная реализация
Дорешал на полный балл
3)Автоматизация склада - Планировал (10 из 100). Взял 1
Ошибки: Неверная идея
Дорешал на 32 балла
4)Машинное обучение - ничего не придумал

19_Rui2 (17.02.2019)
A)Дела по Дому - Взял 100, как и планировал
B)Возращение Домой - Планировал(85 из 100). Взял 75.
Ошибки: Медленное решение.
Дорешал на полный балл.
C)Прогулка по Бруклину - Планировал (20 из 100). Взял 14.
Ошибки: Неверная идея
D)Взлом компьютера - ничего не придумал

19_Rui1 (10.02.2019)
A)Поиск Трезубца - Планировал (100 из 100). Взял 36.
Ошибки - Неверная идея
Дорешал на полный балл

B)Атакующие Пары - Планировал (70 из 100). Взял 16.
Ошибки - Неверная реализация
Дорешал на 55 баллов

C)Минное поле - Планировал (50 из 100). Взял 0.
Ошибки - Неверная реализация.
Дорешал на 65 баллов

D)Оптимальное построение - ничего не придумал
Женя Хамиченок

Темы: 0
Сообщений: 4

Мой профиль
19_Rui3, day 1
1. 100
2. 44 не придумал идею
3. 44 не придумал идею
Дорешать:
2. 100



19_SPb, day 2
1. 83 не прошли некоторые тесты по времени, я знал что не пройдут
2. 45 не придумал идею, написал рекурсию
Дорешать :
1. 100




19_SPb, day 1
1. 57 примерно на столько и хотел написать
2. 45 примерно на столько и хотел написать
3. 32 примерно на столько и хотел написать
Дорешать:
1. 100
2. 100
Михаил Долинский

Темы: 1982
Сообщений: 47183

Мой профиль
Писать всё в одном СВОЁМ сообщении - в верх сообщения.
Переходим на него по ссылке со своей фамилии
если она уже есть, иначе делаем новое ОДНО сообщение


Записи у каждого получатся в порядке, обратном хронологическому.
Так удобнее и писать, и читать.

11 кл: Ермаков Бирич
10 кл: Козлов, Радченко, Хамиченок, Сачковский, Кузьменко, Свиридков, Паращенко
9 кл: Костяной, Харрасов, Ситников, Великович, Коротков, Морозов, Лютиков, Либуркин
8 кл: Лосев, Попович, Бортенко, Головешкина
6 кл: Горбатовский

Писать
дату, название олимпиады

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

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

Темы: 30
Сообщений: 143

Мой профиль
Начну новый сезон "ошибок, которые мы совершаем"
22.11.2021 - писал Educational Round 117
А - сдал быстро, проблем не испытывал

В - идея, конечно же, придумал мгновенно, начал писал солв, когда дописал слетели семплы. Тк по неизвестным мне причинам дебаггер решил отказать в работе, пришлось дебажить глазами. В итоге оказалось, что не учел один случай, когда неюзнутые элементы надо было распределить по всему массиву. Заслал - словил WA. Бага была в том, что перебирал неюзнутые переменные на отрезке (min(a, b); max(a, b)), а надо было на (a; b) (a не обязательно меньше b)

C - придумал сразу, проблем не испытывал

D - после прочтения написал рекурсию с максимальной контстантной глубиной. Заслал и словил WA3, увеличил макс глубину рекурсии - словил TL4. Понял, что идея неверная и быстро придумал правильную через алгоритм Евклида

E - сначала прочитал условие и испугался фразы "Монокарп хочет максимизировать математическое ожидание количества студентов, которые прочитают необходимые им сообщения", тк такого я раньше впринципе не встречал и пошел читать другие задачи. Прочитав F и G, мне больше симпатизировала G, но 10 минут мне хватило для того, чтобы понять, что она сложная и впринциипе не было никаких наметок на идею решения, поэтому вернулся к Е. Для начала я посчитал матожидание для семплов, после чего понял, как впринципе оно считается для любых тестов. Доказав, что длина ответа не превышает 20(в условии сказано, что челик читает максимум 20 рандомных сообщений). Там функция будет убывать на всем отрезке (20; 2e5]. Изходя из этого быстро придумал решение и сдал задачу.

Оставалось 30 минут контеста и я решил подумать над F. В итоге было несколько наметок на идею решения. Сегодня ее допридумал и дорешал

В итоге получил +31 рейта, в следствие чего вернул себе желтого
Александр Лосев

Темы: 30
Сообщений: 143

Мой профиль
27.11-28.11 IATI2021

Day1:
Изначально прочитал все задачи и больше симпатизировала Сшка. Минут за 10 придумал обработку первого запроса, потом еще минут за 10 придумал обработку второго запроса на корень на лог (изначально я думал, что это будет фулл, но потом оказалось, что нет). Быстро закодил обработку первого запроса, заработала с первого раза. Потом минут за 30 закодил обработку второго запроса и семплы заработали. Заслал и словил WA на всех группах, даже на той, где не было запросов первого типа, а значит я неверно считал ответ. Искал ошибки в фенвике и неявной ДОшке, но там багов не видел, потом пытался сделать тесты, которые как-то сломают мое решение, но все безуспешно. Методом "исключения" кода минут за 30 я нашел очень глупый баг. А баг заключался в том, что я массив веторов пар vc[i] использовал как набор вершин на глубине i, отсортиванных по времени входа, а также я его использовал как набор запросов первого типа для вершины i. В следствие чего запросы и вершины слились в один вектор и неверно обрабатывали запросы первого типа, а также потом неверно считали ответ. Исправив баг я заслал код и словил TL на последней группе(остальные все зашли). Я начал задавать себе вопрос:"точно ли разделение k на "меньше корня от n" и на "больше корня" работает за корень на лог?". В голову быстро пришел тест, где у меня идет цепочка длиной корень от n и потом от одной вершины отходят остальные ребра. Этот случай уже работал за линию на лог. Быстро придумав оптимайз, я сдал задачу. Оптимайз заключался в том, что я не разделял k на два случая, и использовал соптимайзженный случай с k<sqrt(n)
Прошла половина контеста, а у меня было 0 + 0 + 100. Пошел думать над Ашкой. Быстро сдал на 8 баллов обычный Ним(первая группа была равна игре Ним). Потом минут за 30-50 придумал вторую группу(11 баллов), немного похожую на Ним, но с изменениями. Пошел думать над Б. Пытался придумать группу на 18 баллов каким-нибудь жадником, пришла в голову одна идея, но не доказав ее я сразу пошел кодить. Минут за 10 закодил и заслал, получив свои 0 баллов и WA впридачу. После этого я понял, что идея плохая и в голове вертелся тест, который у меня слетал. До конца контеста я не смог ничего придумать, кроме брута на Б, который я не успел закодить до конца контеста.

Итог: 19 + 0 + 100 = 119

A - Теория Шпрага-Гранди
B - жадник, структуры, деревья
С - структуры, деревья, offline-обработка запросов

Day2:
Прочитав А я заслал код, который я думал, что возьмет фулл, но взял ~20 баллов. Я начал перечитывать условие и пытался понять, почему это не фулл. Как оказалось, я не посмотрел на формулу подсчета баллов и там надо было минимизировать длину подсказки, которую мы генерировали с помощью первого метода. На этом я начал думать, что за темы могут быть в задаче и пришла в голову только одна мысль. С помощью подсказки вернуть битовое представление длины НОП(наибольшая общая подпоследовательность) двух последовательностей(все три множества нам передавали в аргументы первого метода) и потом, исходя из размерности этой длины, я поделил на два случая, где len<sqrt(n) и len>sqrt(n). Первый случай решался через ДП f[i][len] - минимальный индекс во втором массиве для НОП длины len. А вот над вторым случаем я думал, что в среднем раз в корень элементов будет встречаться ответ. Поэтому написал ДП f[i][j] - макс длина НОП, где i обработанных элементов в первом массива и j во втором, при этом разница между i и j не более корня. Закодив и отдебажив минут за 30-50, я заслал этот солв и словил WA на всех тестах. Чуть позже я напоролся на ту же проблему, что и в первый день, второй случай утверждал, что В СРЕДНЕМ встречается раз в корень элементов. То есть может быть так, что у меня в начале первого массива куча рандомных элементов, а потом идут элементы НОП. Как это исправить я уже не знал и переключился на другие задачи
B я скипнул, никаких мыслей не было. С показалась самой простой из трех данных. Придумал какую-то идею, которую я не смог оценить по размеру ответа(баллы давались за длину ответа, а также правильный ли он вообще). Написал минут за 20 и словил суммарно около 28 баллов, что очень мало(каждый из тестов давал по ~0,5 балла, всего тестов 50). К началу четвертого часа я начал набирать баллы за тесты, информацию о которых дали в условии, в Сшке. Минут за 30-40 я их всех разобрал и в итоге за С словил ~38 баллов(28 за "группы" и 10 набрали остальные).
Дальше решил набрать хотя бы две группы на В. Быстро свел задачу к покрытию графа минимальным количеством ребернонепересекающихся путей, которые решались через максимальное паросочетание. Быстро написал и словил 25 баллов за первую группу, но вторая не зашла(там ограничения стояли n <= 10^4, но TL было около 0,2 сек, из-за чего квадрат и не зашел). Потом быстро закодил брут на А, который зафуллил первую группу
В последнем часу я думал над Сшкой, в голове у меня вырисовывалась main idea, но я не смог оценить длину ответа этой идеи и сложно было закодить(я и до конца контеста так и не дописал идею).

Итог: 26 + 25 + 38 = ~89 баллов
А - Ad Hoc, возможно ДП
В - какое-нибудь ДП + структуры, тк там получается DAG и разбор случаев для неявного проведения ребер
С - чистый Ad Hoc
Михаил Долинский

Темы: 1982
Сообщений: 47183

Мой профиль
Здорово, что так подробно всё описал.
Это хорошая пища для размышлений.
Но не хватает выводов

1. Что нужно было делать по-другому в каждый из дней для получения более высокого результата
2. Какой обобщённый опыт извлёк – для применения в будущих личных контестах
3. На чём основывается твоя уверенность, что ты мог взять золото на этом контесте?

И надо, наконец, написать явную тактику решения личных контестов.
Которую нужно будет модифицировать по мере накопления опыта.
Александр Лосев

Темы: 30
Сообщений: 143

Мой профиль
1. ответ в пункте 2
2. Когда я вывожу какой-то факт в задаче, надо обязательно его доказать либо существованием контр-теста, либо математическим доказательством.
3. На данном контесте не было такого рода задач(отдельная группа = отдельная задача), которые я не решал ранее

За последние 3 года контестов с фидбеком и группами у меня вырисовалась тактика:
1) Читаю все задачи
2) Расставляю потенциальную сложность для каждой из задач
3) Иду по списку из пункта 2 и пытаюсь минут за 10-20 придумать фулл решение:
  а) если фулл не придумалось, то просматриваю группы и их ограничивения
  б) расставляю потенциальную сложность для каждой из групп
  в) решаю группы от легкой к сложной(возможны исключения из-за количества баллов за группу и потенциальной сложностью написания кода для группы)
  г) если минут за 20 группа не придумалась, то переключаюсь на другую задачу
4) Метод придумывания идеи задачи:
  а) что нам известно?
  б) что мы можем получить из того, что нам известно? И что надо для этого сделать?
  в) пункт а и пункт б чередуются
  г) когда нашлась идея решения, то что из алгоритмов надо использовать, чтобы её довести до нужных нам ограничений


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

Темы: 1982
Сообщений: 47183

Мой профиль


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

4) Метод придумывания идеи задачи:
а) что нам известно?
б) что мы можем получить из того, что нам известно? И что надо для этого сделать?
в) пункт а и пункт б чередуются 

Здорово, что есть такой пункт в плане.
Я бы добавил

- что нам нужно найти?
- что нужно знать, чтобы это найти?

То есть, получается своего рода "meet-in-the-middle", то есть
идти как от исходных данных к результату,
так и от результата к исходным данным.


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

На данном контесте не было такого рода задач(отдельная группа = отдельная задача), которые я не решал ранее  
Это очень здорово. Наверно сильно помогла работа, которую ты придумал и реализовал со сложными Codeforces задачами. Значит именно её и надо активно продолжать в поиске новых проблем и идей, и отработке навыков написания и отладки сложных задач (класса IOI), я так понимаю на темы:
- сложное ДП
- сложные структуры данных
- графы
- элементы теории чисел
- конструктивные
и их комбинации

Что касается личных контестов для индивидуального спортивного прорешивания
(сверх того, что мы будем решать на сборах и по воскресеньям),
предлагаю начать с IOI 2021, 2020, 2019 ...
на каждый день олимпиады свой 5-часовой подход, потом обязательно дорешивание
- в идеале на 600
- как минимум - на золото(серебро/бронзу - на что нацеливаешься?)

Можно и нужно пользоваться форумом
Описания решений задач IOI 2010 - ...
Читать, что там уже описано и
Писать, то что не описано.
Александр Лосев

Темы: 30
Сообщений: 143

Мой профиль
13.12.2021-14.12.2021

Первый день:
С задачами АВС проблем не возникало, быстро их сдал. А вот с задачей D я сильно налажал
Почему я не сдал задачу D? Первый вариант решения был впринципе неверный, так как я в некоторых случаях полностью проходился по бору и сливал два мелких поддерева. То есть это был тест q = 10^5 и все запросы равны "and 2^20-2", то есть я доходил от корня до нижних вершин и там сливал, каждый раз проходя через 2^19 верхних элементов.
То есть на первой половине контеста у меня было неверное решение, после, я заметил этот тест и начал оптимайзить его. Заоптимайзив код, у меня эти варианты отсеклись. В этом случае я прошелся по высоте h, бит которой в операции and равен нулю, и по всем НЕУДАЛЕННЫМ элементам высоты h проходился и сливал поддеревья. но это тоже работало медленно, тк тест мог спрашивать одну и ту же высоту и работать за 2^h. Я это тоже заметил и начал делать так, как ребята, не заходить на ту высоту, которую мы сливали, так как там просто свапаются два указателя на ребра. И я до конца контеста не смог адаптировать свое решение со слиянием так, чтобы быстро свапало ребра.
Как оказалось, я мог не интерпретировать задачу как "при операции and необходимо слить два поддерева бита h, который равен нулю в x(число запроса and), и после свапать ребра", а как "при операции and просто перестроим бор в лоб, если хотя бы один бит мы раньше не выключали, а также, если бит мы раньше выключали и выключаем сейчас, то изменить значение в бите h ксора всех ранее операций xor на 0"
В итоге я себе усложнил жизнь из-за неверной интерпретации

Второй день:
Единственная проблема, с которой я столкнулся, так это неверное прочтение задачи В.
Я изначально прочитал как "между всеми парами перлов в ответе разница между их временами появления не более m". А оказалось, что было "между всеми парами перлов ОДНОГО множества в ответе разница между их временами появления не более m". Поэтому и сначала решение ловило 15 баллов и я переключился на написание D, так как думал, что лучше сначала сдам D, пока не забуду реализацию из своей головы, а потом вернусь к В
Михаил Долинский

Темы: 1982
Сообщений: 47183

Мой профиль
Я всё-таки не понял ответ на главный вопрос.
Что нужно делать в такой ситуации, чтобы ГАРАНТИРОВАННО сдать задачу (4-ая 1-го дня).
Какие выводы ты сделал?
Какие уроки извлёк?

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

Темы: 30
Сообщений: 143

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

Вот я и заметил в Dшке, что от правого поддерева проходит переливка в левое. Замечание-то верное, но я пошел писать код ТОЧНО не оценив сложность(по времени выполнения) идеи. Мне не стоило лезть на рожон и писать код. Надо было еще больше поисследовать в боре. Потратил бы больше времени на раздумья и исследование, тогда бы сдал.
Михаил Долинский

Темы: 1982
Сообщений: 47183

Мой профиль
И снова слишком общий и недостаточно конкретный ответ.
А как решать - уже можно идти писать или нужно продолжать думать и исследовать?


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

Темы: 30
Сообщений: 143

Мой профиль
Пока что для меня этот вопрос сложный
Думаю, что на тренировках надо экспериментировать над этим:
1) Либо когда я придумал идею, написать на бумаге псевдокод на эту идею и на каждом куске псевдокода смотреть, существует ли контртест по времени, который упадет на этом месте
2) Либо выделять определенное время на раздумье после придумывания идеи, параллельно задавая вопросы "а что может пойти не так?", "где может упасть идея?" и тп вопросы
Михаил Долинский

Темы: 1982
Сообщений: 47183

Мой профиль
Подумай и реши как конкретно ты будешь действовать на олимпиаде в четверг.
Так и делай, потом напиши, что получилось.
 
Индекс форума ->Олимпиадное программирование ->Методика подготовки к IOI 2007 - ... 1, 2, 3, ... 11, 12, 13, 14, 15, 16, 17, 18
Time:0,062