[Logo] Форум DL
  [DL]  На главную страницу 
Индекс форума ->Олимпиадное программирование ->Методика подготовки к IOI 2007 - ... 1, 2, 3, 4
Автор Сообщение
Андрей Костяной

Темы: 121
Сообщений: 274

Мой профиль
02.03.2021 - 07.03.2021

Закончились сборы ЗКШ. Написали еще 3 контеста.

-- В 4-ом я довольно долго писал задачи E и F, из-за этого поздно придумал G и не успел сдать на контесте. Ошибка была в том, что в задаче Е было дано ограничение n <= 20, то есть конкретный намек на битовые маски, а я все равно упорно пытался придуать полиномиальное решение.

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

-- 6-ой был самым удачным для меня, я сдал все задачи и стал топ-1 див А

По итогу, в рейтинге див А я 6-ой.

Также прошла олимпиада ЗКШ. 4 задачи были довольно простыми, сдал их за +- 1 час 20 минут. Дальше была задача F, сначала написал брут для проверки идеи, он набрал 42 балла. Потом придумал улучшение на 71 и сдал это решение минут за 20. После этого до конца контеста боролся с задачей Е (набрал по ней 25 баллов).

По итогам олимпиады занял 5-ое место и диплом 1-ой степени.

Все задачи контестов ЗКШ я дорешал, осталось дорешать олимпиаду MWJ.

Написал тренировку COCI. Не сдал 5-ую задачу, потому что не правильно рассчитал время написания кода и, соответственно, неправильно расставил приоритеты при наборе баллов по задачам.

Также сейчас идет мартовский long challenge на codechef. Вроде придумал несколько не самых простых задач, в ближайшее время собираюсь заняться их написанием.
Дмитрий Горбатовский

Темы: 7
Сообщений: 28

Мой профиль
Отпишусь про Московскую открытую олимпиаду.

1 день.

Быстро прочитал задачи(20 минут), сразу же начал набирать немного баллов по задачам.
Вначале написал жадник на A, который в итоге получил WA. Потом взял баллы по B(15). Начал думать над C, потратил около получаса, в итоге получил 0. После этого я посмотрел, то что по задаче B есть подгруппа на 42 балла, которая мне тогда казалась несложной, и вместо того чтобы начать думать над D я пошёл думать над B, которая тогда казалась легче всего. Во время того как писал B я переключался и думал над A и C. В D было несколько довольно лёгких подгрупп, но они имели низкую стоимость(10 баллов суммарно), и в итоге я не писал их.
В конце первых 4 часов у меня было 15 баллов.
В конце часа я понял, что нужно начать писать частички, и сел писать A. Написав пару дп, которые ловили WA я понял что неправильно понял условие, и в итоге у меня не осталось времени на дебаг.
В итоге разбалловка 0+15+0+0.
После контеста я узнал, что неправильно понял условие в B.

2 день.

Прочитал все задачи, и выделили 2 лёгких(A и С), среднюю(D) и непонятную(B, задача на строки). Сразу сел писать A, и получил 60 баллов. Потом сел писать C(там была реализация), в итоге писал и дебагал полтора часа, после чего получил 0. Переключился на D, и в итоге за 1 час набрал 40 балллов и оставил задачу, т.к. на следующие подгруппы надо было писать что-то сложное. Оставшийся контест писал A и С.
В последние 50 минут я оставил писать A и принялся за С. Писал её недолго(минут 20) но дебагал до конца контеста, и заслал её за 2 минуты до конца.

В итоге разбалловка 60+0+45+40

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

Темы: 121
Сообщений: 274

Мой профиль
08.03.2021 - 16.03.2021

В эти дни занимался мало.

Написал long challenge, заслал несколько не самых простых задач.

Написал 706 CF Div 1, сдал только две задачи, не смог придумать D и C, их уже дорешал.

Прошла открытая олимпиада.

1-ый тур написал совсем ужасно, набрал по задачам 12 + 100 + 14 + 26. Проблема была в том, что по каждой из задач A,C,D я почти полностью додумал идею на большее количество баллов, но не смог довести ни одну из них до конца. Что с этим делать -- без понятия, я переключался между задачами, делал небольшие перерывы и т.п.

2-ой тур написал получше, но все равно не доволен. Получил 100 + 34 + 76 + 40. По задаче Д я во время контеста успел написать код, который должен брать 70+ баллов, но это было минут за 15 до конца и я не успел его отдебажить (там +- 370 строк). То, что я не успел это сделать во время контеста возможно связано с тем, что я набирал частичные по С на 76 баллов, а мог потратить на нее чуть больше времени и придумать сразу полное решение + потратить меньше времени на его реализацию + хватило бы времени на исправление кода на Д (мне нужно было еще минут 20). С другой стороны, мог и не придумать на полный балл, тогда вообще все плохо было бы.

Написал тренировку COCI, сдал все задачи за <3 часа.
Михаил Долинский

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

Мой профиль


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


Прошла открытая олимпиада.

1-ый тур написал совсем ужасно, набрал по задачам 12 + 100 + 14 + 26. Проблема была в том, что по каждой из задач A,C,D я почти полностью додумал идею на большее количество баллов, но не смог довести ни одну из них до конца. Что с этим делать -- без понятия, я переключался между задачами, делал небольшие перерывы и т.п. 
Не понимаю слово "почти".
Если придумал - нужно реализовывать, а не переключаться на другие задачи.
Если "почти придумал", возможно тоже не надо переключаться,а увеличить время на эту задачу,чтобы избавиться от "почти".

2-ой тур написал получше, но все равно не доволен. Получил 100 + 34 + 76 + 40. По задаче Д я во время контеста успел написать код, который должен брать 70+ баллов, но это было минут за 15 до конца и я не успел его отдебажить (там +- 370 строк). То, что я не успел это сделать во время контеста возможно связано с тем, что я набирал частичные по С на 76 баллов, а мог потратить на нее чуть больше времени и придумать сразу полное решение + потратить меньше времени на его реализацию + хватило бы времени на исправление кода на Д (мне нужно было еще минут 20). С другой стороны, мог и не придумать на полный балл, тогда вообще все плохо было бы. 
Надо в тактике конкретно и подробно отразить, как решать олимпиаду - ты как написал первую версию - совсем неполную, так больше к ней и не возвращался.

Написал тренировку COCI, сдал все задачи за <3 часа. 

Я думаю, у тебя великолепная сила рук и много знаний.
Но бывают "ступоры" с придумыванием.
Может есть смысл потренировать именно придумывание.

Например так.
Берёшь Codeforces Round (старый, который не решал) и всё отведённое время занимаешься только придумыванием.
(с переключением между задачами по правилам тактики)
Ничего не пишешь.
Правильность идей проверяешь по авторскому разбору

Ещё можно поступать также (5часов заниматься придумыванием,потом смотреть разбор)
с международными официальными олимпиадами (предварительно убедившись, что есть разбор)
IOI,APOI,CEOI,BalticOI
и Российские последние.

И на основе полученного опыта написать свою книгу (и сам попользуешься, и детям останется)
"Как решать задачу", где отразить приёмы, которыми можно/нужно пользоваться,чтобы придумать решение задачи.

- возможно это зависит от тематики задачи
- среди приёмов - ты уже озвучивал - исследование пространства ответов (написанием брута) в поисках закономерности
- систематически перечислить все известные стандартные приёмы (ты часто при объяснении решения на разборе такую фразу употребляешь)

Можно начать с прочтения книги Пойа "Как решать задачу"
(это про задачи по математике и написано очень много лет назад)
Андрей Костяной

Темы: 121
Сообщений: 274

Мой профиль
17.03.2021 - 01.05.2021

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

И так, начнем с дорешки за это время:
1) https://codeforces.com/contest/1500/problem/E 2_4 задач с открытой олимпиады школьников. Сдал ее на полный балл своим кодом с контеста, нужно было потратить еще +- 30 минут, чтобы оно взяло баллов 70+;
2) https://www.codechef.com/MARCH21A/problems/RWALKS задача на центроидку;
3) https://codeforces.com/contest/1483/problem/F Задача Н с Технокубка на Ахо-Корасик;
4) https://csacademy.com/contest/archive/task/nogcd/statement/ интересное сведение к Эйлерову циклу;
5) https://csacademy.com/contest/archive/task/manhattan техническая задача на комбинаторику;
6) https://contest.yandex.ru/contest/26459/problems/3/?success=50450690#43063/2021_03_29/ES66KH5msm задача 2_3 с респы на оочень интересную sqrt-декомпозицию;
7) задача 1_4 с респы, дорешал на 100 своим решение на 70, не хватило буквально 10 минут, чтобы сдать ее на контесте
8) https://codeforces.com/contest/1498/problem/F интересное сведение к стандартному НИМу, дальше техническая реализация;
9) https://codeforces.com/contest/1513/problem/F свести к дереву отрезков;
10) https://www.codechef.com/problems/ARRAYOPS конструктивная задача;
11) https://www.codechef.com/COOK128A/problems/SANITIZE интересное сведение к +- стандартному перебору;
12) https://atcoder.jp/contests/arc117/tasks/arc117_c важно свести операции из условия к матричному виду, дальше дело техники;
13) https://atcoder.jp/contests/arc117/tasks/arc117_d интересное сведение к двум DFS;
14) https://atcoder.jp/contests/arc117/tasks/arc117_e интересная задача на ДП;
15) http://www.usaco.org/index.php?page=viewproblem2&cpid=1141 интересная задача на ДП, либо на нахождение определителя матрицы;
16) https://oj.uz/problem/view/COI20_paint задача с COI 2020 на Sqrt-декомпозицию + техника small-to-large (в авторской реализации открыл для себя swap стандартных STL контейнеров, который работает за O(1) )
17) https://codeforces.com/contest/1517/problem/G интересное сведение к потокам;
18) https://atcoder.jp/contests/abc199/tasks/abc199_f задача на возведение матрицы в степень;
19) https://codeforces.com/contest/1500/problem/C задача 1_4 с открытой олимпиады школьников, интересное сведение к графам и классам эквивалентности;
20) https://codeforces.com/contest/1500/problem/D задача 2_3 с открытой олимпиады, узнал из нее про технику минимуа за O(1) но не с деком, а с двумя стеками (бывает полезно, когда мы умеем только вставлять в структуру, но не умеем удалять);


Прошла олимпиада Технокубок. Быстро сдал 6 задач, оставшиеся 2 были очень сложными (На контесте, вроде, только два человека решил G).


Прошла республиканская олимпиада 2021.

В первый день получил 370/400, не успел по времени исправить 4-ую на 100.

Во второй день получил 319/400. Две задачи были совсем простыми. 3-ая была гробом контеста, я сдал на 39 и почти все оставшееся время улучшал баллы по открытым тестам (последнее улучшение было за +- 5 минут до конца контеста и суммарно по ним у меня +- 80 баллов).


Написал 715 CF раунд. В целом раунд очень зашел, сдал 3 задачи, 3-ая была не самой простой.


Написал atcoder regular contest 117. Сдал A,B задачи. В С задаче не смог найти правильную матрицу. В Д задаче был ближе всего к решению, но не успел довести до полного решения во время контеста.


Написал тренировку USACO FEB. Была очень простая задача, ее сдал оч быстро. Еще 2 задачи были очень сложными, я больше пытался решать подгруппы, но ни одну не смог дожать до полного балла.


Написал тренировку USACO Open Contest. Сдал 2/3 задач, 3-ую сдало много людей, но многие участники решали не авторсим решением (там интересное ДП), а свели задачу к BEST formula, в которой нужно уметь находить определитель матрицы. Я его находить не умею, потому что в школьных контестах эта тема не затрагивается.


Написал CF rounf 2050. Сдал A,B,C без особых проблем. В D задаче долго пытался сдать решение, но получал WA, решил переключиться на Е. Придумал по ней решение, окончательную почти правильную версию отправил минут за 25 до конца. НО. Я не заметил, что ответ нужно выводить по модулю (он помещался в long long, поэтому я не обратил внимание на формат вывода). Обнаружил я это только за минут 5 до конца контеста и быстро исправил свою ошибку. Думаю, что если бы внимательнее прочитал формат вывода, то успел бы сдать Д. А так слитый рейтинг
Михаил Долинский

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

Мой профиль
На придумывание так и не начал тренироваться
Андрей Костяной

Темы: 121
Сообщений: 274

Мой профиль
03.05.2021

Прошел 1-ый контест сборов.

Было 4 задачи, первые впечатления:
A) св-во, что корень можно взять log log A раз + корневую как-нибудь прикрутить;
B) что-то на строки (может даже строковые структуры);
C) ДП, вроде сходу понятно, куда думать;
D) задача на структуры.

Я начал думать над всеми задачами по очереди. Придумал по А полное решение, решил сначала написать брут (чтобы проверить правильное понимание условие). Написал минут за 5, сдал на 33 балла на +- 37-ой минуте. Начал писать полное и через 7 минут понял, что не продумал один момент, который оказался критическим. Решил переключиться. Придумал по задаче B куб с хорошей константой, который должен был взять 50 баллов. Сдал его на +- 1 часу 33-ей минуте. К этому времени я уже примерно представлял полное по С, но решил сначала написать идею на Д, сдал ее на 20 баллов на 2 часу 15-ой минуте. Теперь уже решил сдать задачу С. Сначала решил написать куб (его легко потом можно исправить на квадрат). Сдал куб в начале 4-ого часа. Еще через 10 минут сдал полное по С. Теперь нужно было что-то придумывать по задачам. Я опять стал их чередовать. Подумал над А минут 15, потом над B еще минут 15-20. Продвижений особых не было. Когда переключился на задачу Д, то через минут 10 смог додумать идею со включениями-исключениями на 100 баллов и, так как у меня был код на 20 баллов, я минут за 10 исправил его на 100. Все оставшееся время пытался придумать решения по А и B.

Итог: 33 + 50 + 100 + 100 = 283.

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

Темы: 121
Сообщений: 274

Мой профиль
04.05.2021

Прошел 2-ой день отбора к миру.

Первое впечатление о задачах:
1) ДП для префиксов;
2) почти стандартный сканлайн;
3) какое-то ДП, комбинаторика;
4) что-то на структуры;

Опять начал думать над всеми задачами по порядку. Начала думать в сторону ДП над А, спустя 10 минут решил поменять направление и быстро придумал жадник на фулл. Получил 100 по А на +- 40-ой минуте. Дальше решил подумать над С. Придумал решение за куб. Начал его писать и через 20 минут получил WA 7. Ушло минут минут 10 на то, чтобы понять, в чем ошибка, и еще через 10 минут (1 час 43 минуты) я получил по задаче 73 балла. Примерно представлял, куда думать, чтобы получить 100, но пока решил переключиться на B. Там я примерно представлял, как писать сканлайн, решил сначала написать медленную версию, а потом улучшить ее с ДО. Сдал медленную версию в 2 часа 36 минут и через еще 7 минут получил по B 100 баллов. Теперь решил уже дожать задачу С. Ушло минут 15, чтобы додумать ее до 100 и еще 30 минут, чтобы получить по полный балл. Оставалось 3 часа 30 минут на задачу Д. Были легкие подгруппы на 25 баллов, сдал их за 30 минут. Еще в начале контеста я придумал, скорее всего, полное решение по Д, но оно требует написание Link-cut (который я никогда не реализовывал), поэтому до конца контесты я пытлася придумать решение без него, но безуспешно.

Итог: 100 + 100 + 100 + 25 = 325.

Контестом доволен.
Михаил Долинский

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

Мой профиль


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

Еще в начале контеста я придумал, скорее всего, полное решение по Д, но оно требует написание Link-cut (который я никогда не реализовывал), поэтому до конца контесты я пытлася придумать решение без него, но безуспешно. 
И много ещё есть таких тем, которые "на слуху" (то есть часто бывают в контестах), но ты никогда не реализовывал?
Может есть смысл составить их список и реализовать хоть по разу?

На Link-cut даже я многократно натыкался, хотя читал задач/разборов на порядки меньше чем ты.
Андрей Костяной

Темы: 121
Сообщений: 274

Мой профиль
Я не разбирал реализацию link-cut, потому что его не дают на школьных контестах.
Михаил Долинский

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

Мой профиль
Ну вот же дали
И к тому же у тебя впереди и студенческие контесты.

А ты выяснил - у этой задачи есть решение без link-cut?
Может быть такое, что автор задумывал другое, а с link-cut оно тоже решается?

Кстати, а почему не написал про третий день?
Андрей Костяной

Темы: 121
Сообщений: 274

Мой профиль
На сборах к миру дают и FFT, они не показатель того, что на самом деле дают на школьные контесты. Ребятам нужно найти много задач, дают то, что есть.

Да, у этой задачи есть решение без link-cut. Там можно решить с помощью сжатия дерева. На контесте я думал над сжатием, но я не знал одну фишку, которую открыл только из авторского кода.


Теперь про отбор.



3-ий день отбора написал не очень. Получил 40 + 100 + 80 = 220 (первое место 249). Задачу B сдал за вполне разумное время. В А задаче мог добрать еще 9 баллов, но не сделал этого из-за проблем с задачей С.

А вот теперь по поводу задачи С. Полное решение со стеком занимает от силы строк 20 кода. Но я потратил на эту задачу почти 2 часа, потому что не придумал полное, а писал на 80 двумерное дерево отрезков. Я не знаю, почему не придумал, ведь ограничение на N <= 10^7 явно указывали на линейное решение + когда-то видел похожую задачу на стек.




4-ый день отбора.

Прочитал все задачи, на Д задачу быстро придумал дерево доминаторов и сдал ее на 100 на 57-ой минуте. Потом подумал над задачей С и придумал код Прюфера на 54 балла. Решил временно переключиться, чтобы сдать простой брут на А на 14 баллов, но, видимо, в задаче не оч сильные тесты и брут зашел на 69. Переключился на B и не придумав ничего, решил вернуться к написанию С на 54. Как только сдал С на 54, то почти сразу додумал на 100 в 3 часа 16 минут сдал ее. Остальное время я исследовал задачу B, но смог сдать только на 36 (k = 2, когда полные ограничения k = 10).

Итог: 69 + 36 + 100 + 100.
Михаил Долинский

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

Мой профиль


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

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

Да, у этой задачи есть решение без link-cut. Там можно решить с помощью сжатия дерева. На контесте я думал над сжатием, но я не знал одну фишку, которую открыл только из авторского кода. 

Получается есть смысл знать link-cut.
А как проще придумать/написать - сжатием дерева или link-cut?
Повторяю вопрос - ты не ответил - думаю есть смысл подумать над ним.
И много ещё есть таких тем, которые "на слуху" (то есть часто бывают в контестах), но ты никогда не реализовывал?
Может есть смысл составить их список и реализовать хоть по разу? 


А вот теперь по поводу задачи С. Полное решение со стеком занимает от силы строк 20 кода. Но я потратил на эту задачу почти 2 часа, потому что не придумал полное, а писал на 80 двумерное дерево отрезков. Я не знаю, почему не придумал, ведь ограничение на N <= 10^7 явно указывали на линейное решение + когда-то видел похожую задачу на стек. 
А сколько времени ты думал над придумыванием решения?
Было время подумать над альтернативными подходами?
Что про это в тактике написано?
Ты придерживался того, что написано?
Андрей Костяной

Темы: 121
Сообщений: 274

Мой профиль
Проще сдать со сжатием дерева (я уже дорешал эту задачу).

Если и есть какие-то такие темы "на слуху", которые я не реализовывал, то единственная причина, почему я их не разбирал -- они не появляются на школьных соревнованиях + большие объемы написания кода. К примеру хорошая реализация Link-cut со splay деревом займет строк 300 минимум. И мне кажется бесполезным изучать эти темы сейчас, когда остается месяц до IOI (особенно если учесть, что их нету в IOI 2021 syllabus).


В задаче С у меня было много времени, чтобы придумать решение (больше часа, я думаю). Я не стал думать дольше, потому что по тактике выставил предел времени, когда пора начинать писать код.



Теперь про отбор.

День 5.

В первые 50 минут контеста сдал задачу С. Дальше по-очереди думал над всеми задачами и самой простой оказалась Д, сдал ее в 2 часа 15 минут. Дальше продолжал чередовать задачи А и B. Через примерно час решил больше сделать упор в задачу А, так как в ней у меня были продвижения. Я стал писать разные бруты и исследования. В 4 часа 29 минут я смог сдать полное решение по задаче А. По задаче B я набрал 0 баллов, не придумал вообще ничего.

Итог: 100 + 0 + 100 + 100 = 300.

После контеста спросил решение на B у парня, который ее сдал. Частично я придумал многие вещи для полного решения, но самые важные факты заметить не смог.
Андрей Костяной

Темы: 121
Сообщений: 274

Мой профиль
День 6.

Итог: 32 + 19 + 100 -- плохой результат.

Как все произошло. Прочитал все задачи, сразу придумал ДП на задачу С на 100 баллов, решил подумать над остальными задачами. Придумал частичное на B на 19 баллов, сдал его, потому что B выглядела самой сложной задачей контеста. Дальше решил подумать над задачей А. Придумал решение, которое укладывалось в ограничение по времени, но словило бы ML. Сдал по А брут, чтобы был не 0 (это заняло мало времени) и пошел писать С на 100. С сдал +- в 3 часа. Было много времени я придумал сложное решение на +23 балла по B и пошел его реализовывать (и так до конца контеста не смог его реализовать).

Что самое обидное -- после окончания контеста я придумал, как исправить свое решение по А на 100 баллов, подумав над задачей еще пару минут.
 
Индекс форума ->Олимпиадное программирование ->Методика подготовки к IOI 2007 - ... 1, 2, 3, 4
Time:0,047