Автор |
Сообщение |
20.08.2021 15:58:52
Тема: Re:Гомель: 2048 манулов
|
Михаил Долинский
Темы: 1984
Сообщений: 47247
Мой профиль
|
Хорошо бы Поповичу и Горбатовскому сдать хотя бы эти задачи
В скобках – кто сдал (Лосев, Попович, Горбатовский, Подгорный,Бортенко, Брель, Ермаков)
ДП
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. Поедание сыра - поток в специальной сети, бинпоиск по ответу (Ло,Поп,Го)
|
02.09.2021 14:14:21
Тема: Re:Гомель: 2048 манулов
|
Гомель: 2048 манулов
Темы: 1
Сообщений: 35
Мой профиль
|
отбор ВКОШП 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 +
|
02.09.2021 15:41:42
Тема: Re:Гомель: 2048 манулов
|
Михаил Долинский
Темы: 1984
Сообщений: 47247
Мой профиль
|
По сути вы большие молодцы
Результаты отбора 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
По содержанию
Получается по лишним попыткам Саша - рекордсмен.
Саша, надо с этим делать что-то.
|
06.09.2021 07:57:13
Тема: Re:Гомель: 2048 манулов
|
Гомель: 2048 манулов
Темы: 1
Сообщений: 35
Мой профиль
|
Отбор на ВКОШП 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 (ограничения не те поставил для одного массива)
|
06.09.2021 16:33:31
Тема: Re:Гомель: 2048 манулов
|
Михаил Долинский
Темы: 1984
Сообщений: 47247
Мой профиль
|
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 лишних отсылок.
Что ты придумал, чтобы уменьшить их количество?
|
13.09.2021 10:56:55
Тема: Re:Гомель: 2048 манулов
|
Гомель: 2048 манулов
Темы: 1
Сообщений: 35
Мой профиль
|
Отбор на ВКОШП 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 - не учел один случай
|
14.09.2021 06:22:48
Тема: Re:Гомель: 2048 манулов
|
Михаил Долинский
Темы: 1984
Сообщений: 47247
Мой профиль
|
From: Michael Dolinsky
Sent: Monday, September 13, 2021 5:08 AM
To: 'Лосев Саша'
Cc: 'Виталий Попович'; 'Дмитрий Горбатовский'
Subject: RE: Заключительная бага в I
То, что дорешал – здорово.
То, что не сдали во время олимпиады – безобразие.
Виталий и Дима – это к Вам упрёк в большей степени.
Надо работать до конца олимпиады.
И не расслабляться во время олимпиады, как бы хорошо не складывались у Вас дела.
From: Лосев Саша
Subject: Заключительная бага в I
Дома я дорешал I с первой попытки
Ошибка была далеко не в геометрических формулах, а в том, какое расстояние надо прибавить, если идем по такому ребру.
|
20.09.2021 11:19:04
Тема: Re:Гомель: 2048 манулов
|
Гомель: 2048 манулов
Темы: 1
Сообщений: 35
Мой профиль
|
Отбор на ВКОШП 2013
Саша - B + , C +, E + , F +, H +7 = 7
Виталик - A +2, D +, J +3 = 5
A - лонги
H - пару попыток - это слет на семплах, остальные - считал, что для четных длин числа не более 4 хороших чисел(через брут через троичные маски выяснилось, что это не так)
J - количество символов в строке принимали за n, а в столбце - за m
Очень долго исправляли баги на легких задачах, в следствие чего не успели сдать таску G, в коде которой в одной строчке была бага
|
27.09.2021 16:46:47
Тема: Re:Гомель: 2048 манулов
|
Гомель: 2048 манулов
Темы: 1
Сообщений: 35
Мой профиль
|
Отбор ко ВКОШП 2012
Саша - C + , D +, F +4, H +, I +3 = 7
Виталик - G +2, J +2 = 4
Дима - A + , B +, E +3 = 3
E - кривая реализация идеи
F - одна проверочная посылка, три посылки были с неверным выводом для больших ограничений
G - когда пары для левых и правых частей строки совпадали, то мы могли бы свапнуть две половины строки и получить верный ответ
J - считали ответ для единичной окружности, а не для окружности с радиусом r
|
04.10.2021 12:43:30
Тема: Re:Гомель: 2048 манулов
|
Гомель: 2048 манулов
Темы: 1
Сообщений: 35
Мой профиль
|
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 - не учел один случай
|
12.10.2021 19:52:52
Тема: Re:Гомель: 2048 манулов
|
Гомель: 2048 манулов
Темы: 1
Сообщений: 35
Мой профиль
|
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)
|
18.10.2021 08:20:35
Тема: Re:Гомель: 2048 манулов
|
Гомель: 2048 манулов
Темы: 1
Сообщений: 35
Мой профиль
|
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 - надо было выводить в виде ПСП, а выводили как хотели
|
24.10.2021 17:08:13
Тема: Re:Гомель: 2048 манулов
|
Гомель: 2048 манулов
Темы: 1
Сообщений: 35
Мой профиль
|
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 - не рассмотрел случай
|
15.11.2021 11:12:44
Тема: Re:Гомель: 2048 манулов
|
Гомель: 2048 манулов
Темы: 1
Сообщений: 35
Мой профиль
|
Отбор на ВКОШП 2021
Саша - D +, E + , H +7, J +, K + = 7
Виталик - A +, B +5, C + , I + = 5
B +5 - нашли противоречие в условии и дизориентировались в ограничениях
H +7 - сначала заслали просто алгоритм Евклида, который не зашел на тестах с числами Фибоначчи + выясняли, почему WA на 27ом тесте + 2 лишние посылки с WA на втором семпле
Придумали правильно F, но ошибка оказалась не в подсчете ответа, а в погрешности(eps)
|
24.11.2021 07:50:54
Тема: Re:Гомель: 2048 манулов
|
Гомель: 2048 манулов
Темы: 1
Сообщений: 35
Мой профиль
|
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 МБ
|
|
|