441A - Валера и антиквариат

Автор задачи gridnevvvit

Нужно реализовать то, что записано в условии. Например, это можно сделать так: посчитаем q_i — минимальная цена товара у продавца i Тогда если q_i < v, то мы можем заключить сделку с продавцом i. Иначе не сможем.

Авторское решение: 6850474

441B - Валера и фрукты

Автор задачи gridnevvvit

Будем последовательно перебирать дни от 1 до 3001. Пусть текущий день это день i. Кроме того, дополнительно будем поддерживать величину cur --- количество фруктов, которые мы не успели собрать в предыдущие дни. Предположим, что в день и созреет now фруктов. Если now + cur ≤ v, то нужно добавить к ответу now + cur и обновить значение cur (cur = 0). Иначе к ответу нужно прибавить величину v, а величину cur обновить следующим образом. Пусть tv = max(v - cur, 0). Тогда cur будет равен величине cur = now - tv. Иначе говоря, сначала мы пытаемся собрать те фрукты, которые завтра уже испортятся.

Кроме того, можно решить задачу и за . Однако, этого не требовалось.

Авторское решение: 6850502

Бонус. Предположим, что фрукты можно собирать в дни a_i, a_i + 1, ..., a_i + T_i, где T_i — некоторое заданное число для каждого дерева. Как решить оптимально такую задачу? Да, еще. Кроме того, для каждого дня заданное свое значение v (производительность труда в каждый день).

441C - Валера и трубы

Автор задачи gridnevvvit

Задача решается довольно просто. Сначала построим такой обход прямоугольной таблицы, который посещает все его клетки. Его построить очень просто:

1. Пусть сначала мы стоим клетке (1, 1). Слева направо дойдем до самой правой клетки поля в этой строке, до клетки (1, m).
2. Перейдем на следующую строку, в ячейку (2, m). Справа налево дойдем до самой левой клетки поля в этой строке, до клетки (2, 1).
3. Перейдем на следующую строку. Повторим действия из пунктов 1. и 2. до тех пор, пока не посетим все клетки.

После того, как мы построили такой обход, получить ответ не трудно: достаточно первые (k - 1) трубу сформировать из 2 ячеек, а последнюю трубу из оставшихся.

Авторское решение: 6850508

441D - Валера и обмены

Aвтор задачи danilka.pro

В данной задаче удобно представить перестановку в виде ориентированного графа c n вершинами, а из каждой вершины i проведено единственное ребро в вершину p[i]. Очевидно, что этот граф полностью состоит из простых циклов.

Если провести операцию обмена (i, j), то ребра и станут ребрами и соответственно. Тогда, если i и j находятся в одном цикле, то этот цикл разорвется:

а если в разных, то циклы, в которых они содержатся, соединятся в один:

а это значит, что любая операция обмена либо увеличивает число циклов на один, либо уменьшает на один.

На основании всего вышеизложенного, чтобы получить перестановку q из перестановки p, нужно увеличить (или уменьшить) число циклов в перестановке p до n - m. Пусть с — число циклов в перестановке p. Тогда k всегда равно |(n - m) - c|.

Для выполнения условия лексикографической минимальности, рассмотрим три случая:

1) n - m < c

Очевидно, что в этом случае выгоднее всего уменьшать число циклов, соединяя их с циклом, содержащим вершину 1. Таким образом, в этом случае любой обмен имеет вид (1, v), где v > 1. Поскольку вершина каждого последующего цикла больше предыдущей, данный случай решается за O(n).

2) n - m > c

В этом случае необходимо для каждой вершины разрывать ее цикл, совершая обмен с наименьшей возможной вершиной (она так же должна находится в цикле). Это можно сделать, если представить цикл в виде строки . Поскольку каждый цикл разрывается за линейную сложность, такое решение работает за O(n²).

Бонус: данный способ представления цикла позволяет оптимизировать решение до ассимптотики , можете подумать, как.

3) n - m = с

Так как в этом случае k = 0, никаких обменов делать не нужно.

Крайне рекомендуется ознакомиться с авторским решением: 6850515

441E - Валера и число

Автор задачи gridnevvvit

Решать задачу будем следующим образом: будем считать динамическое программирование d[i][mask][last][cnt] — вероятность получить через i шагов такое число v, что его последние 8 бит равны маске mask, 9-ый бит равен значению last, а cnt — это количество подряд идущих бит (начиная с 9-го бита) которые равны по величине значению last.

Хорошо, а почему мы отбросили остальные биты? Понятно, что используя операцию  +  = 1 мы сможем изменить только первый нулевой бит, индекс которого  ≥ 9.

Переходы достаточно очевидны: либо мы прибавим единицу, либо  *  = 2 (Подробнее их можно изучить в моем решении). Возможно, следует задать вопрос такой. Например, мы имеем число в двоичном представлении x = 1011111111.

И в текущий момент, мы делаем  +  = 1. Согласно тому, что я написал выше, мы должны перейти в состояние d[1][0][1][2], однако мы не сможем этого сделать, поскольку у нас нет никакой информации о 1 в 10-ой позиции. Однако, поскольку мы не сможем больше изменить никакой бит с индексом  >  = 9 (так как mask = 0) мы сделаем переход в состояние d[1][0][1][1].

Авторское решение: 6850523

Бонус. Предположим, что мы имеем немного другой псевдокод.

// input x, k, p
 
for(i = 0; i < k; i += 1) {
   if (x четное) {
     rnd = случайное число на отрезке [1, 100]
     if (rnd <= p)
       x *= 2;
     else
       x += 1;
   } else {
      x *= 2;
   }
}
 
s = 0;
 
while (x четное) {
  x /= 2;
  s += 1;
}
 

Как и прежде, нужно найти математическое ожидание s.

Насколько эффективно вы можете решать такую задачу? Можете ли вы доказать свое решение?