Блог пользователя Berezin

Автор Berezin, 11 лет назад, По-русски

366A — Дима и вахта

Заметим, что решения не существует, если самый дешевый способ стоит больше n. В противном случае всегда можно доплатить за любое угощение, дополнив суммарную стоимость до n.

Найдем самый дешевый способ. Очевидно, что каждой вахтерше лучше покупать то угощение, минимальная цена которого меньше. То есть, если есть вахта с параметрами a b c d, то стоимость минимального подкупа будет min(a, b) + min(c, d). Выберем вахту с наименьшей минимальной стоимость подкупа. Если она больше n, ответ -1. Иначе, ответом может быть, к примеру: Номер вахты, min(a, b), nmin(a, b).

366B — Дима и дела

Дима успевает сделать спокойно k–1 дело, то есть Инна всегда ругает его за k-ое дело, начиная с выбранного Димой первого дела. Таким образом, ответ для дел с одинаковым остатком от деления на k будет одинаковым, вывести нужно ответ с минимальным номером первого дела, поэтому достаточно посчитать суммы “руганий” для дел 0, 1... k–1. Это можно сделать к примеру так: Завести массив int sum[k]. И при считывании числа сразу определять его в соответствующую ячейку:

sum[I mod k] +  = a[i]. Теперь осталось выбрать первое i такое, что sum[i] минимальное.

Сложность решения O(N).

366C — Дима и салат

Будем поддерживать динамику d[num][balance] где num – последний рассмотренный фрукт, balance – разница между суммами выбранных калорийностей и вкусностей. Умножим все b на k. Тогда ответом будет d[n][0].

d[num][balance] = максимально возможной сумме вкусностей.

Переход: из d[num][balance] можно осуществить так:

d[num + 1][balance] = max(d[num + 1][balance], d[num][balance]) – если мы не берем фрукт.

d[num + 1][balance + a[i] - b[ik] = max(d[num + 1][balance + a[i] - b[ik], d[num][balance] + a[i]) – если берем.

На самом деле, баланс может быть отрицательным, поэтому в языках программирования, не поддерживающих отрицательную индексацию, индексы баланса нужно сдвинуть на самое большое отрицательное число, которым может стать баланс. Если баланс – сумма каллорийностей минус сумма вкусностей, то это сумма всех вкусностей всех фруктов.

366D — Дима и граф-ловушка

Очевидно, что лояльность пути – это ширина диапазона, с которым его можно пройти, а диапазон этот – пересечение диапазонов ребер пути. Это выплывает из того, что числа является валидным для пути, если с ним можно пройти через все ребра. Переберем все ребра графа, пусть левая граница диапазона на ребре – это левая граница пересечения. Это значит, что мы не можем использовать ребра, у которых левая граница не больше нашей. Переберем все правые границы, считая ответом диапазон с зафиксированной ранее левой границей и выбранной нами правой. Такой ответ существует, если можно пройти из первой вершины в последнюю с выбранными ограничениями. Проверим граф на связность выбирая только ребра с левой границей не больше нашей, и правой границей не меньше нашей. Если граф связный, обновляем ответ. Заметим, что правую границу можно перебирать с помощью бин поиска, таким образом итоговая сложность решения O(M2·logM).

366E — Дима и волшебная гитара

Задача имеет несколько решений. Опишу авторское, с остальными вы можете ознакомиться, посмотрев решения участников. Очевидно, что для нахождения ответа нужно посчитать матрицу maxDis[k][k], где maxDis[i][j] – максимальная сложность перехода между нотами i и j.

Тогда останется пройтись по песне, и обновлять ответ для каждой пары соседних нот. Давайте подумаем, как можно быстро посчитать матрицу.

Для каждого места (x1, y1) на гитаре переберем все места (x2, y2) такие, что y2 ≤ y1.

Если (x2 ≤ x1) расстояние будет x1x2 + y1y2. И значит, нас интересует минимальное значение x2 + y2 в подматрице от (0, 0) до (x, y).

Если (x2 ≥ x1) расстояние будет x2x1 + y1y2. И значит, нас интересует максимальное значение x2y2 в подматрице от (n–1, 0) до (x, y).

Будем считать эти значения для каждой ноты. Памяти нужно слишком много, но можно хранить только предыдущую строчку динамики для каждой ноты. Для каждой ячейки обновим динамику для всех нот, и для нашей ноты (которая и лежит в этой ячейке) сравним значение (i + j) или (ij) с текущим в динамике.

Сложность O(N·M·K)

Разбор задач Codeforces Round 214 (Div. 2)
  • Проголосовать: нравится
  • +52
  • Проголосовать: не нравится

»
11 лет назад, # |
Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

Я, видимо, неправильно понял задачу, но перечитывание не помогло. Подскажите, пожалуйста, почему нижеприведённый тест не валит авторское решение?

1 5 4 3
4 1 2 4 3
1 4 3

upd. Укоротил тест.

  • »
    »
    11 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Мы считаем динамику

    A[i][j][k] — минимальное I + J (I <= i, J <= j, guitar[I][J] = k).

    B[i][j][k] — максимальное I — J (I <= i, J <= j, guitar[I][J] = k).

    A[0][4][4] = 0; поэтому matrix[3][4] = (0 + 4 — A[0][4][4]) = 4.

    Надеюсь, объяснил.

    Простите, если разбор или ответ не внятный, очень устал =)

    • »
      »
      »
      11 лет назад, # ^ |
        Проголосовать: нравится -6 Проголосовать: не нравится

      Правильно ли я понимаю, что: maxDis[1][4] = 2, maxDis[4][3] = 4? Если так, то у вас получится ответ 6, в то время как правильный 5. Или здесь правильный ответ 6? Или я решение не понял? Вы тоже простите, если что, сегодня весь вечер туплю.

      • »
        »
        »
        »
        11 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Начнем с того, что ответ — расстояние между (1, 5) и (1, 1) — 4.

        • »
          »
          »
          »
          »
          11 лет назад, # ^ |
            Проголосовать: нравится +5 Проголосовать: не нравится

          Напомню, что сложность песни — это максимальная сложность перехода между соседними (не сумма)

        • »
          »
          »
          »
          »
          11 лет назад, # ^ |
            Проголосовать: нравится -6 Проголосовать: не нравится

          Ой, спасибо, ещё раз перечитал задачу, и теперь уже понял. Так она куда проще. Я же решал задачу, где сложность песни была сумма переходов между нотами. Она немного посложнее :\

    • »
      »
      »
      11 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Спасибо за замечательные задачи!

»
11 лет назад, # |
Rev. 3   Проголосовать: нравится +24 Проголосовать: не нравится

I (but not just me, as I noticed from looking at others' codes) have a cool solution of E:

Imagine that we want to calculate the max. distance of 2 tones a, b. Take tone a at (x1, y1) and b at (x2, y2); notice that |x1 - x2| + |y1 - y2| is the maximum of  ± (x1 - x2) ± (y1 - y2) for all signs, which leads to 4 possible expressions:

x1 + y1 - x2 - y2
x1 - y1 - x2 + y2
 - x1 + y1 + x2 - y2
 - x1 - y1 + x2 + y2

Instead of limiting ourselves to the correct expression, we can evaluate the maxima of all pairs of points with all 4 expressions, and the answer will still be the maximum of them all. Notice that all 4 are linear, so we just need to calculate the maximum and minimum of $x_1+y_1$ and x1 - y1 for all points of one tone; the result for 2 tones can be found by trying the maxima of all 4 expressions, which are (in that order)

Complexity: O(NM) :D

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Please elaborate the part Notice that all 4 are linear, so we just need to calculate the maximum and minimum of x1 + y1 and x1 - y1 for all points of one tone;

    • »
      »
      »
      11 лет назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

      We compute the numbers and and take their difference. Similarly for the other 3 expressions, and for any pair of tones (denoted here as "1" and "2").

      For any linear function f (UTFG if you don't know about these) we have

»
11 лет назад, # |
Rev. 3   Проголосовать: нравится +11 Проголосовать: не нравится

Actually there is a simple soluton for problem D with complexity O(M ^ 2).

Tip: Two pointers instead of binary search.

»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can u double-check the expressions in solution for task C?

»
11 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Can someone please explain the solution to C? I did not understand the use of balance. I just thought of doing the following: For a pair (a,b), if a/b = k, it can be.included in our solution. For all pairs for which a/b!=k, check if adding the pair to the solution satisfies given conditions. If yes, include it in solution. We can choose nC2 pairs and do the above operations in O(n^2).

»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

In D, what do you mean by ribs and boards?

  • »
    »
    11 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    i'm not sure, but i think rib means edge, and board means bound (i.e. left board = lower bound, right board = upper bound)

»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

can somebody explain problem D solution

»
11 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

А в D, когда Сережа фиксирует путь, чтобы посчитать его лояльность, под путём он подразумевает конкретные рёбра, по которым пойдёт, или вершины, через которые пойдёт. При кратных рёбрах эти варианты дадут разный результат на таком тесте:

3 3  
1 2 1 1  
1 2 2 2  
2 3 1 2

Судя по разбору, имеется в виду именно зафиксированный по рёбрам путь, но при чтении задачи это не было очевидно.

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Да, имелись ввиду ребра. Если я не ошибаюсь, в сэмплах был тест с кратными ребрами.

»
11 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

В задаче С в последний формуле кажется опечатка!

d[num + 1][balance + a[i] - b[i]·k] = max(d[num + 1][balance + a[i] - b[i]·k], d[num][balance] + a[i])

=>

d[num + 1][balance + a[i] - b[i]·k] = max(d[num + 1][balance], d[num][balance + a[i] - b[i]·k] + a[i])
»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I don't like how A is worded,

"If a chocolate bar for some guard costs less than the minimum chocolate bar price for this guard is, or if a box of juice for some guard costs less than the minimum box of juice price for this guard is, then the guard doesn't accept such a gift."

By using "this guard" and "some guard", it can be read that out of all the guards, this guard's minimum chocolate price must be the minimum out of every guard.

  • »
    »
    6 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    you are absolutely correct there is a problem in this statement my solution is not working just because of this condition

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I must say problem C is amazing, never seen any problem quite like it.

»
17 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
C can be solved with use of dp with bitmasks 
dp state: dp[i][summation of tastes][summation of calories] 
and if we want add new taste it will be 

dp[i+1][summation + a[i]]<<=b[i];

we will shift every summation of calories by b[i];

ACCEPTED