Форум DL

Мой профиль

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

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

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

Для цикла это очевидно. Надо научиться придумывать такое!

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

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

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

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

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

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

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

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

Мой профиль

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

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, про который я впервые услышал.

Мой профиль

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 просто почитаю идею, задача точно не из тех, которую стоит реализовывать.

Мой профиль

Прошла областная олимпиада 2024

На мой взгляд очень многие ребята из Гомеля выступили хуже, чем могли бы.

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

Мой профиль

Как решал олимпиаду:
1 день: Прочитал условия всех задач. Пошел писать первое придуманное решение на задачу А. Оно оказалось неверным, пришлось еще думать. После 45 минут раздумий, пошел набирать частичные баллы на B, С. С задачей B были какие-то проблемы. Мое решение выводило правильный ответ, компилятор выдавал обратное. Набрать на ней баллы у меня так и не получилось. На задачу С я тоже придумал рабочее на частичные баллы, однако я его написал так, что он летело по времени. Потом оказалось, что нужно было просто посчитать ответ заранее, так как там были подтесты. На задачу D вообще оказалось, что можно было написать жадник, но у меня его придумать не получилось, хотя жадник был не очень сложный. Под конец получилось набрать 37 баллов на А. Также на малое количество баллов повлияла растерянность.
2 день: Также прочитал условия. Задача А придумывалась моментально, сразу написал и решил. Позже набрал частичные баллы на B. Больше на этой задаче не получилось. На это я потратил 2,5 часа. Потом также набрал небольшие баллы на C. И оставшийся час пошел набирать баллы на D, которая была с открытыми тестами.
Какие ошибки совершил:
Растерялся после 3 часов в первый день. Расчитывал на то, что закрою задачу А за 50мин-1час. Во второй день до лучшего результата по моему мнению не хватило около 50 баллов. Не хватило практики.
Что и как нужно делать по другому на олимпиаде, чтобы лучше выступить:
Не опускать руки и чаще переключаться между задачами.
Что нужно изменить в подготовке, чтобы лучше выступать:
Больше заниматься.
-----------
Коновал Константин

Мой профиль

Как решал олимпиаду (по дням):
1 день : Прочитал условия ТОЛЬКО A и B. За первые 2 часа решил сконцентрироваться на задаче А.Решил написать перебор случаев, но у меня не получалось(слишком много надо было учитывать). Пытался написать B на первую подгруппу, но летело по TL.После этого опять начал сидеть над А и в итоге потратил, почти всё свое время (на оставшееся не успел понять и написать С).
2 день : Прочитал условия А. Решил её с помощью ДО но брало не все подгруппы. Переключился и написал неполный балл на B.
Также написал неполный балл на С.Потом понял в чём ошибка и сдал А. Оставшееся время придумал (1-1,5 часа) полное решение на В, однако ввиду кривой реализации она летела по TL. За 10 минут немного взял баллов на D(открытые тетсы).

Основными ошибками 1 дня я считаю сильную зацикленность на том, чтобы сдать задачу А(ввиду этого потерял непростительно много времени). Во 2 дне сильных ошибок я не совершал, однако считаю, что лучше бы я уделил больше времени D.

Мой профиль

День 1: Прочитал задачу А, потратил на неё более 1.5 часов и получилось только на 3 балла. пошёл дальше читать В, С и D. не смог набрать ни на одной из них баллов и оставшийся 1 час решал А, и в итоге сдал её только на 11 баллов.
День 2: Прочитал задачу А, придумал решение которое в теории должно было набрать около 60 - 70 баллов, но прошла на фулл. Прочитал задачу В, написал решение на 35 и пошёл дальше. Прочитал С, она была похожа на В, но у меня с ней были проблемы и я решил не повторять ошибку 1-ого дня и пошёл дальше. Почти всё оставшиеся время решал 3 теста из D и набрал 22 балла, последние 30 минут пытался исправить С.
Какие ошибки совершил:
День 1: Зациклился на задаче А.
День 2: Мог взять подтесты на В(чтобы набрать 50 баллов вместо 35) и не смог исправить решение на С.
Что и как нужно делать по другому на олимпиаде, чтобы лучше выступать:
Не совершать ошибок 1-ого дня, а то есть не зацикливаться на 1 задаче, и читать всё. Быстро переключаться между задачами.
Что нужно изменить в подготовке/тренировках, чтобы лучше выступать:
Больше заниматься.

Мой профиль

день 1:прочитал все условия и начал решать А потратил в итоге 3 часа потом начал решать D здал за час потом пошёл решать
В и нехватило 5 минут что здать на 100
день 2:прочитал условия и за 30 минут решил А и также за час здал В потом 2 часа думал на С но придумал только на 6 баллов и за последний час здал D на 15.66 баллов
Какие ошибки совершал:
слишком долго думал на одной задачей
Что и как нужно делать по другому на олимпиаде, чтобы лучше выступать:
Уметь сконцетрироватся
Что нужно изменить в подготовке/тренировках, чтобы лучше выступать:
Больше заниматся

Мой профиль

Как решал олимпиаду:
1 день: с самого начала сел над задачей А придумал правильное решение на 1ом часу, написал не заработало переключился на другое, только к 3му часу когда я все еще сидел над А я вспомнил про то решение написал отдебажил получил 100 баллов, оставшиеся 2 часа сидел над задачей Б в итоге мог получить еще минимум 70 баллов на С и Д, Д я пытался писать в моменте между А и Б получил 0 и забыл про Д
2 день: закрыл А за 25-30 минут потом собирал баллы, придумал решение на Б про префиксы и суффиксы но не осмелился кодить потому что не представлял как бы реализовывал, еще на Б мог написать группы на +25 баллов, я скорее забыл про Б и С и просто сидел над Д
Какие ошибки совершал:
очень плохо распределил время в первом туре и не написал фулл Б во втором
Что и как нужно делать по другому на олимпиаде, чтобы лучше выступать: сначала собрать частички а потом писать все фулы которые приходят в голову
Что нужно изменить в подготовке/тренировках, чтобы лучше выступать:
Больше заниматься.

Мой профиль

Как решал олимпиаду:

1-й день. A сдал спустя минут 50. На B сначала придумывалась центроидная декомпозиция и чуть было не начал ее писать.
Посидел, придумал простое ДП, написал, отдебагал, к концу только третьего часа сдал. Оставалось 2 часа и тут была моя ключевая ошибка.
Я пошел читать/думать C, а D решил оставить на потом. Взял частичные баллы по С, за минут 30-40 до конца решил перейти на D и набрать "хоть что-нибудь".

По первому дню могу сказать, что надо быть морально готовым, что задача D может оказаться легче задачи A и стараться более грамотнее распределять время (возможно прочитав сначала все задачи, хотя мне не очень нравится держать много задач в голове)

2-й день. A и В сдал за минут 40. Прочитал уже сразу C и D. Подумал минут 30 на C.
Решил перейти на D. Писал 2 разных отжига, оба брали около 20 баллов (а потратил около 2-х часов). Оставшееся время потратил на C, набрал частично, полной идеи не было (хотя всех знаний хватало, что в первый день, что во второй).

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

Общий вывод: Лучше распределять время, больше заниматься.

Мой профиль

Как решал олимпиаду:
1 день: Я прочитал условие задачи А, и начал её делать. Через 2 часа у меня был на ней 41 балл. Потом я прочитал условия других задач. Решил доделать А, через ещё 2 часа у меня на ней было 60 баллов. После начал думать над С но так её и не решил.
2 день: Я прочитал первую задачу, и через пол часа решил её. Потом прочитал условия остальных задач. Решил В на 35, и С на 18. Остальное время придумывал полное решение над В.
Какие ошибки совершил:
В первый день думал что закрою А, поэтому уделил ей слишком много времени. Правильно было бы взять частичные баллы на остальных задачах. Во второй день нужно было взять баллы на D, а не сидеть над B.
Что и как нужно делать по другому на олимпиаде, чтобы лучше выступать: сначала собрать частички, а потом писать все фулы.
Что нужно изменить в подготовке/тренировках, чтобы лучше выступать:
Больше заниматься.

Мой профиль

День 1: Прочитала условие A.Около 45 минут думала над решением. Ничего не придумав написала частичное
решение на одну подгруппу. Прочитала B,C. Написала частичное решение на В но оно летело по TL.
Написала частичное на С на 13 баллов. Вернулась к А и решила писать разбор случаев. Но нужно было
много всего учитывать и оно прошло на 32 балла. Летел тест из второй подгруппы(n<=7) и я пыталась
найти случай который не учла. Я потратила много времени на A и решила писать частичное на D поскольку
осталось мало времени. Но мне не хватило времени.

День 2: Прочитала условие A. За 40 минут написала полное решение. Прочитала В,C и написала решение на B
на 15 баллов. Решение на С не проходила ни одну подгруппу (вердикт WA) скорее всего из-за неточности
с округлением. Прочитала D, писала первые два теста в ручную, но получилось чуть больше 15 баллов
(во втором тесте раставляла 9, вместо 10). Вернулась к В и написала решение на 50 баллов. После
пыталась исправить решение С, но лучше не стало.

Ошибки: В первый день я потратила слишком много времени на A, нужно было чаще переключаться между задачами.
Во второй день я долго сидела над С ,хотя могла набрать ещё баллов над D.
Я плохо распределяла время между задачами(особенно в первый день)из-за чего взяла меньше баллов чем могла

Мой профиль

День 1: Прочитал А. Условие было очень лёгким, но хорошие идеи не приходили (только огромный разбор случаев). Прочитал B. Она была гораздо легче (для меня). Придумал решение за 5 секунд, написал (на тот момент прошло ~30 мин.). Понял, что А должна быть мега лёгкой (условие простое, тем более это первая задача). Час думал над лёгким решением. Понял, что ничего не придумаю. Стал писать, прости господи, разбор случаев на 130 строк. Начиналась паника. Вдруг, я что-то забыл?! Вдруг, не то пишу?! Вдруг, не разберу какой-то случай?! На 3,5 час сдал. Поверил, что не всё ещё потеряно. Пол часа подумал над С. Полное решение я придумать не смог, поэтому написал частичное на 25. Прочитал D. Судя по ограничениям (можно было написать O(n^2)) подумал, что это какое-то жёсткое ДП. Написал на 7 баллов.

P. S. D оказалась жадником и если бы не ограничения, которые меня запутали, и малое кол-во времени, я бы её сдал.

2. A, B оказались безумно лёгкими. Сдал их за пол часа. Прочитал C, D. Испугался D. Подумал, что не смогу взять 100 баллов на C. (может оно и к лучшему, но в принципе она сдаваема). (забуксовал, т. к. ничего не придумывалось). Написал предпросчёт (сохранялку ответов для n<=2000) на C. Получил свои 25 баллов. (осталось 1.5 часа) Понял, что D не такая уж и страшная. Написал первый тест лапками. Получил 10 баллов. Придумал ПОЧТИ оптимальный вариант расстановки ферзей двумя лесенками на 2-3 тесты. Получил 6.48 (вроде-бы) и 7 баллов соответственно (P. S. к концу понял, что на 2-ой тест можно было написать перебор и получить на 3.52 балла больше, но не успел). Остальные тесты разбирать не стал и написал рандомизатор основанный на random_shuffle (можно было и рекурсию (и она взяла бы больше баллов), но почему-то не подумал). Получил ещё 6 баллов. Контест кончился.

Мои ошибки:
1. Я не привык решать очень лёгкие задачи по типу А1, поэтому не могу сходу (или даже в принципе) придумать простое решение (будь задачи потруднее (например на республике), я бы взял, наверно, больше

).
2. Думал, что область труднее, поэтому боялся терять время над придумыванием C и D.
3. У меня было правило: А - лёгкая (и так оно и есть), из-за этого я не думал над С, D, пока не сдам А (это правильный подход, если А сдаваема, но я просидел над ней 3 часа, вместо сдавания D, как Терешко).

Что нужно изменить:
1. Перестать бояться думать над C и D. Начинать придумывать фуллы.
2. Если ничего не придумывается на А - думать проще (я это знал, и думал проще, но из-за малого опыта в решении простых задач, не смог написать микроперебор).
3. Рассматривать каждый тест в задачах с открытыми тестами и выделять на эти задачи по 2 часа.

Я считаю что тренировки менять не надо. Разве что во время подготовки (за месяц-два) забить на школу и днями решать CodeForces, чтобы сдавать А за 10 мин. и брать не 7, а 100 баллов на жадниках типа D1.

Мой профиль

как решал олимпиаду:
1 день: в первые 10 минут придумал решение к А в итоге сдал на 40 минуте. Пошел думать над B не писал на первые 2 подгруппы перебор так как почему-то думал не пройдет по времени, в итоге придумывал код 2 часа, психанул и сдал на 3 подгруппы на 30 баллов.4 час пытался придумать формулу к С но не вышло и написал так же перебор на 25.В последний час решал D, но сразу была неправильная идея с которой я мучился до конца, в итоге ничего не набрал на D.
2 день: За 30-40 минут сдал А на 100, пытался придумать что-то интересное на B, но в итоге после часа над задачей написал дп на первые 2 подгруппы и отдельный случай на третью. так же написал на 18 баллов на С. И пытался то вручную то писав код брать баллы на D но код не выводил варианты и в итоге пришлось руками придумывать.

какие ошибки совершал:
Поспешил с оценкой задачи по времени что отняло 30 баллов, так же поздно перешел к D и оставил всего час.
во второй день был немного не собранный из-за чего и взял мало баллов на D.

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

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

Мой профиль

День 1: Я прочел сначала A, после просидел на ней 1 час и пошел читать другие. попытался их решить, но я всё равно хотел сделать А и сидел на ней дальше. потом под конец я понял как делать A и почти написал решение но не успел. В итоге я её решил почти сразу после конца.

День 2: Я начал с прочтения сразу всех задач и решил делать A и C пробовал но идея пришла только под конец и я не успел сделать A а на самотестировании доделал её за 10 минут

Какие ошибки я совершал: Я всегда собираюсь лишь под конец олимпиады и не успеваю сделать что-то.

Что и как нужно делать по другому на олимпиаде, чтобы лучше выступать: хорошо выспаться и быть в хорошей форме.

Что нужно изменить в подготовке/тренировках, чтобы лучше выступать: главное это понимать тему правильно, неважно сколько времени это займёт много или мало. И ещё важно развивать логику чтобы уметь применять эти знания в не стандартных задачах.