CodeChef invites you to participate in the September Lunchtime 2014 at http://www.codechef.com/LTIME16. This is an IOI style contest. This means that the problems will be partially graded. You will get score for passing certain test data.

Time: 29th September 2014, 1100 hrs to 1400 hrs. (Indian Standard Time — +5:30 GMT) — Check your timezone.

Details: http://www.codechef.com/LTIME16/

Registration: Just need to have a CodeChef user id to participate. New users please register here

- Problem Setter : Roman Furko
- Problem Tester: Gedi Zheng
- Editorialist:Devendra Agarwal
- Russian Translator: Sergey Kulik
- Mandarin Translator: Gedi Zheng & Minako Kojima

It promises to deliver on an interesting set of algorithmic problems with something for all.
The contest is open for all and those, who are interested, are requested to have a CodeChef User ID, in order to participate.

Недавно пришла в голову задача, но никак не могу придумать решения.

Постановка задачи: Дано множество из N точек(декартовая система). Нужно построить многоугольник минимальной площади.Многоугольник должен быть без самопересечений и содержать все точки как вершины многоугольника. Нужен самый оптимальный алгоритм :)

Будет очень круто, если Вы прикрепите код. Заранее спасибо!

Приветствуются всевозможные решения!

313A - Илья и банковский счет

В данной задаче не было ничего сложного. Нужно было уметь пользоваться div и mod. Понятно, что если n>0, то нет смысла удалят цифру. А иначе, нужно удалять.

Для лучшего понимая посмотрите решение

313B - Илья и запросы

Предпосчитаем такой масив A_i, что A_i = 1, если s_i = s_i + 1, иначе A_i = 0. Теперь не сложно заметить, что ответом на запрос будет Sum_{A, l, r - 1}. Данную функцию можно организовать множеством вариантов. Одним из, является дерево отрезков. Но так как запросы можно выполнять в оффлайн, то можно использовать массив частичных сумм. Пусть Sum_i – это сумма всех A_j, (j ≤ i). Тогда, что бы найти сумму на отрезке (l, r - 1) – нужно Sum_r - 1 - Sum_l - 1.

Для лучшего понимая посмотрите решение.

313C - Илья и матрица

Для начала отсортируем массив. Пусть С_i –-- это количество раз вхождения числа А_і в оптимальную расстановку. Понятно, что ответом будет сумма всех чисел A_i*C_i (1 ≤ i ≤ 4ⁿ). Теперь нужно заметить, что максимальный элемент будет входить n + 1 раз. (Если размер массива равен 4ⁿ). Следующие 3 числа, будут входить в ответ n раз, еще следующие 12 уже n - 1. И так далее. Представим, что массив отсортирован по не возрастанию. Не сложно заметить, что ответом будет Sum(1, 1) + Sum(1, 4) + Sum(1, 16)… + Sum(1, 4ⁿ). Сумму на отрезках можно реализовывать в лоб, так как это позволяли ограничения.

Для лучшего понимая посмотрите решение.

313D - Илья и дороги

Для того что бы решить эту задачу нужно было разбить её на две более легкие. Пусть Full_i, j – минимальная стоимость покрыть заданными отрезками, отрезок (i, j). Для того что бы подсчитать эту величину, для всех (i, j) нужно перебрать левую границу отрезка і, и двигать правую. Решение данной подзадачи имеет сложность О(nm). Теперь нам нужно решить вторую подзадачу. Вторая подзадача звучит так: покрыть не менее К точек, отрезками которые не пересекаются (Их стоимости мы знаем, так как мы решили первую подзадачу). Для её решения нужно использовать тот же метод динамического программирования, который намного проще чем решение первой подзадачи. Пусть dp_i, j — минимальная стоимость покрыть j точек, если мы просмотрели только префикс длинной i. Из состояния (i, j) мы можем перейти в такие состояния:

1) dp_{i + 1, j} = min(dp_{i + 1, j}, dp_i, j); Скажем, что мы не будем покрывать точку с номером i + 1

2) dp_{k, j + len} = min(dp_{k, j + len}, dp_i, j + Cost); Cost — стоимость покрытия отрезка длинной len, который заканчивается в точке k. Значение Cost мы предпосчитали в первой подзадаче.

Для лучшего понимая посмотрите решение

313E - Илья и два числа

Для решения данной задачи нужно уметь использовать кучу и дерево интервалов. Заметим, что если мы берем цифру і с первого числа, и цифру j со второго, то в третьей будет цифра ((i + j)mod m). На каждом шагу из всех таких пар выбирается максимум. Ответ мы выводим на экран, а те две цифры, что мы использовали, нужно удалить. Для решения уже новой задачи, можно завести кучу, в которой изначально будет N значений. Для каждой цифры из первого множества, та цифра из второго которая будет самым оптимальным для ответа. То есть (i1 + i2)mod m = MAX. Но когда мы используем какую-то пару, возможно распадется другая пара. Для того что бы быстро строить новые пары, нужно использовать дерево интервалов для поиска К-го элемента.

Для лучшего понимая посмотрите решение

Также, существует более простое и понятное решение, которое описал MrDindows. Решение MrDindows

Извините за ожидание.

Всем привет!

В ближайший четверг 30 мая в 19:30 MSK пройдет Codeforces Round #186 (Div. 2), автором которого являюсь я. Это мой первый раунд на Codeforces и я надеюсь что все получат удовольствие от решения задач на нём.

Спасибо Геральду Агапову (Gerald) за огромную помощь в подготовке раунда и Марии Беловой (Delinur) за перевод условий на английский. Также, хочется поблагодарить Ваню Здомского (ballon), за то что он протестировал раунд.

Разбалловка сегодня такая: 500-1000-1500-2500-2500

Good luck & have fun! :)

Недавно встретил данную задачу для ограничений N<=100, M<=10000. Первая мысль была минкост, но он будет очень долго работать, так как сложность минкоста О(N^3*M). Подскажите пожалуйста, как решить заданную задачу за подходящее время (1-3 сек).