Привет Codeforces!

Приглашаем всех принять участие в Codeforces Round #266, который состоится 12 сентября в 19:30 MSK для участников Div2. Как обычно, участники из первого дивизиона могут принять участие вне конкурса.

Подготовкой задач занимались Antoniuk и я. Это наш второй раунд на CF, и все еще надеемся, что не последний.

Выражаем благодарность Gerald за помощь в подготовке раунда, Delinur за перевод условий на английский, а также MikeMirzayanov за Codeforces и Polygon.

Разбалловка задач будет стандартной: 500-1000-1500-2000-2500.

Желаем удачи и высокого рейтинга!

UPD. Раунд завершен. Спасибо всем за участие, надеюсь задачи вам понравились.

UPD2 Поздравляем пятерку победителей:

1) dominator_hza
2) Final_Battle
3) free_pascal
4) vanhanh.pham
5) NUOUN

UPD3. разбор задач

431A - Черный квадрат

В этой задаче нужно было просто сделать то, что написано в условии.

for i = 1 .. s.size()
 if (s[i] = '1') ans += a[1];
 else ...

Асимптотика: O(N)
Решение: 6676675

431B - Очередь в душ

В этой задаче, в следствии маленьких ограничений, можно перебрать все перестановки и среди всех перестановок выбрать ту, в которой ответ получается наибольший.Легче всего это было сделать использую стандартную процедуру (для С++) next_permutation либо же просто написал 5 циклов. Для каждой перестановки можно было как промоделировать процесс описанный в условии, так и заметить что первый студент со вторым и второй с третьим будут общаться 1 раз(за все время которое они будут стоять в очереди), а третий с четвертым и четвертый с пятым 2 раза. Остальные пары студентов между собой общаться не будут.

Асимптотика: O(n!)
Решение: 6676695

431C - k-дерево

Эта задача может быть решена методом динамического программирования.
Пусть Dp[n][is] — количество путей длины n в к-дереве, в котором если is = 1 — есть ребро веса не меньше d, is = 0 — веса всех ребер меньше d.
Начальное значение Dp[0][0] = 1.
Переход — перебрать ребро из корня которым начинается путь, тогда задача сведется к аналогичной но уже для меньшей длины пути (поскольку поддерево сына вершины абсолютно такое-же к-дерево).

Dp[n][0] = Dp[n-1][0] + ... + Dp[n-min(d-1,n)][0] Dp[n][1] = Dp[n-1][1] + ... + Dp[n-min(d-1,n)][1] + (Dp[n-d][0] + Dp[n-d][1]) + ... + (Dp[n-min(n,k)][0] + Dp[n-min(n,k)][1])

Смотрите решение для уточнения деталей.

Асимптотика: O(nk)
Заметим что это решение, подсчитав частичные суммы, можно очевидным образом модифицировать до O(n), но этого в задаче не требовалось.
Решение: 6676700

431D - Случайное задание

Будем искать n бинарным поиском. Такая функция будет монотонна,поскольку количество чисел с ровно k единичными битами на отрезке n + 2 ... 2·(n + 1) не меньше чем количество таких чисел на отрезке n + 1 ... 2·n. Справедливость предыдущего утверждения следует из того, что n + 1 и 2·(n + 1) имеют одинаковое количество единичных бит. Для нахождения количества чисел на заданном отрезке L...R у которых ровно k единичных бит, нам достаточно научиться считать это количество для отрезков вида 1...L, тогда ответом будет F(1...R) - F(1..L - 1).
Поймем как считать F(1...X). Переберем в каком бите(начиная от старших к младшим) число будет отличаться от X. Пусть первое отличие в i-ом бите(только если в X — этот бит единичный, потому что число не может превышать X).Тогда все остальные младшие биты мы можем выбрать как угодно, при условии что общее количество единичных бит будет равно k. Это можно сделать C_i^k - cnt способами, где cnt — количество единичных бит в числе X с номерами большими i, а C_n^k — биномиальный коэффициент. Так же нужно не забыть про само число X (если в нем, конечно, ровно K единичных бит).

long long F( X )
   Ans = 0 , cnt = 0;
   for i = Max_Bit...0
      if (bit(X,i) == 1) Ans += C[i][K - cnt] , cnt ++;
   if (Bit_Counts(X) == K) Ans ++;   
   return Ans;

Асимптотика: O(log²(Ans))
Решение: 6676713

431E - Химический эксперимент

Разберемся сначала в условии.
У нас есть n колб. В начале в каждой из них налито определенное количество ртути. Надо уметь выполнять два вида действий:

1. Сделать количество ртути в p-й колбе равным x.
   
2. Дано число v — это количество воды, которую надо оптимально разлить по этим колбам. Что значит оптимально? Надо в некоторые колбы долить воду так, чтобы среди всех колб, куда мы налили хоть какое-то количество воды, максимальный объем жидкости(вода + ртуть) был как можно меньше.
   

Ну собственно теперь перейдем к решению.
Используем бинарный поиск для нахождения ответа, в частности, будем перебирать количество ртути в колбе( пусть оно равно d), такой что в меньшие по объему колбы можно разлить все v литров воды, так, чтобы максимальный уровень жидкости не превысил d. Пусть количество колб объемом ртути, меньшим чем d равно t.
Теперь задача свелась к тому, чтобы научиться считать суммарный объем воды который нужно долить в каждую из t наименьших колб, чтобы уровень жидкости в каждой из них стал равен d.

Пусть a[i] — суммарный объем ртути в колбах в которых ровно i литров ртути и b[i] — количество колб в которых объем ртути равен i. Тогда t = b[0] + ... + b[d - 1] и v₁ = t * d - (a[0] + a[1] + ... + a[d - 1]) — суммарный максимальный объем воды который можно долить. Если v₁ < v, то очевидно этого места мало чтобы разлить всю воду, иначе вполне достаточно и значит ответ уже будет не больше d.
После того как мы нашли такое наименьшее d, мы можем утверждать что ответ равен d — (v₁ — v)/t.

Чтобы быстро искать a[0] + a[1] + ... + a[d - 1] и b[0] + ... + b[d - 1], а также выполнять запросы первого типа можно использовать дерево Фенвика.

Асимптотика: O(qlog²(n))
Решение: 6676668

Добрый вечер сообщество Codeforces!

Прошедший неделю назад 1 тур (13.01.2012) Киевской городской олимпиады школьников по информатике вызвал достаточное количество вопросов, и я, не увидев здесь о нем ни слова, решил высказать свои впечатления и поинтересоваться вашим мнением.

Подскажите пожалуйста возможно ли в системе непересекающихся множеств реализовать разъединение множеств не теряя при этом выигрыша во времени (например не отказываясь от использования эвристики сжатия путей).