Форум DL

Мой профиль

ICPC Live Stream
Онлайн трансляция финала в среду 20 мая в 12 часов по Москве

Teams for ACM ICPC World Finals 2015 — Marrakesh, Morocco

Photo with famous people on ACM ICPC WF

Мой профиль

ACM-ICPC World Finals 2015

Oficcial scoreboard
Scoreboard with TC/CF handles

Мой профиль

Final Results

                                                                           Solv Time
 1 St. Petersburg National Research University of IT, Mechanics and Optics  13  1801  
 2 Moscow State University                                                  11  1293  
 3 The University of Tokyo                                                  11  1369  
 4 Tsinghua University                                                      10  1234  

 5 Peking University                                                        10  1250  
 6 University of California at Berkeley                                     10  1347  
 7 University of Zagreb                                                     10  1501  
 8 Charles University in Prague                                             10  1567  

 9 Shanghai Jiao Tong University                                            10  1616 
10 Massachusetts Institute of Technology                                    10  1629 
11 Korea University                                                          9  1220 
12 University of Warsaw                                                      9  1233

Полуфинал АСМ 2015 в Санкт-Петербурге

Мой профиль

ACM-ICPC World Finals Problems Solutions +1

Мой профиль

О случайностях на контестах

Мой профиль

Задача А
В данной задаче дана последовательность до миллиона чисел, заданная формулой с параметрами. Требуется найти максимум a[i] - a[j], i <= j. Решение: будем поддерживать максимум на префиксе последовательности и если разность между максимумом и текущим элементом больше текущего ответа - пересчитаем ответ. Сложность Time ~ O(n) Memory ~ O(1). Подарок

Задача B.
Требуется определить максимальную площадь наложения 2 многоугольников (не более 10 вершин), если заданы скорости их движения. Решение - трих (или дих по производной), реализация будет оооочень сложной из-за обилия мат формул и мест где можно накосячить.

Задача С. В данной задаче требуется определить минимальную сумму расстояний в полном ориентированном графе на 100 вершин, путь только в вершину сбольшим номером, при условии того, что из 1 можно выходить не более k раз. Решение - поток минимальной стоимости на двудольном графе. Первая доля - k вершин с номером 0 вершины от 1 до n-1, вторая доля - вершины от 1 до n+1. Веса ребёр читаются в матрице. Сложность как напишите, можно за n^4.

Задача D.
По сути если выкинуть всё условие, то требуется уметь находить объём пересечения сферы и параллелипипида за О(1). Не много стереометрии и в целом всё... Знания интергалов помогут. Дальше дих в лоб. Сложность N*M*log(1/e). e~10-6 - точность вывода.

Задача F.
Сразу переформулирую. Есть граф, вершина задана тройкой чисел (x,y,pos) - курсор в клетке (x,y) и набираем pos букву текста. Всего вершин 50*50*10000 = 25кк, из каждой вершины не более 5 переходов. Требуется найти минимальный путь из (1,1,1) в какую-нибудь (X,Y,|L|+1). Вполне заходит очередь в лоб. Если есть желание максимально оптимизировать (ну там место в топе заработать) то A*. Сложность O(N*M*|L|) по памяти и времени.

Задача H
Требуется определить координаты N ям, так чтобы суммарное расстояние транспортировки L единиц земли + землю с ям было минимальным. Решение. Заметим что если мы перейдём от L -> 1 то ответ уменьшится в L*L раз (там квадратичная функция), саму функцию посчитать не тяжело. Дальше трих с учётом того что мы уже знаем как поставить k ям оптимально ставим k+1. Потом восстанавливаем ответ. Не используйте дих по производной, не хватит точности.
Сложность Time O(N*log(1000/e)) e ~ 10-6, Memory ~ O(n).

Задача I
Дано множество линий единичной ширины и дано множество объектов на линиях с заданным положением, размером и скоростью. Требуется найти промежуток времени максимальной длины, чтобы для любого момента времени t было верно: на линии 1 нет объекта в [t,t+d], на линии 2 нет объекта [t+d,t+2d], на 3 - [t+2d,t+3d] и так далее.
Решение: найдём время появления и удаления объекта на каждой линии, в приведённом времени (вычти номер линии умножить на d), при удалении вычтя d ещё раз. Отсортируем по возрастанию. Дальше пройдёмся по событиям и посмотрим когда нету объектов (как в скобочном балансе). Из таких моментов выберем максимальной длины с учётом начала и конца. Сложность Time ~ O(M log M) Memory ~ O(M). M = 10^5

Задача J.
Требуется найти максимум функции на отрезке. Функция - кол-во способов построить параллелограмм с вершинами в целых точках и площадью x - тоже целое. Нетрудно заметить (ну или кому-как

), что F(x) = sum(i,1,x-1)[ C[i] * C[x - i] ], C[y] - кол-во делителей числа y. Итого сложность квадрат, x - 500k что совсем нехорошо. По-хорошему нужно делать преобразование Фурье (быстрое) оно переведёт свёртку в произведение. Если лень/не знаете предпросчитаем блочно сколько можем (зависит от ограничения на размер посылаемого файла) и получим опорные точки, напрмер каждые 100 элементов (тогда 500к/100 = 5к * 10 = 50кб должно влезть). Ответ на запрос - 5к + 50(мы знаем в большую или в меньшую сторону ближе считать) * 250к (функция симметрична) в худшем случае - 12,5кк на запрос. 25кк * 500 = 7ккк за 20 секунд более чем реально. В крайнем случае делать блоки не равномерно а в конце более плотно, этим ещё раза в 2 можно оптимизировать. Итого всё зависит от ограничения на размер файла. Минут за 15 локально просчитает.

Задача L
В данной задача требуется придумать кодировку текста (алфавит 4 символа, длина не более 20) непрефиксным способом, если вероятность появления каждой буквы независима и задаются во входном файле. Будем использовать шифт Хафтмана (Шифтмана). Разобьём все виды текста (4^20) на группы с одинаковой вероятностью (не более C[4,20] ~ 160 000). Дальше - будем использовать стандартный алгоритм (через кучу/дерево, т.к. за квадрат нельзя). При этом будем объединять сразу всю группы + возможно 1 из предыдущей группы. Сложность Time ~ O( C[4,N] * log(C[4,N]) ). Memory ~ O(C[4,N]).

Задача M
В данной задаче требуется уметь отвечать на запросы вида
- добавить прямоугольник с известными координатами
- изменять координаты прямогульника
- определять какой прямоугольник находится в заданной точке.

Так как запросов не более 256, то можно всё реализовать в лоб, просто храня массив прямоугольников и обновляя его какждый запрос. Сложность порядка O(n^2). Задача на реализацию, требует аккуратной обработки частных случаев и внимательного чтения условия. Китайский/индусский код.

Мой профиль

ACM-ICPC Live archive

Мой профиль

По ссылке выше не тестирует, рекомендую https://icpc.kattis.com

Если кому интересно, привожу свои решения некоторых из задач.

A http://ideone.com/cV3DY2 0.17s
C http://ideone.com/vftHD5 0.02s
D http://ideone.com/QajVmr 0.56s
F http://ideone.com/zZIKHP 2.37s оптимизация слабая http://ideone.com/xQYKLR до 1.95s
H http://ideone.com/tob3Fj 0.01s
I http://ideone.com/WXP06N 0.40s
J http://ideone.com/hwsgRh 0.63s решил через преобразование, так интереснее

L http://ideone.com/MmpMwF 0.03s , если заменить long double на double - 0.02s и место в топе решений

В задаче L решение чуть проще чем думал сразу.

TL в задачах абсолютно неадекватные, например в задаче F на icpcarchive.ecs.baylor.edu - 30 секунд, на каттисе 5. И так далее.

Мой профиль

Обновлен разбор и решения.

Решение по М не выкладываю, китайский кривой код.