Форум DL

Мой профиль

Кодировщики Паша, Антон.
Алгоритмизатор Лёша.

Паша : B+ F+
Антон : C+ D+ E+

0. Все приходят вовремя
1. 1-2 простые решаем в произвольном порядке
2. Лёша оценивает сложность реализации задачи Антоном и Пашей
3. Смотрим в монитор (при посадке на комп и при уходе с компа)
4. При поручении задач кодерам Лёша учитывает индивидуальность.
5. Перед выслушиванием алгоритма кодер читает задачу и если есть время придумывает решение
6. Если задача не сдаётся кодер берёт минут 10 или сдать или понять в чём проблема или оценить сколько времени ему понадобится
7. Если через 10 минут видимого прогресса нет, - исходник распечатывается, машина освобождается
8. Если ещё через 10 минут задача не сдана см. пункт 7.

Предпочтительные темы
Паша
- Математика

Антон
- ДП
- Сложные структуры данных

Довести до ума
Паша
-

Антон
- Деревья (максимумов минимумов отрезков сумм ...)
- Декартово дерево

Дорешать
Паша : A H G
Антон : I J G

Мой профиль

Дорешал A H

Мой профиль

Дорешать задачи A B E H I J
Разобраться с точность

Мой профиль

Математика на потом(кроме a+b).
Фиксация ключевых точек задачи перед её реализацией.
Порядок решения определяется заранее Капитаном.
Капитан управляет перемещением кодеров между столом и компьютером.
Беречь время.
Следить за монитором, сообщать капитану.
Кодировать аккуратнее.
Приходить вовремя.

Мой профиль

Список тем, нужных для решения задач на минском четвертьфинале ICPC этого года:

структуры данных (очередь, бор)
графы (обычные, двудольные)
циклы
BFS
meet-in-the-middle
битовые маски
ДП
поиск подстроки (как минимум КМП)
геометрия (2D, 3D)
дихотомия, трихотомия
градиентный спуск
быстрое возведение в целую степень
алгебраические преобразования
теория чисел
симуляция (аккуратная)
разбиение на подзадачи
симплекс-подход
жадный подход

Другие темы для изучения:

графы (деревья, скрытые, компоненты, Эйлеров цикл)
максимальный поток (паросочетания)
минимальное остовное дерево
поиск пути
DFS, топологическая сортировка
рекурсия (обычная, с меморизацией)
LCA
ДП (по дереву, по (ломаному) профилю, на строках, по маске, )
комбинаторика
решето Эратосфена (обычное, двойное, функция Эйлера)
работа с дробями, логарифмы
теория вероятности
системы счисления, битовые операции
длинная арифметика, арифметика по модулю
матрицы (операции, алгоритмы)
геометрия (сжатие координат, диаграмма Вороного)
стратегические игры (функция Гранди)
структуры данных (стек, бесконечная очередь, список (односвязный, двусвязный), бинарная куча,
BIT, бинарное дерево (1D, 2D, 3D), сортировочное дерево)
сортировка (N^2, Bin, Merge)
хеш (функции, таблицы)
парсинг, даты, римские числа
перебор (скользящее окно)
метод Монте-Карло

______________________
// LeX

Мой профиль

Отчёт о выступлении команды на ICPC NEE4W этого года

На олимпиаде я с самого начала приступил к чтению задач, часть задач читали они; первая обнаруженная простая задача (C, на BFS) пошла к Павлу на написание. С ней он справился быстро.
Ко времени, когда он закончил, я нашёл ещё одну простую задачу (F, на симуляцию) и выдал ему. С ней он справился быстро, как и с первой.
Когда он написал вторую, у меня была в наличии (найдена, но не сдана нами) только одна простая задача (H, римское исчисление). Хотя римских чисел они почему-то боялись, задача была предельно проста; так что я объяснил им простейшее решение задачи и отправил их вдвоём писать её (фактически, сложность была лишь в расчёте длины числа в римской записи). Сам же я занялся дочитыванием условий (непрочтёнными оставалось три задачи из дюжины).
Тем не менее, мне приходилось часто отвлекаться, чтобы контролировать процесс отладки. Так что прочёл я лишь одну задачу из трёх (L), плюс ещё 2 абзаца второй (помню это точно, т.к. в течение получаса безуспешно пытался вернуться к прочтению с этого места).
Когда задача была дописана и сдана, они обратились ко мне за новой. Простейшей из прочтённых была задача D (для решения нужно было знать только бор). Поскольку в большинстве остальных требовалось возиться с математикой, я отдал её Антону (предварительно спросив, сможет ли он реализовать рабочий бор); Павлу же выдал задачу на стереометрию (E), описал задачу (вкратце) и предложил ему сделать расчёт для примеров в условии. Сам же вернулся к чтению.
Ответ у него не сошёлся. Я объяснил ему условие подробно и попытался вернуться к чтению. Затем мне пришло в голову, каким образом в тесте может получиться такой ответ, и я объяснил это Павлу; тот заявил, что я рассказал ему условие неправильно (в первый раз я объяснил упрощённое условие, но сделал это для проверки предполагаемого решения; во второй же рассказал ему полное условие). Задачи я читал внимательно, чтобы не было проблем с "неправильным переводом" (как случалось в прошлые годы), так что здесь проблемы не было.
Я дочитал одну задачу и собирался заняться второй. Павел заявил, что ответ не сходится (судя по тому, что он бормотал в процессе, он дифференцировал исходную формулу). Далее он начал перепроверять выкладки, пытаясь привлечь к процессу меня; я отказался, так как был занят другими задачами (прочтением последней и анализом остальных). Предложил ему вывести значение для первого теста (что не помогло), затем сказал, что лучше здесь использовать трихотомию (нужно было найти максимум для функции по параметру).
Я предложил ему две задачи на алгебраический расчёт. Одной (I) он испугался, поэтому задумываться не стал, вторая (L) требовала более подробного анализа, но он сказал, что встречал раньше что-то подобное (как я, собственно, и предполагал), и занялся расчётом.

продолжение ниже…

______________________
// LeX

Мой профиль

…продолжение

Пока он был занят, я дочитал последнюю задачу (примерно к середине олимпиады) и приступил к сравнению сложности нахождения решений; Антон к тому времени явно закончил писать код и перешёл к отладке. Павел сказал, что ничего не выводится, и спросил, нет ли задач попроще. Я объяснил ему условия оставшихся задач (для верности: если бы я случайно пропустил что-то элементарное, он бы это заметил), после чего занял его предпоследней прочтённой (J); сам же я вернулся к сравнению.
Вскоре он заявил, что задача сложная (впоследствии, на разборе, я пришёл к выводу, что если бы у меня было время заняться ею вплотную, то решение я нашёл бы без особых проблем); я дал ему последнюю прочтённую задачу (K) и описал ему решение (расчёт подзадач, затем расчёт основной задачи). Единственную сложность представлял собой поиск функции сравнения для сортировки (расчёт требовал жадного подхода), однако жадник был из простейших, так что я предложил ему две наиболее вероятные в подобной задаче функции сравнения и предложил проверить их. Сам же в это время вернулся к первым двум задачам; обе имели решение, простое в реализации, и одна из них (B) была потенциально простейшей из оставшихся (на разборе я пришёл к выводу, что не ошибся).
Павел быстро определил, что вторая из предложенных функций подходит, и после одобрения его обоснования (с жадным подходом иначе нельзя) сменил Антона за компьютером (тот отправил свой код на распечатку). Я взглянул на составленный мною список задач и пришёл к выводу, что шесть-семь для нас сдать было бы вполне реально. Далее я собирался вернуться к добиванию почти-составленных-решений (наиболее простых из оставшихся), но Антон обратился ко мне за помощью в проверке его кода.
Проверка дала неожиданные результаты. "Здесь я добавляю строку в бор" – сказал он, указывая на первую функцию и явно собрался перейти ко второй. Однако я остановил его, увидев непривычную реализацию. При ближайшем рассмотрении я пришёл к выводу, что в его боре хранится только последнее добавленное слово. Я уточнил, действительно ли он знает бор, и сказал ему, что добавление делается не так. Он начал объяснять мне, как работает его добавление (при этом я понял только, что к бору его объяснение никакого отношения явно не имеет). Объяснил ему, как реализую это я, и несколько раз указал на место явного различия (условный оператор, который у него попросту отсутствовал). Зачеркнул тело процедуры и продиктовал правильное; он несколько раз пытался убедить меня, что для добавления вершины нужно знать родителя её родителя (что есть явный бред).
Указал ему на лишний массив (информацию о наличии дуги по букве проще хранить в массиве с дугами - 0 для отсутствующих); сказал, что помимо этого в вершине нужно хранить только булевскую метку, говорящую, является ли вершина терминальной. Взглянул на остальной код и пришёл к выводу, что алгоритмических ошибок нет (об остальном трудно судить до переписания кода).
Павел дописал задачу, проверил её работу на примерах из условия и отправил на тестирование. Задача не прошла 3-й тест (WA). После незначительных правок - 45-й (RE). Он распечатал код и поменялся с Антоном (тот стал переписывать свою задачу). К анализу кода снова был привлечён я.
Проверив код Павла, алгоритмических ошибок я не нашёл. Пришлось анализировать используемые типы на предмет необходимой размерности. В итоге расчёт показал, что в одном месте наибольшее значение превышает ограничение типа (4-байтовое целое там, где нужно 8-байтовое). Он переделал решение; задача упала на 55-м тесте (RE). Я повторил анализ и нашёл ещё одно тонкое место, однако изменение кода на результат тестирования не повлияло.
Проверяя результаты расчётов, я случайно заметил, что константа-ограничение была меньше, чем в условии(!). Как оказалось, Павел и не думал выписывать константы из условия, вводя их по памяти. Объяснив ему, что так делать не надо, я отправил его исправлять "опечатку". Задача прошла.
До конца олимпиады оставалось полчаса. Я пришёл к выводу, что на придумывание ещё одного решения времени недостаточно, и решил помогать в отладке Антону.
Исправляя найденные ошибки в реализации, мы получали ещё более неправильные результаты. Как оказалось, виной тому была весьма неожиданная особенность его реализации бора: вершины-листья он не хранил. Почему Антон реализовал бор именно так, я так и не понял (хотя понял, почему ему хотелось знать родителя родителя добавляемой вершины).
К сожалению, когда я обнаружил проблему, до конца олимпиады оставалось десять минут. По моей оценке, изменение кода для нормального бора заняло бы не более пяти минут (что оставляло бы ещё пять на отладку), однако они на два голоса начали убеждать меня в том, что на переписывание уйдёт слишком много времени и нужно отлаживать то, что есть. Я честно попытался, но через 5 минут пришёл к выводу, что изменение бора, вносимое реализацией Антона, усложняет его работу в разы, так что на разбор его кода у меня уйдёт как минимум четверть часа (которой у нас не было).
Поскольку времени на приведение бора в нормальный вид (и убеждение их в том, что так надо) уже не хватало, я предоставил Антону разбираться с его кодом самому, давая только общие указания (что-то ещё требовало более подробного разбора его кода). Конечно, я пробовал предлагать и изменения (основанные на принципе работы нормального бора и разобранной мной части кода Антона), но их эффект был хаотическим и пользы они не принесли.
______________________
// LeX

Мой профиль

Сочинение на тему "почему уровень моей команды гораздо ниже моего"

Основной проблемой моей команды является недостаток самостоятельности участников. Это является прямым следствием того, что они занимаются исключительно по воскресеньям, на тренировочных олимпиадах (правда, Антон иногда приходит по субботам на лекции по теории и методам). Дома они не занимаются, и самостоятельно задачи не решают.
Как следствие, они не могут отлаживать код сложных задач (также иногда просят, чтобы я диктовал им код). Методы, которыми они раньше не пользовались, они реализуют плохо (и вообще избегают это делать), а известные им теоретически не умеют грамотно переводить в код (оптимизируют где попало, что, в лучшем случае, усложняет работу – а значит, и отладку – алгоритма); что, в свою очередь, сводит на нет развитие их навыков.
Вообще, важность отладки они серьёзно недооценивают, упирая на скорость написания кода (поэтому мне нередко приходится отлаживать поспешно набранный код сложной задачи).
Сам я тоже не занимаюсь регулярной сдачей задач, однако, в отличие от них, имею наработанные навыки (полученные вследствие тренировок ещё в школе), позволяющие выполнять вышеописанные действия гораздо лучше, чем они.
Теоретически, я должен работать за компьютером медленнее всех в команде, т.к. часто останавливаюсь, задумываясь над дальнейшим кодом (потому что стараюсь писать код с минимальным количеством "опасных" мест); на практике получается, что Антон пишет медленнее меня в разы (при наихудшей оценке моей производительности – вдвое). Павел же не проявляет никакой видимой инициативы в овладении новыми методами (структуры данных, алгоритмы), и при этом игнорирует мои указания о небходимости изучать их.
______________________
// LeX

Мой профиль

В целом согласен с приведенными замечаниями, хотелось бы отметить что задачу, по которой у меня возникли лишние отсылки я в руках не держал, в связи с чем и перепутал 2 константы между собой.
По поводу задачи D, я не понимаю как можно было так объяснить бор что его не смогли написать примерно за 3 часа. По поводу задачи E я дал обоснование невозможности решать через формулу и сказал что нужно писать трих(или дих по производной),оставалось примерно пол-часа, но было сказано что исправить бор 10 минут из-за чего мы эту задачу писать и не пытались.Как выяснилось в последствии задача B была оооочень простая, но мы её даже не смотрели.
И ещё, я пишу достаточно быстро и правильно те вещи, полную реализацию которых я сам понимаю, остальное, как следует из распределения тем должен писать Антон, на практике получается, что мне говорят учи всё и пиши всё(например вчера мне пришлось писать 7 задач из 8), я просто физически не могу кодить 5 часов, при этом быстро и без ошибок, может всё же в команде должно быть 3 кодера,так как работа по анализу условия редко занимает более 2 часов, остальное время у кого-то из команды практически пропадает...

Мой профиль

1. В ближайшее воскресенье вам всем вместе надо обсудить ПОВТОРНО

- распределение обязанностей в команде
- тактику решения задач на олимпиадах
- методику подготовки

2. Мое мнение таково

- Леше надо оставить роль
алгоритмировщика - придумывателя решений
и по возможности помощника в поиске тяжелых ошибок
(считаю без компа - только на распечатке)

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

- перед Антоном надо ставить вопрос РЕБРОМ - или он наращивает мастерство, или в команде ГГУ-1 будет ДРУГОЙ третий (первые два Леша и Паша - лучшие в универе пока по крайней мере

)

- для ускорения продвижения Антона вперед можно рассмотреть вопрос о его ВРЕМЕННОЙ замене по воскресеньям каждый раз на нового третьего, начать, например с Юденко(ПМ-21) - он вроде обещал серьезно работать, а Антон мог бы либо кодить параллельно все задачи олимпиады от простой к сложной (с алгоритмической поддержкой от Леши) либо выступать за другую команду.

Мой профиль

В финал ACM ICPC 2013 года от NEERC выходят следующие 19 команд:


SPb NRU ITMO 1               Короткевич, Кевер, Нигматуллин   - Россия,    Санкт-Петербургский НИУ ИТМО 
Moscow SU 1                  Рогуленко, Калужин, Фёдоров      - Россия,    МГУ 
Belarusian SU 1              Удовиченко, Малевич, Жгировский  - Беларусь,  БГУ 
SPb SU 4                     Егоров, Кунявский, Суворов       - Россия,    СПбГУ 
Ural FU 2                    Долгоруков, Соболева, Щелконогов - Россия,    Уральский ФУ 
Almaty Intl IT U 1           Большаков, Коваленко, Кутыбаев   - Казахстан, ИИТУ 
Kazakh-British TU 1          Айтбаев, Алмахан, Сатылханов     - Казахстан, КБТУ 
Moscow IPT 4                 Пименов, Горшенин, Альсармини    - Россия,    МФТИ 
Izhevsk STU #1               Бурлаков, Гатин, Смирнов         - Россия,    Ижевский ГТУ 
SPb AU #1                    Чаднов, Краско, Лазарев          - Россия,    СПб АУ 
Samara SAU #1                Дергунов, Глащенко, Семушин      - Россия,    Самарский ГАУ 
Ufa SATU                     Лежанкин, Мазгаров, Рипатти      - Россия,    Уфимский ГАТУ 
Altai STU 1                  Есипенко, Силин, Уваров          - Россия,    Алтайский ГTУ 
Kaunas TU                    Ciakas, Kusas, Mulevicius        - Литва,     Kaunas TU 
Moscow AI 1                  Белоусов, Сафонов, Журавлёв      - Россия,    МАИ 
Saratov SU 2                 Давтян, Гусаров, Кудряшов        - Россия,    Саратовский ГУ 
Moscow I of Steel and Alloys Булатов, Кофман, Крохина         - Россия,    МИСиС 
Perm SU 1                    Ошеров, Акимов, Заякин           - Россия,    Пермский ГУ 
Novosibirsk SU 1             Белошапко, Щербина, Стененко     - Россия,    НГУ                     5 задач, 35 место

А могла бы и команда ГГУ там быть.
Надо только захотеть.

Мой профиль

Среда программирования на финале

Мой профиль

Как решают полуфинал