Форум DL

Мой профиль

26-30.06.2020

В эти дни я в основном разбирался с долгами по дорешке и написал несколько контестов.

Дорешка:
1) https://codeforces.com/contest/1373/problem/G, задача с последнего едука. Как я уже говорил, на едуке я не оч быстро разобрался с F, из-за этого не успел подумать над G. В дорешке сам полностью придумал идею и дорешал;
2) https://oj.uz/problem/view/COI18_zagonetka, задача с COI_2018. На контесте вообще не правильно придумал, как восстанавливать ребра, Леша Ситников подсказал правильное направление, дальше я сам все додумал;
3) https://oj.uz/problem/view/COI18_svjetlost, задача на геому + ДО с COI_2018. От геомы было не оч много, только определение полярного угла точки, дальше не сложное ДО. Теперь я умею пользоваться atan2 (находит полярный угол точки, это встроенная ф-ция);
4) https://oj.uz/problem/view/COI18_pick, задача с COI_2018. Довольно конструктивная. В принципе, если понять главную фишку (что почти всегда внутри 0 точек) и примерно понять, как строить такие многоугольники, то все становится не сложно. У меня получилось строк 500, но можно было намного меньше, просто я не писал ф-ции, а все руками (мне лично так было удобнее)

(к сожалению почти все задачи с COI_2018 на DL сдать не смог, так как нету чекеров

)

(остальная дорешка будет потом, чтобы не нарушать хронологию)

Теперь воскресная тренировка. Мы писали COCI_2016_R2. Вот первые впечатления о задачах:
1) изик;
2) перевод числа в k-ую систему счисления;
3) очевидная идея с жадностью (+ у меня были какие-то воспоминания о решении этой задаче, возможно на каких-то старых сборах с ней уже встречался);
4) понятно сразу, как для нечетных и +- очевидно, что для четных >2 должны быть какое-то решение.
5) Если сходу, то что-то страшное, даже не сразу понял условие;
6) тут простор для всяких жадностей и ДП;

Первые 4 задачи были совсем простыми, поэтому их я закрыл за 1-ый час. Дальше я решил все-таки разобраться с условием 5-ой. Это у меня получилась, но я решил все-таки пока что подумать над 6-ой. Вроде придумал какое-то ДП, но решил пока не спешить и еще подумать. Придумал еще несколько жадосов, но вроде как сам их и сломал, поэтому решил все-таки написать ДП. Справился я с этим примерно к началу 3-его часа и получил 80 баллов. Еще подумав я понял, в чем была моя проблема я решил вернуться к жадникам. Решил отправить один из вариантов на "авось" (тем более писался он оч быстро). Но получил 0 баллов. Мне понадобилось немного времени, чтобы понять причину этого результата и я решил переключиться на 5-ую. Как только я переключился (это было примерно в начале 3-его часа), мне сразу же пришла в голову идея с хешами. Я ее еще немного докрутил и к началу 4-ого часа я получил полный балл по 5-ой. После этого я стал думать над 6-ой, мне пришли в голову идеи с неполиномиальным решением (за 2^n*n) и до конца контеста я пытался придумать что-нибудь за 2^k*n, так как у меня были идеи, что возможно можно будет для маленьких k использовать такое решение, а для больших k - какой-нибудь жадник или еще что.

Как я и предполагал, самым важным ходом было догадаться, что при k^2 >= n ответ всегда существует (на это намекали ограничения, так как n = 400 это подозрительно, ведь если бы хотели куб, то поставили бы 500, а если квадрат, то >1000). Само ДП довольно интересное и док-во мат индукцией, что при k^2 >= n мы выиграем, тоже было оч интересным.

Кроме того, я написал codechef_june_lunchtime. Это мой 1-ый lunchtime Div 1.

1-ая задача была совсем простой. На 2-ую я сходу ничего не придумал, поэтому решил сначала попробовать 3-ю. Она была более стандартной, поэтому я над ней не оч много думал и без особых проблем сдал. Затем я решил вернуться ко 2-ой. Были какие-то страшные идеи с сетами по моментам времени, но потом я подумал, что это 2-ая задача и на нее должно быть что-то простое и сразу придумал простое решение (думаю, что нужно запомнить такой прием, т.е. подумать, что задача простая и не заморачиваться с чем-то сложным). Ее тоже без особых проблем сдал. После этого мне оставались 4-ая и 5-ая задачи. Я решил сначала написать 5-ую на 50, так как это было совсем просто, даже думать не нужно было. После этого у меня были полные идеи на 5-ую (она похожа на одну из задач со сборов к миру 2019), но я решил, что сначала нужно сдать более простые 50 баллов по 4-ой задаче. Этим я и занялся. Первая версия моего решения получила 0. Я относительно быстро догадался, что проблема в отрицательных числах. Поэтому примерно через 40 минут от сдачи 5-ой на 50, я получил еще 50 по 4-ой. Так как я уже знал фулл по 5-ой, то я начал печатать. За минут 20 я написал решение, но оно получило TL. Пришлось немного побороться с константой модульной арифметики и еще через минут 20 я получил долгожданный фулл. После этого я продолжил думать над 4-ой, думал над тем, как проверить, можно ли из такого-то набора чисел собрать правильный массив и начинал уже думать над тем, что для этого какое-либо число должно встречаться не больше половины раз, но к этому времени контест закончился.

https://www.codechef.com/LTIME85A/problems/RESTCH. Вот ссылка на 4-ую задачу, ее я уже дорешал. Как я и думал, нужно было сформулировать условие, в каком случае мы можем собрать массив. После этого можно было аккуратно строить с помощью сета. На эту задачу почему-то не выложили разбор, поэтому мне еще пришлось повозиться, разбирая коды других участников.

P.S. На этом lunchtime в Div 1 я занял 6-ое место, и на предыдущем lunchtime Div 2 я занял 6-ое место. С - стабильность

Мой профиль

ДП 1 
1. Бомбардировка              ( 8 / 295)  Костяной 
2. Конькобежная трасса        (30 / 108)  Гомель-1, Костяной, Харрасов  
3. Космический корабль        (19 /  96)  Коробейников, Ситников, Лосев 
4. Турнир ораторов            (58 /  45)  Лосев, Харрасов 
5. Диск                       (36 /  45)  Попович  
6. RSA++                      (94 /  36)  Горбатовский 

ДП 2 
1. Цифровая строка            ( 2 / 1005) - 
2. Reverse 2D                 (13 / 239)  Харрасов 
3. Видео сервис               (19 / 187)  Лосев  
4. Лазер                      (20 / 144)  Лосев 
5. Арифметический показатель  (50 /  66)  Горбатовский 
6. Новый факультатив          (19 /  60) - 

Графы 
1. Диверсия                   ( 6 / 431)  Костяной 
2. Служба спасения            (12 / 148)  Коробейников, Гуленко, Костяной 
3. Западный поток - интеракт. (21 / 121)  Костяной, Лосев, Ситников 
4. Путешественник             (29 /  64)  Кадушко, Лосев, Костяной  
5. Праздничное украшение      (80 /  19)  Кадушко, Горбатовский, Лосев 
6. Дороги                    (190 /  12)  Лосев 

BY_2020 
День 1 
1. День Вселенной             (23 /   2) -
2. Вулканы на Венере          (20 /   2) - 
3. Любимые игрушки - интеракт.( 8 /   5)  Лосев 
4. Ракета на нейтринной тяге  ( 3 /  12)  Костяной 
День 2 
1. Сорняки                    (15 /   3) - 
2. Очаровательные нейтрино    (11 /   4) -  
3. Марсианские Игры           ( 5 /   8)  Лосев, Костяной 
4. Ускоритель частиц - с ОТ   ( 1 /  25)  Костяной

Мой профиль

01-05.07.2020

Я буду рассказывать про тренировки и параллельно про дорешку.

0*) https://www.codechef.com/problems/COWSHEDS, задача с последнего lunchtime. Я ее сдал на контесте, но я помнил, что в задаче со сборов к миру был подход за O(n log n) с красивой идеей (приведение к отрезкам длины 2^k), поэтому я проверил разбор, и, да, у этой задачи тоже было решение за O(n log n) с похожей идеей, поэтому я дорешал ее 2-ым способом.

1) тренировка со среды COCI_2016_R3

В принципе ничего особенно интересного не было (среди 5-ти задач, их я сдал на контесте). А вот в 6-ой мало того, что геометрия, так еще и быстрое преобразование Фурье. Мне кажется, что в ближайшее время такую задачу дорешивать нет смысла, так как БПФ - это более студенческая тема.

2) CF 654 Div 2. Так как контест анрейт я относительно быстро разобрался с ABC, потом придумал D, но накосячил в реализации, переключился на E1. Долго тупил, потом все-таки придумал и сдал без особых проблем. Затем я решил переключиться на F. Вот тут произошло самое обидное. Я придумал все, просто все. Я дошел до того, что тут скорее всего ДО на подотрезок макс длины с ограничениями, но я не знаю, просто не знаю, почему я это не стал писать. Я этого не отвергал, просто мысль промелькнула и все (после контеста я дорешал эту задачу этой идеей). К сожалению до конца контеста так и не нашел багов в D и не додумал E2, так как мои мысли были направлены на корнячку в F (D и E2 уже дорешал).

3) CF Global 9. За 7 минут сдал A,B. Еще минут за +- 10 попытался накинуть что-нибудь на С, но получил только -2. Решил переключиться на D и через 20 минут сдал ее с +. Так как я уже был подбодрен тем, что сдал D, я решил вернуться и добить С. Получилось у меня это только через 15 минут в общей сложности с +4. Ну, ладно, прошло чуть меньше часа, нужно быстрее двигаться дальше. Прочитал E. Как-то сразу в голову пришла идея, что ответ всегда существует. Потом придумал перебор от 1 до n и решение за O(n^2 log n). Реализовал его и тут же столкнулся с проблемой одинаковых чисел (у меня остался хороший тест от задачи C, который чудесным образом подошел сюда). Написал какой-то костыль, что если плохо, то тип ответа не существует и решил отправить, так как с моим штрафом -50 не сыграет особой роли. Естественно, я получил WA 4. Я понял, что просто так не отелаюсь и немного пришлось додумать идею, но в общей сложности к 1.40 я сдал эту задачу с +1. После этого до конца контеста я пытался придумать F, но ничего путного в голову не пришло.

По итогу F и G оказались очень конструктивными, а кода была строк 10-20 (без дефайнов). Их я уже дорешал.

(и, да, я вернул себе международного мастера

)

4) воскресная тренировка COCI_2016. Сразу скажу, что я лег поздно, так как ждал рейт с Глобала. Из-за этого я был оч не оч на контесте.

ABC-задачи изики, поэтому перейдем к интересному.
D - я почти сразу придумал идею про то, как искать прогрессии и что нам нужно мин покрытие, но я также понял, что жадосы ломаются.
E - придумал сразу, что нужно перевернуть строки. Пытался какие-то жадосы, потом приумал идею про спуски и подъемы по преффиксам.
F - придумал сразу хеши и как решать N = M за куб с константой. Потом придумал, как изменить для N != M, но все еще за куб, это решение брало 140 и 1 тест TL. Потом понял, что я мог просто написать двоичные подъемы и сразу получил фулл.

Почему я во время контеста не сдал D и E? Я оч неправильно подошел к контесту, так как:
1) я лег поздно;
2) я оч хотел сдать F. Я понимал, что улучшив со 140 до 160 я не получу особо профита, но мне просто хотелось фулл. Я осознавал во время контеста, что я поступаю не правильно, но я был очень уставшим и это было моим отдыхом, так как я решал в свое удовольствие.

Думаю, что я добил бы Е, если бы немного раньше закончил с F.
D - вообще отдельная тема. Оказалось, что все, что я придумал - это и есть задуманное решение. Авторы в разборе написали, что, да, есть тесты, которые ломают жадники, но эта задача NP-полная, поэтому чтобы можно было ее сдать за разумное время, они сделали плохие тесты, на которых жадники (более-менее умные) берут фулл. Оправдывались они тем, что жадники очень часто получают правильный ответ или очень-очень близкий. Просто без комментариев.

Е и D уже дорешал, только засылал не в дорешку, а на oj и в олимпиады по информатике, так как дорешка пока не открыта.

Мой профиль

6 июля

Долги по теории

 Решить и описать решения                                                                   

 2012_1_3. Цифровая строка            ( 2 / 976)   Костяной 
 2017_2_2. Новый факультатив          (17 /  61)   Горбатовский

Текущее состояние в теории (Задано 26 задач)
... дорешать все задачи – до 17 июня - не получилось
Может надо помощь просить, тем у кого не получается.

Решено

             Задачи    ДП 1     ДП 2    Графы   BY_2020
Костяной       20        4        2       6        8
Лосев          18        5        3       4        6
Харрасов       14        5        3                6
Ситников       14        4        1       4        5
Попович        13        6                2        5 
Горбатовский   12        3        0       5        4

Никаких изменений в теории

Текущее состояние в дорешивании воскресных олимпиад (114 задач к дорешиванию)

Решено

Костяной     105(+ 9)
Попович      105(+ 9)
Ситников      84(+11)
Лосев         78(+10)
Горбатовский  34(+ 0)
Харрасов       7(+ 0)

Мой профиль

01.07.2020 - 06.07.2020
Дорешал несколько задач и написал несколько конестов (довольно не плохо, но можно лучше и больше)

ABC167_E (https://atcoder.jp/contests/abc167/tasks/abc167_e) - из-за того, что я неправильно понял условие (вроде пропустил слово "adjacent" или неправильно его перевел) я не решил задачу, хотя некоторые формулы совпадали с теми, которые в разборе.

ABC167_F (https://atcoder.jp/contests/abc167/tasks/abc167_f) - как и предполагалось, задача на жадник (нужно сформировать большую ПСП из некоторых последовательностей скобок - сказать, возможно ли это)

Решил CodeForces Round #654 (https://codeforces.com/contest/1371)
Все прошло очень плохо. Рассказывать даже не хочется. За 30 минут решил AB и, ничего не придумав по CD (кроме каких-нибудь костылей) ушел с раунда ни с чем, если не считать слитого рейтинга
C и D дорешал на следующий день

C - жадник с 2-мя простыми случаями, которые я не заметил
D - жадник + конструктив. На контесте какой-то более-менее логичный конструктив написал, но он оказался неверным

Решали COCI16_17_R4
A — реализация
B — реализация
C — дп
D — теория чисел, битмаски
E — дп, строки (бор)
F — хеши

За 20 минут сдал AB. Прочитал C, понял, что ДП и стал думать. Придумал, написал и отправил. Сначала словил кучу WA (выходил за границы массива). А дальше было несколько тестов с ML. В какой-то момент я решил, что у меня будет сумма элементов не больше 150000 (хотя в условии было написано 100000) и долго пытался уменьшить память при таких ограничениях. Но потом посмотрел в условие и увидел, что там 100000, исправил и сдал. Потом прочитал DEF. Более-менее решаемой мне показалась E и я стал думать над ней. Сначала написал неправильное ДП, но каким-то чудом взяло 14 баллов. Потом понял, что строки я могу переставлять как хочу, мне пришла идея построить бор по суффиксам (или по префиксам, если перевернуть строки). Написал эту идею и оно не взяло все баллы. Долго я искал, ошибку и понял, что я не так реализовал и у меня выводило больше, чем надо. Исправил, сдал. Над F я не стал думать и решил перейти на D и до конца контеста (1 час ± 20 минут) я писал ее. Но так и не сдал. В целом довольно неплохо отрешал контест

Дальше я написал ABC173 (https://atcoder.jp/contests/abc173)
A — жадник, реализация
B — реализация
C — перебор
D — жадник
E — жадник
F — деревья, дп

AB сдал быстро, но над C я заморочился, т.к. сначала не так понял условие. Эти задачи сдал и пошел дальше. На D сразу придумался какой-то жадник, я его написал, а он оказался неверным. Дальше нарисовав немаленький тест, я пришел к полному решению и сдал с 4-ой попытки (т.к. до этого засылал неправильные реализации полной идеи). E вроде как встречалась где-то, но я ее не помню. Довольно неприятная задача с разбором случаев и реализацией. Я ее писал до конца контеста, т.к. никаких идей по F не было. В итоге закончил контест с 4-мя задачами

Впрочем, есть над чем работать (учить английский и не тупить. из-за этого теряется куча времени)
(есть еще, что я успел сделать, но это потом)
______________________
Жизнь - игра. Сюжет - так себе, но графика потрясающая.

Мой профиль

6-12.07.2020

В эти дни шел long challenge на codechef и почти все силы я положил на него. Смог сдать 3 изика, 1 медиум, 1 медиум-хард полностью и еще 1 медиум-хард и 1 хард частично. Завтра будут результаты и долгожданный разбор. В принципе мне нравится участвовать в long, так как он заставляет меня думать над задачами ну очень долго (в обычное время я бы уже посмотрел разбор).

В среду решали тренировку COCI_2016_R5. Контест оказался довольно несложным, я даже сначала не оч поверил в это. Но потом собрался и закрылся. Понравилась 6-ая задача (оптимайзы битсетами и ДП по поддеревьям).

Отрешал тренировочный CF 655 Div 2. Раунд для меня был анрейт. Быстро справился с ABC. Потом прочитал Д и придумал какой-то жадос. Отослал и тут КФ лег. Появилась огромная очередь из посылок, поэтому я решил не терять время и пойти подумать над F. Через минут 15 (!) оттестилось решение на Д и я получил WA. Но к этому времени я уже придумал что-то близкое к полному на F, поэтому я решил ее добить. Додумал F и стал печатать. Но после отсылки я получи WA. И до конца контеста я то и дело пытался дожать F, но так и не смог. До сих пор не понимаю, в чем ощибка в моем решении.

Отрешал воскресную тренировку COCI_2016_R6. Контест был довольно несложным (первые 5 задач). C ABCD вообще не было проблем, а вот с Е мне пришлось повозиться, чтобы уложиться в ML и TL. Из-за того, что долго боролся с Е, мне осталось мало времени на F. Я стал над ней думать и придумал CHT, для ответа на запросы. Кроме того я уже начал думать, что нужно переходить от (A,B) к (A/B,1), но к этому времени контест закончился.

В разборе на F было все то, что я уже придумал + надо было додумать идею с (A,B). Обидно, думаю, что если было бы больше времени, то я мог бы и сам додумать на контесте. А чтобы было больше времени, я должен был сдать быстрее Е. Зато теперь освоил +- новую для меня фишку оптимайзов по памяти (я в теории такое думал, но до этого писал 1 раз от силы). Короче, контест был довольно поучительным.

Также отрешал CF Educational 91. В самом начале раунда CF упал. Просто нельзя было отослать решения и читать условия. Но потом как-то разрулили эти проблемы и продлили раунд на 30 минут. Я закрыл 6/7, в принципе доволен, так как на F сдал ДО относительно быстро. На G посмотрел разбор и, да, я думал, что нужно бить на интервалы +- n/k, но про сортировку я пока что не до конца осознал.

В общем, за эту неделю накопилось прилично дорешки (2 раунда CF, задача с воскресной COCI + завтра выложат разбор на Codechef). Поэтому завтра-послезавтра я буду по уши в дорешивании.

Мой профиль

13 июля

Долги по теории

 Решить и описать решения                                                                   

 2012_1_3. Цифровая строка            ( 2 / 976)   Костяной 
 2017_2_2. Новый факультатив          (17 /  61)   Горбатовский

Текущее состояние в теории (Задано 26 задач)
... дорешать все задачи – до 17 июня - не получилось
Может надо помощь просить, тем у кого не получается.

Решено

             Задачи    ДП 1     ДП 2    Графы   BY_2020
Костяной       20        4        2       6        8
Лосев          18        5        3       4        6
Харрасов       14        5        3                6
Ситников       14        4        1       4        5
Попович        13        6                2        5 
Горбатовский   12        3        0       5        4

Никаких изменений в теории

Текущее состояние в дорешивании воскресных олимпиад (126 задач к дорешиванию)

Решено

Костяной     122(+17)
Попович      116(+ 9)
Ситников      91(+ 7)
Лосев         83(+ 5)
Горбатовский  34(  0)
Харрасов       7(  0)

Мой профиль

13-19.07.2020

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

Сначала дорешка:
1) https://www.codechef.com/problems/EXPREP, задача с long на суф мас + ССД. На контесте я все про классы одинкаовых строк придумал, но я не придумал как хитро обрабатывать одинаковые строки (эту идею прочитал, а дальше ДО легко придумывается, если что, то вроде даже Фенвиками можн оптимайзнуть);
2) https://oj.uz/problem/view/COCI17_gauss, задача с воскресной тренировки (12-ого числа). Как я и говорил, на контесте почти все придумал, но все равно задача оч неприятная в плане реализации, доволен;

Обе эти задачи были оч объемными, так что это было хорошей практикой написания длинных (для СП, конечно) кодов.

(остальная дорешка будет потом, чтобы не нарушать хронологии)

Теперь тренировка со среды 15.07. 4 задачи были совсем простыми, 5-ая была какой-то конструктивной, поэтому я решил сначала подумать над 6-ой. Там был теорвер, что тоже не оч приятно, но я применил +- стандартное уравнение для ТВ и придумал решение за O(nm) времени и памяти с автоматом по КМП. Но, к сожалению, это только 96 баллов, так как авторы поставили ограничения 64 MB (я думаю, что это было сделано специально, так как авторское решение не оч стандартное для ТВ, но об этом позже). После этого я до конца контеста пытался придумать, как оптимайзнуть 6-ую и совсем не думал над 5-ой. Очевидно, что я должен был думать над 5-ой, так как в 6-ой особых продвижений не было. Раз я забываю сам переключаться, то, видимо, придется вернуться к методу "переключение раз в 10-15 минут".

5-ую задачу уже дорешал, думаю, что ее реально было бы придумать, учитывая, сколько у меня было времени, после того как я получил 96 по 6-ой. 6-ую пока не дорешал, так как не оч понимаю один момент, но все остальное (КМП и т.п.) понимаю, поэтому в ближайшее время сдам и ее тоже.

Кроме того с последнего long я хотел дорешать эту задачу https://www.codechef.com/JULY20A/problems/WEIRDMUL, в ней было FFT и техника multi-point evaluation (смысл этой техники в том, чтобы узнавать значения многочлена в нескольких точках одновременно быстрее, чем за квадрат). Для этого я даже разобрал FFT (это оказалось не так уж сложно) и дорешал соответствующую задачу для практики (https://judge.yosupo.jp/problem/convolution_mod). Но сама техника multi-point evaluation требует оч узких математических знаний в модульной арифметике с многочленами, причем я понимаю, что если мне на контесте онлайн нужно будет такое сдать, то все это легко гуглится (и реализации тоже), а на оффлайн контестах для школьников такого не дают, поэтому я решил, что оставлю эту задачу не дорешанной.

Зачем же я тогда изучил FFT?
1) На отборе к миру давали задачу на FFT;
2) Это не такой сложный алгоритм (даже в плане написания кода там строк 20-30);
3) Я нашел очень подробное и простое описание в книге "Алгоритмы", которую я получил за дип на Открытой олимпиаде.

Кроме FFT, в этой книге есть много чего интересного и написано это доступным языком, поэтому я сейчас на нее и налег. Самое интересное обычно это задания после темы, там их обычно штук 30-40 разной степени сложности и мне нравится их решать, так как это не совсем программирование, потому что я должен математически придумать док-во или что-нибудь в этом роде. И частенько в этих заданиях встречаются всякие интересный св-ва, например, у мин остова и дерева кратчайших расстояний из вершины s (если мы говорим про Дейкстру) всегда будет хотя бы одно общее ребро. Такие св-ва могут быть полезны в том плане, что я не буду их доказывать на контесте, а буду использовать сразу.

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

Теперь воскресная тренировка COI_2017. Задачи были такими:
1) какой-то конструктив;
2) сразу же подумал про D&C;
3) Похоже на бит маски;
4) сразу же идея решения с центроидкой.

Из всех задач (кроме 4-ой, которую я сразу придумал), мне больше всего симпатизировала 2-ая, поэтому я и стал над ней думать. Придумал D&C с СНМ-ом и решил, что так как я знаю решение на 2 задачи, то я сначала напишу 2-ую, так как она сложнее, а потом возьмусь за 4-ую, так как ее я смогу сдать быстро. Со 2-ой я веселился аж до +- 3.40 (не помню точно, но вроде я часа 2 писал). И потом +- за час сдал 4-ую. На 1-ую я еще на контесте что-то похожее на решение за куб придумал, но за оставшееся время не успел реализовать. В принципе все задачи на этом контесте были решаемыми, как я понял, проблема была только в том, как все это успеть за 5 часов. Тип в 3-ей задаче вроде тож не оч сложно придумать изломаный профиль, но реализовывать очень больно.

Кроме того написал July Cook-off. Было 8 задач, 5 я смог сдать, не скажу, что это наилучший результат, но +- не плохо. Обидно за штраф, просто я привык, что на Codeforces если ты получаешь WA 1, но тебе не дают минус, а тут, к сожалению, так не работает.

Мой профиль

20 июля

Долги по теории

 Решить и описать решения                                                                   

 2012_1_3. Цифровая строка            ( 2 / 976)   Костяной 
 2017_2_2. Новый факультатив          (17 /  61)   Горбатовский

Текущее состояние в теории (Задано 26 задач)
... дорешать все задачи – до 17 июня - не получилось
Может надо помощь просить, тем у кого не получается.

Решено

             Задачи    ДП 1     ДП 2    Графы   BY_2020
Костяной       20        4        2       6        8
Лосев          18        5        3       4        6
Харрасов       14        5        3                6
Ситников       14        4        1       4        5
Попович        13        6                2        5 
Горбатовский   12        3        0       5        4

Никаких изменений в теории

Текущее состояние в дорешивании воскресных олимпиад (136 задач к дорешиванию)

Решено

Костяной     127 (+ 5)
Попович      125 (+ 9)
Ситников      99 (+ 8)
Лосев         88 (+ 5)
Горбатовский  34 (  0)
Харрасов       7 (  0)

На этой неделе можно попробовать свои силы в Балтийской олимпиаде

From: IOI-announce [mailto:ioi-announce-bounces@lists.ioinformatics.org] On Behalf Of Jevgenijs
Sent: Sunday, July 19, 2020 2:35 PM
To: ioi-announce@lists.ioinformatics.org
Subject: [IOI-announce] BOI online mirror

Dear all,

We are happy to host BOI 2020 online mirror on Codeforces on 22nd and 23rd of July. In the end, there is a 1 day delay, since otherwise the contests would clash with the Codeforces contests.

Please read the full blog post with details on
https://codeforces.com/blog/entry/80321

--
Best wishes,
Jevgenijs Vihrovs,
BOI 2020 organizer

Мой профиль

20-26.07.2020

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

Сначала о дорешке:
1) https://oj.uz/problem/view/COCI16_meksikanac, моя первая задача на FFT, в которой не написано "напишите FFT". Было немного геомы (неприятно, но ладно) и сама идея с FFT очень красивая;
2) https://oj.uz/problem/view/COCI17_klavir, задача на теорвер. На контесте я решал совершенно по-другому, но этот метод тоже оч понятный и красивый;
3) https://oj.uz/problem/view/COI17_ili, задача с COI_2017, не сдал на контесте, так как не хватило времени, а так идея не оч сложная;
4) https://www.codechef.com/problems/TOTEM, задача с последнего cook off. Оказалась оч простой, но на контесте на нее вообще не хватило времени;
5) https://www.codechef.com/problems/EXTREME, задача с последнего cook off. Ее на контесте сдало 2 человека, но мне не составило особого труда ее дорешать самому. Видимо на codechef не оч нужно смотреть на кол-во успешных посылок;
6) https://www.codechef.com/problems/CHEFMOD, задача с последнего cook off. Вот это действительно интересная задача. Нужно было уметь решать уравнение вида a^x = b (mod m), при известных a, b, m. Она решается алгоритмом baby-step-giant-step (умное использование meet-in-the-middle). Для этого я даже сдал задачу (https://judge.yosupo.jp/problem/discrete_logarithm_mod) просто чтобы потренироваться в написании этого алгоритма (кода очень мало). Кроме того нужно было использовать sqrt-эвристику, поиграть с константой (решить уравнение), чтобы получить AC и уметь решать модульное линейное уравнение первого порядка (несложно сводится к расширенному алгоритму Евклида). Короче, оч интересная задача. (на удивление, эту задачу сдало 4 человека, мб просто какая-то идея баянистая)

(об остальной дорешке потом, чтобы не ломать хронологию)

Теперь о контестах:
1) 658 Div 1 CF
Контест сразу не задался из-за того, что когда я написал решение на A2, то я случайно его отправил на A1. Из-за этого штраф за перепосылку + меньше баллов, так как полное решение позже написано. Ну, ладно, про это как-то забыл. Написал B с +. И тут 2-ой неприятный момент: я придумал решение на C почти сразу и у меня было 2 идеи жадника. Одну я написал на контесте и получил WA и совершенно забыл про 2-ую. А 2-ая оказалась фуллом. Эту задача сдал только в дорешке, к сожалению(. Хочу еще дорешать D задачу с этого раунда.
2) тренировка со среды COCI_2016_R1
Сама олимпиада оказалась несложной, но я оч много тупил. Кроме того, обидно, что я не сделал фулл, так как на DL не успел отдебажить 3-ую (я обращался к элементу, которого уже нет).
3) 659 Div 1
Я сдал A очень быстро. Но потом ничего сдать не смог(. На B придумывал решение очень долго, а когда придумал, то получил WA 3, потому что не поставил один if. Ее я уже дорешал. С этого контеста нужно еще хотя бы 2-3 задачи дорешать.
4) Codechef Lunchtime
Этим контестом доволен с большего. Сдал 3 из 5 задач на 100 баллов и одну на 50. Занял итоговое 12-ое место и поднял 2467 рейт (2500 - гросс на Codechef). Планирую дорешать все задачи
5) Воскресный контест COCI_2015_R2
5 задач были простыми (если не учитывать проблем с чекером на 3-ей). А 6-ая была намного сложнее. Я придумывал идею, что можно бить плоскость на решетку с клетками размера (len / 2) (потому что это похоже на задачу с APIO-2018 и на алгоритм нахождения мин расстояния между двумя точками на плоскости), но я не додумался, что для любого массива длины k в нем найдется непустое подмножество, сумма чисел которого делится на k (это можно доказать принципом Дирихле). Думаю, что если бы придумал это, то сдал бы задачу. За то +1 новый прием. Ее я уже сдал в дорешку.

Мой профиль

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

20-26.07.2020

Супер-правильная идея Андрея - отписываться о работе за неделю в воскресенье вечером.
Очень хотелось бы, чтобы все взяли её на вооружение.

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

.

Гомель
Рейтинг Фамилия Имя

2206 Костяной Андрей
2184 Харрасов Антон

2142 Попович Виталий

1916 Кругликов Игорь
1833 Горбатовский Дмитрий
1744 Лосев Александр
1731 Ситников Алексей

Мозырь
Рейтинг Фамилия Имя

2115 Дамасевич Станислав
1882 Полынь Станислав
1825 Кольченко Антон
1695 Никита Черноокий
1627 Булавко Тимофей
1339 Вегера Константин

Всем остальным, включая Антона и Андрея, надо прибавлять!

Теперь о контестах:
И тут 2-ой неприятный момент: я придумал решение на C почти сразу и у меня было 2 идеи жадника. Одну я написал на контесте и получил WA и совершенно забыл про 2-ую. А 2-ая оказалась фуллом.

Даже я знаю из отчётов Андрея, что он должен фиксировать идеи и возвращаться к зафиксированному, в случае необходимости.
Непонятно, почему Андрей не выполняет собственные "написанные кровью" правила.
И, как следствие, наступает на те же грабли.
Одна из важнейших целей подобных отчётов - исключение повторения зафиксированных ошибок.

2) тренировка со среды COCI_2016_R1
Сама олимпиада оказалась несложной, но я оч много тупил.

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

Кроме того, обидно, что я не сделал фулл, так как на DL не успел отдебажить 3-ую (я обращался к элементу, которого уже нет).

Я не понимаю, а на республике/IOI решения с такими ошибками тоже заходят? Только DL их обнаруживает?
Надо на DL менять опции компиляции, чтобы пропускать такие решения?

3) 659 Div 1
Я сдал A очень быстро. Но потом ничего сдать не смог(. На B придумывал решение очень долго, а когда придумал, то получил WA 3, потому что не поставил один if. Ее я уже дорешал.

А про if во время контеста как было сообразить? Ты просто после контеста тест взял и понял про if?
А самому такой тест придумать сложно было?

Огромное спасибо Андрею за отчёты.
Думаю, и ему это очень полезно.
Но важно, что на них могут учиться и те, кто сейчас решают задачи вместе с ним,
и, что ещё более важно, ВСЕ ПОСЛЕДУЮЩИЕ поколения школьников.

Мой профиль

27 июля

Долги по теории

 Решить и описать решения                                                                   

 2012_1_3. Цифровая строка            ( 2 / 976)   Костяной 
 2017_2_2. Новый факультатив          (17 /  61)   Горбатовский

Текущее состояние в теории (Задано 26 задач)
... дорешать все задачи – до 17 июня - не получилось
Может надо помощь просить, тем у кого не получается.

Решено

             Задачи    ДП 1     ДП 2    Графы   BY_2020
Костяной       20        4        2       6        8
Лосев          18        5        3       4        6
Харрасов       14        5        3                6
Ситников       14        4        1       4        5
Попович        13        6                2        5 
Горбатовский   12        3        0       5        4

Никаких изменений в теории

Текущее состояние в дорешивании воскресных олимпиад (148 задач к дорешиванию)

Решено

Костяной     138 (+11)
Попович      132 (+ 7)
Лосев        100 (+12)
Ситников     100 (+ 1)
Горбатовский  34 (  0)
Харрасов       7 (  0)

Мой профиль

Что касается того, что я забываю писать про идеи. Я уже записываю >80% идей точно, но все равно иногда об этом забываю. Но каждый раз, когда я на это натыкаюсь, я начинаю записывать ещё больше. Поэтому к IOI я уже полностью разберусь с этой проблемой

Мой профиль

К началу IOI страницы не будет хватать для записи идей

______________________
Жизнь - игра. Сюжет - так себе, но графика потрясающая.

Мой профиль

27.07-02.08

Как я и говорил, у меня накопилось много дорешки, поэтому я в первую очередь разбирался с ней:
1) https://www.codechef.com/problems/COPAIR, задача с последнего lunchtime. Я еще на контесте придумал, что там корневая эвристика, но кроме того там нужно было еще много чего (как например для корневой написать корневую

). Приятно было реализовать такое;
2) https://www.codechef.com/problems/POFP, задача с последнего lunchtime. Прикольная задача на ДП, думаю, что не сдал на контесте, так как писал частичное на COPAIR (на все не хватило времени);
3) https://codeforces.com/contest/1383/problem/C, задача просто с одной МЕГА конструктивной идеей. Если ее придумать, то дальше все просто;
4) https://codeforces.com/contest/1383/problem/D, тож конструктивчик, но по мне попроще и красивее;
5) https://codeforces.com/contest/1383/submission/88615026, оч красивое ДП (нужно придумать, как уникально задавать какую-либо строку с помощью набора операций, если это придумать, то дальше не сложно)
6) https://codeforces.com/contest/1381/problem/D, красивая задача на деревья, нужно догадаться об одной штуке и доказать пару несложных утверждений (которые почти следуют из свойств этой нашей штуки) и придумать красивый ход с подвешиванием дерева за интересную вершину и "жадным" движением змейки. Написано тут много всего, конечно, но если придумать ключевую идею, то остальное не так сложно;

(про остальную дорешку напишу дальше, чтобы не нарушать хронологии)

Теперь контесты:
1) контест со среды COCI_2015_R3. 5 задач были простыми, а вот в 6-ой пришлось подумать. Я сразу придумал min-cost-max-flow, но ограничения задачи были слишком большими. А потом я понял, что можно оставлять только интересные состояния, а их мало, а значит я могу применить min-cost-max-flow. Интересно, что авторы решали эту задачу с помощью meet-in-the-middle за экспоненциальное время (странно, что они не придумали мою идею, так как она намного проще и быстрее);
2) Educational 92. Писал контест я после тренировки COCI и был довольно уставшим (не знаю, с чем это связано, так как перед контестом я вроде как выспался). На самом контесте выступил не оч, сдал A,C,D. Не написал B, потому что хотел потом к ней вернуться, но до конца контеста по итогу не успел сдать F (которую успешно сдал в дорешку). Кроме того +- сам придумал G, думаю, что мог бы сдать на контесте, если бы было больше времени. Все задачи уже дорешал;
3) 660 CF Div 2 На контесте было 4 простые задачи и 5-ая геометрия (я что-то придумал, но это по итогу ломалось). По итогу решение довольно замудреное (ну, или мне так кажется), поэтому в ближайшее время я ее сдавать не собираюсь;
4) Так как я все, что хотел, дорешал, то я написал 1-ый день BOI. Набрали я такие баллы:

67 0 39

С А задачей я более менее доволен (к 100 баллам я был не близко, как я понял)
C B задачей (по которой у меня 0), я тоже не оч расстроен, так как она сводилась к геометрии, а геометрию на IOI не дают (конкретно такую точно, так как там были выпуклая оболочка и ССД с сортировкой по углу)
Больше всего я расстроился из-за C задачи:
а) Я не успел до конца контеста отдебажить на 49 баллов, по итогу нужно было удалить одну строчку, а так как эти 10 баллов я пытался получить в последние 20 минут, то мне просто не хватило времени найти ошибку;
б) Из-за этого обиднее даже больше. Еще на контесте я придумал идею, что можно использовать D&C (который как в оптимизации ДП) и для него можно было бы написать СНМ с откатами. Мне оставалось додумать совсем чуть-чуть до 100 баллов, но я отказался от этой идеи и пошел добирать частичные по другим задачам. По итогу моя идея была точь-в-точь написана в разборе. Почему же я не додумал на контесте? Потому что я испугался. Я понимал, что контест сложный и мне казалось невозможным, что я могу придумать такую задачу (по итогу на официальном соревновании ее никто не сдал). Видимо, мне нужно просто выбрасывать такие мысли из головы, так как база у меня уже довольно большая и я вполне способен (как видно на примере) придумывать такие задачи.

Хоть и кажется, что баллов у меня мало, но 1-ый день был довольно сложным, поэтому в общей таблице я смотрюсь относительно не плохо.

В ближайшее время хочу дорешать A и С, пока не уверен насчет B.

5) воскресная тренировка COCI_2015_R4. Контест был довольно простым (меня заставила прям посидеть-подумать только 6-ая задача), закрыл за 2 часа 37 минут.