[Logo] Форум DL
  [DL]  Back to home page 
Forum Index ->Олимпиадное программирование ->Тактика на командных олимпиадах 1, 2, 3, 4
Author Message
Mihail Dolinskiy

Topics: 1737
Messages: 40954

My Profile
Хорошо бы Поповичу и Горбатовскому сдать хотя бы эти задачи

В скобках – кто сдал (Лосев, Попович, Горбатовский, Подгорный,Бортенко, Брель, Ермаков)

ДП
20_H. Тяжкий труд                         - ДП по числу                                               (Ло)
19_G. Слишком много минусов               - ДП по строке                                              (Ло)
19_L. Путешествия во времени              - ДП по дереву                                              (Ло, Бо, Под, Бр)
17_J. Развлечение с копьями               - ДП по двум параметрам (Ло, Го)
16_C. Горные лыжи                         - сортировка, дп по одному параметру, восстановление ответа (Ло,Под,Бо)
15_C. demo                                - максимум на массиве в движущемся окне, ДП, очередь        (Ло,Го,Поп)
15_E. duty                                - формула или ДП                                            (Ло,Под,Бо,Бр)
12_F. kitten                              - ДП по трём параметрам                                     (Ло,Поп,Гор)
11_E. parade                              - ДП по одному параметру BFS                                (Ло,Поп,Гор,Бо)
09_J. Цирковое шоу                        - ДП по трём параметрам                                     (Ло,Поп)

Сложные структуры данных
18_C. Новогодние подарки                  - хеш-таблица, два указателя                                (Ло,Под,Бо,Бр)
18_G. Комбокамень                         - персистентное дерево отрезков                             (Ло,Поп)
18_J. Два префикса                        - префикс-функция                                           (Ло,Поп)
18_K. Расширение сознания вправо          - классы эквивалентности,С++ map<pair<string,int>,vector<int>> (Ло,Го,Под,Бо,Бр)
16_E. Расшифровка ДНК                     - бор                                                       (Ло)
15_K. robot                               - два указателя                                             (Ло,Поп)
12_C. exam                                - стек убывающих элементов                                  (Ло,Поп,Гор)
10_F. party                               - метод событий, декартово дерево(или два дерева отрезков)  (Ло,Поп,Под)
10_H. ring                                - два указателя                                             (Ло)
09_B. Соревнования по программированию    - хеши для сравнения строк                                  (Ло)
08_C. codes                               - сортировка (или бор, или хеши)                            (Ло,Поп,Бо)

Графы
20_С. Проверка маркеров                   - скрытый граф, паросочетание                               (Ло)
20_E. Пранк в IKEA                        - скрытый граф, максимальное независимое множество          (Ло) 
20_G. Приготовление еды                   - скрытый граф, максимальный поток минимальной стоимости    (Ло)
20_I. Точки и отрезки – интерактивная     - скрытый граф, Формула Эйлера для графов, четность числа рёбер (Ло)
20_K. Новый уровень                       - графы, СНМ, С++set                                        (Ло)
19_D. Угадай путь                         - интерактивная – разделяй и властвуй                       (Ло, Бр)
19_J. На заводе                           - двудольный граф, специальный алгоритм                     (никто)
18_E. Конный спорт                        - скрытый граф, гамильтонов путь, рекурсия                  (Ло,Го,По)
18_H. Линеаризация                        - скрытый граф, рекурсия                                    (Ло,Поп) 
17_I. Электрическая цепь                  - граф, C++ MAP, очередь                                    (Ло)
16_J. Полиглоты-интроверты                - скрытый граф, Флойд                                       (Ло, Бо)
14_B. coins                               - скрытый граф, Эйлеров цикл, перебор                       (Ло,Поп,Го)
14_K. zoo                                 - граф                                                      (Ло,Поп,Бо)
13_A. binary                              - z-функция, скрытый граф, DFS                              (Ло,Поп,Бр) 
13_C. dwarfs                              - дерево, BFS                                               (Ло,Поп,Под,Бо,Бр) 
13_J. travel                              - граф, BFS 0-1/Дейкстра                                    (Ло,Поп)
10_K. snake                               - скрытый граф                                              (Ло)
09_A. Поедание сыра                       - поток в специальной сети, бинпоиск по ответу              (Ло,Поп,Го)

Gomel: 2048 manulov

Topics: 1
Messages: 33

My Profile
отбор ВКОШП 2017

Саша    - C, H, J, K
Виталик -    D, E, F, G
Дима    - A, D,    F, I


A +
C +6 ( неверно расписал один случай и несколько попыток потратил для исследования, в каком тесте у меня падало)
D +
E +
F +1 (немного не так поняли условие)
G +
H +2 (когда начиналась новая ночь, у меня недосып мог уйти в минус, чего не должно было быть)
I +1 (ограничения)
J +7 (изначально не правильно поняли условие, позже - не прибавлял длину слова к длине твинта, когда двигал указатель)
K +
Mihail Dolinskiy

Topics: 1737
Messages: 40954

My Profile
По сути вы большие молодцы
Результаты отбора 2017 года
Федя вне конкурса решил те же 10 задач
Гомель-1 (Титенок, Процкий, Кадушко) - 8, так они же и медаль на ВКОШП потом взяли.

Немножко критики

По оформлению

Надо тег PRE ставить, чтобы было как набирали
Саша    - C, H, J, K
Виталик -    D, E, F, G
Дима    - A, D,    F, I


Мне кажется, лучше и попытки там же отражать, так например

Саша    - C+6, H+2, J+1, K  = 9 лишних остылок
Виталик -    D, E, F+1, G   = 1
Дима    - A, D,    F+1, I+1 = 2


По содержанию

Получается по лишним попыткам Саша - рекордсмен.
Саша, надо с этим делать что-то.
Gomel: 2048 manulov

Topics: 1
Messages: 33

My Profile
Отбор на ВКОШП 2015

Саша    - A, D, E, G, H, K 
Виталик - B, C, F, I, J

A +3 (проблема с тестом, когда n = 1)
B +21 (большинство попыток было с багой в виде того, что мы могли удалить потенциального кандидата на ответ)
С +1 (баги в формулах)
D +
E +5 (когда n mod m = 0 я выводил 0, а не n)
F +
G +
H +2 (все две посылки - это лишние посылки медленного и затратного по памяти солва)
I +
J +1 (не учел один случай)
K +1 (ограничения не те поставил для одного массива)
Mihail Dolinskiy

Topics: 1737
Messages: 40954

My Profile
1. Решили все задачи
2. Последнюю сдали "на флажке"
Это всё очень круто

Про попытки давайте так
Саша    - A+3, B+21, D, E+5, G+, H+2, K+1 = 11 
Виталик -      B+21, C+1, F, I, J+1      =   2
                                          B+21 - общие?

Саша = 11 лишних отсылок.
Что ты придумал, чтобы уменьшить их количество?
Gomel: 2048 manulov

Topics: 1
Messages: 33

My Profile
Отбор на ВКОШП 2014

Саша    - А + , D + , F +1, J +1
Виталик - G + , H + , K +4
Дима    - B +1, C +3, E +


B - одну лишнюю фигуру выводил
С - бага в условии переходов для медленного ДП
F - искал простые делители для a * b / (gcd ^ 2), а не для a / gcd и b / gcd по отдельности, из-за этого брало TL
J - неверный индекс в сет добавлял
K - не учел один случай


Mihail Dolinskiy

Topics: 1737
Messages: 40954

My Profile
From: Michael Dolinsky
Sent: Monday, September 13, 2021 5:08 AM
To: 'Лосев Саша'
Cc: 'Виталий Попович'; 'Дмитрий Горбатовский'
Subject: RE: Заключительная бага в I

То, что дорешал – здорово.
То, что не сдали во время олимпиады – безобразие.
Виталий и Дима – это к Вам упрёк в большей степени.
Надо работать до конца олимпиады.
И не расслабляться во время олимпиады, как бы хорошо не складывались у Вас дела. 


From: Лосев Саша
Subject: Заключительная бага в I

Дома я дорешал I с первой попытки
Ошибка была далеко не в геометрических формулах, а в том, какое расстояние надо прибавить, если идем по такому ребру.  
Gomel: 2048 manulov

Topics: 1
Messages: 33

My Profile
Отбор на ВКОШП 2013

Саша    - B + , C +, E + , F +, H +7 = 7
Виталик - A +2, D +, J +3            = 5


A - лонги
H - пару попыток - это слет на семплах, остальные - считал, что для четных длин числа не более 4 хороших чисел(через брут через троичные маски выяснилось, что это не так)
J - количество символов в строке принимали за n, а в столбце - за m

Очень долго исправляли баги на легких задачах, в следствие чего не успели сдать таску G, в коде которой в одной строчке была бага
Gomel: 2048 manulov

Topics: 1
Messages: 33

My Profile
Отбор ко ВКОШП 2012

Саша    - C + , D +, F +4, H +, I +3 = 7
Виталик - G +2, J +2                 = 4
Дима    - A + , B +, E +3            = 3

E - кривая реализация идеи
F - одна проверочная посылка, три посылки были с неверным выводом для больших ограничений
G - когда пары для левых и правых частей строки совпадали, то мы могли бы свапнуть две половины строки и получить верный ответ
J - считали ответ для единичной окружности, а не для окружности с радиусом r
Gomel: 2048 manulov

Topics: 1
Messages: 33

My Profile
4-ая Питерская 2018-2019 усложненная
Саша    - D +4 , E +10, F +5,        = 9
Виталик - E +10, H  +1, J +          = 1
Дима    - A +3 , C   +, E +10, G +1  = 4


А - лонги в больших массивах
D - не учел случай, когда челикам надо было выйти на первом этаже
Е - неверно сортили точки, смежные ребром с вершиной v
F - переполнение и 0 на 1 поменять надо было в одном месте
G - даблы вместо лонгов надо было ставить
H - не учел один случай
Gomel: 2048 manulov

Topics: 1
Messages: 33

My Profile
19 Rup2

Саша - B +, D +2, F +2, H +1 = 5 
Дима - A +, B  +, G +3,      = 3


D - неверно понял условие
F - поставил не те ограничения
G - проверяли брут, который оказался неверным
H - вводил (n, m, k), а надо было (n, k, m)
Gomel: 2048 manulov

Topics: 1
Messages: 33

My Profile
19 Rup3

Саша    - A + , B +5, D +1, E +2, H +, J +2 = 5
Виталик - B +5, E +2, K +2                  = 2


B - изначально написали вроде как верную идею(судя по разбору), потом придумали другую и в ней была одна бага, что если вес одинаковый, то сортили по предкам
D - вместо символа ставил код символа в строку
E - сначала заслали код с одним хешом для префикса, потом написали три хеша
J - неверно пересчитывал преф суммы
K - надо было выводить в виде ПСП, а выводили как хотели
Gomel: 2048 manulov

Topics: 1
Messages: 33

My Profile
19 Rup4

Саша - B +8, D +1, E +1, F +, G +2, H +4, I +1 = 17

B - изначально неверно перефразировал задачу, потом неправильно сортил подстроки длиной k - 2
D - не тот модуль поставил
E - забыл лонги
G - при добавлении вершины в сет, не удалял прошлую копию вершины со старым dst[v]
H - одна посылка с неверной идеей, остальные - проверка медленного решения
I - не рассмотрел случай
Gomel: 2048 manulov

Topics: 1
Messages: 33

My Profile
Отбор на ВКОШП 2021

Саша    - D +, E + , H +7, J +, K + = 7
Виталик - A +, B +5, C + , I +      = 5


B +5 - нашли противоречие в условии и дизориентировались в ограничениях
H +7 - сначала заслали просто алгоритм Евклида, который не зашел на тестах с числами Фибоначчи + выясняли, почему WA на 27ом тесте + 2 лишние посылки с WA на втором семпле

Придумали правильно F, но ошибка оказалась не в подсчете ответа, а в погрешности(eps)

Gomel: 2048 manulov

Topics: 1
Messages: 33

My Profile
20 Rup3

Саша    - A +,   F +1, G +,  H +9, I + = 10
Виталик - B +10, D +1, E +1, J +       = 12
Дима    - G +


B - надо было писать очередь, а не рекурсию, как писали изначально. Много посылок было, тк пытались сделать костыль "когда TL, выводи -1" и подбирали константу под TL(к удивлению, она не равна TL в самой задаче)
D - писал код для нулевой индексации, а номера челов были индексированы с 1, а не с 0
E - не проверял блок, который оканчивался последним символом строки/слобца
F - брал первые min(|a|, |b|), а не первые |a| символов, как было сказано в условии
H - неверно проверял касание двух отрезков через векторное произведение

Очередь или рекурсия? Вот в чем вопрос!
1) если в задаче всегда существует ответ, то берем очередь, так как рекурсия может зайти не в ту ветвь и уйти далеко и надолго
2) оценить память для очереди(максимальная ширина дерева обхода), если много затрат по памяти - рекурсия
3) оценить глубину рекурсии, если слишком глубокая - очередь
4) чтобы оценить пункт 2 и пункт 3, надо взять семплы и придумать несколько тестов, чтобы найти закономерность в глубине/ширине.

Для задачи В:
Тк после переливания у нас всегда найдется пустой или полный бак, то состояние в очереди/рекурсии можно описать в виде:
1) номер текущего бака (3)
2) пустой он или полный (2)
3) номер другого бака (2)
4) объем бака из пункта 3 (1е6)
В итоге получается 3 * 2 * 2 * 1е6 вариантов состояний. То есть макс глубина равняется 12 * 1е6, что очень плохо по времени из-за размера стека, а для очереди память оценивается в линейное количество состояний, то есть O(12 * 1е6), что равно 46 МБ
 
Forum Index ->Олимпиадное программирование ->Тактика на командных олимпиадах 1, 2, 3, 4
Time:0,047