Yury_Bandarchuk's blog

By Yury_Bandarchuk, 8 years ago, In Russian

467A - Юра и заселение

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

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

467B - Федя и новая игра

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

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

467C - Юра и работа

Решение этой задачи — динамическое программирование. Изначально нужно посчитать 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 - Федя и реферат

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

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

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

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

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

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

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

467E - Леша и сложная задача

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

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

Набираем числа из массива 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

»
8 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

»
7 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?

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

Can anyone explain the solution to B more clearly ? It is difficult to understand why the TC is O(n*m).

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

    It is O(n*m) because for calculating binary representation of 'x' it takes log(x) which is approximately 'n' and for calculating the answer it runs a loop of 'm' and finds binary representation of each 'x' and compared it with the binary representation of 'm+1' element, which makes the time complexity of O(n*m).

»
3 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.

  • »
    »
    2 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

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

      Can you explain where greedy would fail?

      • »
        »
        »
        »
        2 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

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

          could anyone explain me why i am getting a TLE on TC#55. I think that the complexity of my solution is O(n*k) as there are n*k cells in dp[n][k] that are needed to be filled . Please somebody help me. code : 77034085

        • »
          »
          »
          »
          »
          2 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

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

      Thanks!

    • »
      »
      »
      22 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Was helpful Bro :)

    • »
      »
      »
      10 months ago, # ^ |
      Rev. 3   Vote: I like it 0 Vote: I do not like it

      I tried similar topdown approach with states n, k 132132140. Gets a TLE. I think its due to the access patterns I have.

»
21 month(s) ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

simple solution : B

find out the XOR with (m+1)th player for every player(1,m) and then find the set bit for every XOR operation, if set_bit<=k increase the counter (means (m+1)th player can make that player his friend.

check MY submission :

99611489

  • »
    »
    11 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Try Hamming Weight Algorithm. It is even more efficient, reducing time complexity to O(1). Also you can search for explanation on Population Count.

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

Anyone struggling with problem C you should check out CSES-Book Shop.Transition for C

$$$dp[i][j]=max(dp[i-1][j],dp[i-m][j-1]+pr[i]-pr[i-m])$$$

submission

»
18 months 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

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

In soluation A : In this problem, you just had to count the number of pairs for which qi — pi ≤ 2

It will be ( qi — pi >= 2 )

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

My solution for problem E:

Solution