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

Topics: 121
Messages: 269

My Profile
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. Вроде придумал несколько не самых простых задач, в ближайшее время собираюсь заняться их написанием.
Dmitriy Gorbatovskiy

Topics: 7
Messages: 24

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

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. Плохая реализация
Также очень слабая сторона. В основном я придумываю решения, но не могу их реализовать, потому что низкая скорость написания кода и его низкое качество.
Andrey Kostyanoy

Topics: 121
Messages: 269

My Profile
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 часа.
Mihail Dolinskiy

Topics: 1706
Messages: 39948

My Profile


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


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

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
и Российские последние.

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

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

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

Topics: 121
Messages: 269

My Profile
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 до конца контеста и быстро исправил свою ошибку. Думаю, что если бы внимательнее прочитал формат вывода, то успел бы сдать Д. А так слитый рейтинг
Mihail Dolinskiy

Topics: 1706
Messages: 39948

My Profile
На придумывание так и не начал тренироваться
Andrey Kostyanoy

Topics: 121
Messages: 269

My Profile
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.

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

Topics: 121
Messages: 269

My Profile
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.

Контестом доволен.
Mihail Dolinskiy

Topics: 1706
Messages: 39948

My Profile


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

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

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

Topics: 121
Messages: 269

My Profile
Я не разбирал реализацию link-cut, потому что его не дают на школьных контестах.
Mihail Dolinskiy

Topics: 1706
Messages: 39948

My Profile
Ну вот же дали
И к тому же у тебя впереди и студенческие контесты.

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

Кстати, а почему не написал про третий день?
 
Forum Index ->Олимпиадное программирование ->Методика подготовки к IOI 2007 - ... 1, 2, 3
Time:0,078