Yury_Bandarchuk's blog

By Yury_Bandarchuk, 10 years ago, In Russian

467A - George and Accommodation

В этой задаче нужно было просто посчитать количество пар, у которых qi - pi ≤ 2

Асимптотика: O(N)

467B - Fedor and New Game

В этой задаче нужно было уметь считать количество различных битов в двух числах. Как вариант, можно просто побежать по битам и посчитать количество различных. Ещё, как вариант, если исходные два числа X и Y, то количество различных битов равнялось бы количеству единиц в числе X xor Y, где xor — операция исключающего или.

Асимптотика O(M·N)

467C - George and Job

Решение этой задачи — динамическое программирование. Изначально нужно посчитать psumR, где psumR — сумма на префиксе массива p длиной R.

Обозначим dpi, j — максимальная прибыль которую может получить Юра, если мы уже выбрали i последовательностей и последний элемент в i-ой последовательности имеет индекс j.

Очевидно, что если i·m > j, то dpi, j = 0. Иначе dpi, j = max(dpi, j - 1, dpi - 1, j - m + psumj - psumj - m) Ответом будет dpk, n.

Ещё нужно было не забыть использовать long long при вычислениях.

Асимптотика: O(N·K)

467D - Fedor and Essay

Первое, что нужно сделать, чтобы облегчить себе работу — перевести все строки в нижний регистр. Затем словам дать номера. Различным словам дать различные номера, а одинаковым — одинаковые.

Затем, из всех строк нужно построить граф. Пусть каждое слово — просто вершина. А пара слов синонимов X и Y — ребро между вершинами, которые отвечают за данные слова. Ребра ориентированные. Также, для каждого слова мы должны хранить его длину и количество букв «R». Будем использовать номера, данные словам, для построения графа.

После создания графа, у нас мог быть петли, кратные ребра, циклы. Поэтому нужно сжать все сильно связные компоненты в одну вершину. После чего задача состоит в том, чтобы посчитать dpver — пара, отвечающая за минимальное количество букв «R» и минимальную длину слова с минимальным количеством букв «R», которым можно заменить слово, за которое отвечает вершина ver.

Пересчет очевиден — dpver = max(dpnextVev, dpver), где nextVer — все вершины, в которые можно пойти из ver. Максимум из двух пар берется как у pair в C++.

Затем нужно пройти по всем словам текста, получить номер вершины, который соответствует нужному слову. Пусть это ver. Тогда к ответу нужно прибавить dpver.

Также, важно было не забыть использовать long long при вычислениях.

Асимптотика: , где w — множество всех слов, которые есть в тексте и в словаре.

467E - Alex and Complicated Task

Данная задача решалась жадно.

Алгоритм решения такой:

Набираем числа из массива a по очереди, пока в последовательности набранных чисел(далее G) не найдется нужная нам четверка. Напоминаю, что нужная четверка чисел имеет вид: [c1, c2, c3, c4] = [x, y, x, y]. Если набрали такую четверку чисел, то добавляем в ответ. Очищаем G и v (далее будет описано, что такое v).

Очевидно, что этот алгоритм оптимален.

Для удобности сжимаем числа в массиве a. То есть каждому числу присваиваем его порядковый номер в отсортированном списке всех уникальных чисел из массива a. Это делается, потому что в дальнейшем нам удобнее использовать числа порядка O(N). Теперь как быстро узнать, что в G найдется нужная нам четверка.

Давайте для каждого уникального числа X хранить список его позиций в G. Назовем этот список vX. Теперь просто можно обработать операцию добавления числа в G. Пусть добавляемое число — это X. Добавим число X в список G. Пусть i — позиция добавленного числа в список G.

Теперь давайте добавим позицию i в список vX.

Можно заметить такой факт:

Если размер списка vx равен 4, то мы нашли нужную нам четверку.

Можно заметить ещё один факт:

Если до добавления мы не нашли нужную четверку чисел, а после добавления нашли, то последнее добавленное число является последним в четверке. То есть наше последнее добавленное число равно c4. Значит мы знаем позицию последнего числа из четверки. Давайте переберем позицию числа c2. Всего возможных позиций числа c2 не больше двух, так как всего позиций, на которых стоит число c2, не больше трех (смотреть предыдущий факт). Одна позиция уже занята числом c4. Итого остается максимум две позиции. Пусть мы проверяем, то что c2 имеет позицию L, а c4 имеет позицию R. Остается только проверить существование таких c1 и c3, что c1 = c3 и их позиции P и Q соответственно. P и Q должны удовлетворять следующим условиям: 1 < P < L, L < Q < R. Это очень легко проверить. Давайте заведем массив T. Ti =  максимальное j, что Gi = Gj. Поддерживать такой массив не составляет труда. Теперь проверка будет требовать только одного запроса: Максимум на отрезке [1, L - 1] в массиве T. Пусть результат запроса равен Z. Если он удовлетворяет условию L < Z < R, то четверка существует. Этим запросом мы нашли позицию числа c3 в списке G. По этим данным мы можем восстановить четверку.

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

Итоговая асимптотика: .

  • Vote: I like it
  • +17
  • Vote: I do not like it

| Write comment?
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

There's also a nice and short solution for E which uses only stack and map/dictionary, check my implementation — 7902705. The idea is taken from enesoncu's code

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Since this was in Russian, I don't think proper discussion happened on this one, so can someone propose a better solution for D?

»
5 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Can someone explain the solution to question C in English clearly? I think google translate messed up the translation.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    To those who need it: Hint: use dp with states k, n.

    Tutorial: The first thing to notice is that each interval needs to be of length m. The thing that strikes is to: First, build an array where the jth element stores the sum of the elements. Now, you can be greedy. choose the interval with the largest sum, then the next non-intersecting interval with the largest sum and so on. But this won't ensure that all k intervals are used. So greedy doesn't work.

    So the solution must be dp. The states are n, k. I tried using n as first and k as second states: I found k as first is better.

    Now, dp[k][n] is going to be max of: dp[k-1][n-m] + sum of interval ending at n = sum[b] and dp[k][n-1].

    This because at each point you can either ignore the interval. Or you can choose it, and then avoid m next points. Because intervals of these points will intersect with the chosen point's interval. At each point, you want the maximum of the two options.

    The answer is at dp[k][n].

    Code: 75654562

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you explain where greedy would fail?

      • »
        »
        »
        »
        5 years ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        i am still a beginner and this is my first comment.hope you can understand. Greedy fails in test cases where by choosing an interval of(l,r) of highest sum you are left with no other interval that you can possibly choosefrom!

        eg-test case->

        • 4 2 2
        • 1 1000 1000 1

        u will choose the (1,2)[array indexed 0] but further you cant choose the other pair.There might be a lot of cases similar to this.Hope you understood

        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          but in that test case it does not matter because we just need to answer the sum...so it will adjust itself...so i think greedy can work

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks!

»
4 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

How to remove TLE in the following python code for Problem C. George and Job

LINK

»
3 years ago, # |
Rev. 2   Vote: I like it -8 Vote: I do not like it

My solution for problem E:

Solution
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem 467C - George and Job you don't even need to precompute prefix sums, since it is guaranteed that $$$m \cdot k \le n$$$, and hence $$$O(nmk) = O(n^2)$$$. There is almost no runtime difference between 245705653 (prefix sums, 186 ms) and 245706424 (naive loop, 187 ms).