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

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

426A - Сережа и кружки

Посчитаем сумму всех элементов Sum и значение максимального элемента M. Если Sum - M ≤ S то ответ — да, иначе — нет.

426B - Сережа и развороты

Решим задачу с обратной стороны. Будем пытаться свернуть нашу матрицу как можно больше число раз. Свернуть означает операцию, обратную к описанной в условии. Для проверки, можно ли свернуть матрицу нужно, что бы выполнялись следующие условия:
1). n mod 2 = 0
2). ai, j = an - i + 1, j for all 1 ≤ i ≤ n, 1 ≤ j ≤ m.

425A - Сережа и обмены

Переберем интервал, на котором будет находится максимальная сумма. Для улучшения суммы, мы можем поменять не более K минимальных элемента из интервала на не более K максимальных элементов, не принадлежащих отрезку. Так как n не большое мы можем делать это любым образом, например отсортировать все элементы на интервале по возрастанию и вне интервала по убыванию, а дальше будем менять максимальный элемент из вне интервала на минимальный в интервале по тех пор, пока не поменяем k элементов или не останется не замененных элементов в отрезке или не останется не замененных элементов вне отрезка или операция обмена вообще не будет оптимальной. Сложность авторского решения O(n3·log(n)).

Есть ли у Вас идеи о ток, как решать эту задачу за время O(N) или O(N·log(N)) ?

425B - Сережа и таблица

Заметим, что если у нас есть массив x[1..n], 0 ≤ xi ≤ 1 и y[1..m], 0 ≤ yi ≤ 1, то матрица описанная в условии имеет следующий вид ai, j = xi xor yj.
Если n ≤ k, то мы можем перебрать массив x и с помощью жадного алгоритма найти наилучший y. Иначе у нас найдется хотя бы одно i, что мы не должны менять ничего в строке номер i. Таким образом мы можем просто перебрать строку и выбрав ее за x жадно посчитать y. Из всех строк выберем самую оптимальную. Такая строка найдется, потому что ошибок меньше, чем количество столбцов в которых они могут быть.

Под жадным алгоритмом понимается следующий: будем для каждого элемента из y смотреть: лучше ли будет ответ, если определенный бит будет равен 0 или 1. Что бы проще проверять, что оптимальнее можно просто взять текущую строку(i) и посмотреть: сколько бит в ней совпадают с x, а сколько нет. Если совпадающих больше, то yi = 0, иначе yi = 1.

425C - Сережа и две последовательности

Для этой задачи будем использовать динамическое программирование: dpi, j — минимальный номер позиции удаленного элемента во втором массиве, что мы провели первую операцию j раз и удалили из первого массива не более i элементов.

Разберемся теперь как делать переходы. Находясь в состоянии dpi, j мы можем оставить все как есть и перейти в состояние dpi + 1, j, иными словами сделать dpi + 1, j:  = min(dpi + 1, j, dpi, j). Что происходит, когда мы делаем первую операцию, при фиксированном префиксе по элемент номер i? Нам нужно найти элемент второго массива с номером больше dpi, j и равный ai, пусть это будет элемент номер t, тогда нужно сделать переход dpi + 1, j + 1:  = min(dpi + 1, j + 1, t).

Как быстро искать нужный элемент: просто сделаем вектор вхождений во второй массив для каждого числа и по нему будем запускать бинарный поиск.

425D - Сережа и квадраты

Пускай прямая x = k содержит не более точек. Тогда мы можем просто для каждой пары точек на ней (пускай они будут (k, y1) и (k, y2)) проверить: есть ли квадрат, который содержит их как вершины. То есть на нужно проверить: есть ли в наших входных данных пара точек (k - |y2 - y1|, y1) и (k - |y2 - y1|, y2), или пара (k + |y2 - y1|, y1) и (k + |y2 - y1|, y2).

Удалим все просмотренные точки и отразим оставшиеся относительно прямой x = y. Мы получили ситуацию, что каждая прямая x = k содержит не более точек. Решим задачу так же как и в первый раз.

Теперь нужно научится проверять: есть ли пара точек на некоторой прямой. Запишем все эти пары в вектора для тех прямых, где мы хотим проверить. Допустим, мы проверяем все пары для прямой номер k. Пометим в некотором массиве u для всех точек с абсциссой k uy = k. Теперь пройдем по всем интересующим нас парам (y1, y2). Пара нам подходит, только если uy1 = uy2 = k.

425E - Сережа и множества

Сначала посмотрим на то, как мы считаем величину F(S). Сперва мы сортируем все интервалы по правому концу, а затем при обходе их в отсортированном порядке смотрим: если текущий интервал не пересекается с последним взятым в множество, то просто возьмем его.

Решение нашей задачи будет использовать эту жадность. Решение задачи, это динамика с параметрами:
1). номер позиции, в которой будут заканчиваться поставленные интервалы.
2). количество поставленных интервалов
3). правая позиция последнего поставленного интервала

Как делать переходы: заметим, что считая dpi, count, last мы можем изменить last только на i, либо вообще не изменять. Давайте посмотрим, что произойдет в обеих случаях. В первом случае last меняется на i, тогда мы должны поставить хотя бы один из интервалов [last + 1, i], [last + 2, i], ..., [i, i], таких интервалов ровно i - last. Что бы узнать количество способов поставить их как нам нужно, можно использовать метод включений-исключений, но на самом деле можно просто взять число 2i - last - 1. Все остальные интервалы: [1, i], [2, i], ..., [last, i] мы можем брать как хотим, таким образом имеем 2last способов. Перемножим количества и получим количество переходов из dpi, count, last в dpi + 1, count + 1, i. Если же мы считаем количество переходов из dpi, count, last в dpi + 1, count, last, то просто будем брать число 2last.

Так же стоит не забыть про случай dpi, 0, 0. Из которого тоже нужно делать переходы, которые по своей сути тривиальны.

Таким образом мы получили очень простое решение.

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

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

D can be solved without using sqrt(n) in a solution and dividing lines into large and small. This algorithm works: Fix upper right corner (x0, y0). We have to choose second corner of our square. We have two sets of candidates those of form (x, y0) where x < x0 and those of form (x0, y) where y < y0. Let's iterate over all candidates from smaller set, which will result in O(n^(3/2)) algorithm.

I think that many contestants implemented that solution using this optimization without any knowledge that this will in fact improve complexity and got accepted :P. Frankly saying I didn't know the proof too, but I knew that problem and solution earlier :P.

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

"Is there some ideas how to solve this problem in time O(N) or O(N * log(N)) ?" My solution for Div1 A (Div2 C) runs in O (N*(k^2)) http://codeforces.com/contest/425/submission/6494646

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

    Can you explaint what the state dp[i][j][k][l] means?thx.

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

      Sure

      At any given index ind (0<=ind<n), we have 3 states (st)

      0 means we have not started the targeted interval yet

      1 means we have started the targeted interval, but did not close it

      2 means we have started the targeted interval and closed it

      according to this values, we can decided whether to use the element at the current index or not.

      Skipping an element within the target interval increases the value (up)

      Considering an element outside of the target interval increases the value (dw)

      for a valid solution, st must be 1 or 2, and up = dw

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

        elegant algorithm. But I think you should not initialize the dp[][][][] with -1,since maybe some answer is actually -1.

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

    My solution for Div1/C runs in O(N2K) using DP. 6490996

    But it seems that runs faster than you for the testcases 31 ms < 93 ms

    Do you have any description?

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

    Thanks for solution. I didnt get the greedy one on the tutorial and it is was a good practice for dp.

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

Is it possible to see any valid implementation of 425D - Sereja and Squares of author's way solution? Thanks

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

C. Sereja and Two Sequences can the second action move empty sequences? can you explain the second sample?

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

C. Sereja and Two Sequences

TEST #2
3 4 3006 1000
1 2 3
1 2 4 3

ans = 2
TEST #4
4 3 100000 1290
75575 42837 79021 96022
42837 79021 96022

ans = 3

can anyone explain it for me ? I'm not very sure about the problem.

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

    You can use operation 1 only if last element of prefixes is the same.

    For test 2, you should do first operation 1 with prefixes (1) and (1), getting

    2 3
    2 4 3

    Then you do operation 1 again with prefixes (2) and (2)

    3
    4 3

    As you removed 4 elements from the sequences, you can now do operation 2 with a cost of 4 energy points, for a total of 1000+1000+4=2004 energy points. Note that you cannot remove (3) and (4 3) at the end, because you wouldn't have enough energy to perform operation 2 at the end (the cost would be 1000+1000+1000+7=3007). You NEED to do operation 2 as last operation.

    For test 4, you can remove all elements using operation 1 three times (the first is on (75575 42837), (42837)), and you have enough energy to do it.

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

      thanks. "The second action is worth the number of energy units equal to the number of elements Sereja removed from the sequences before performing this action." I misunderstood.

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

Один вопрос. Что подразумевает автор под словом backtrack? Согласно гуглу: backtrack=отступать. Или я чего-то не понимаю?..

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

    Поиск с возвратом (англ. Backtracking) — общий метод нахождения решений задачи, в которой требуется полный перебор всех возможных вариантов в некотором множестве М.

    В данном случае, когда строк n <= k (k <= 10) можно перебрать все варианты расположения 1 в столбце, таких вариантов будет 0 до 2^(n — 1), из бинарного числа можно получить расположения 1.

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

Can someone explain this solution 6491956 to div1 E?

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

Why is it Giving WA on problem c Div2??

Please help!!

6500849

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

So what is the final time complexity of problem B Div 1 (D Div 2) "Sereja and Table"?

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

Объясните, пожалуйста, что я делаю не так. Div 2. C.

Пример такой:

7 1

2 2 2 -9 2 2 2

Если следовать решению, то 1) находим интервал с max суммой ([1,3]) 2) находим максимум вне интервала, минимум внутри, если надо, меняем найденные числа местами.

в данном случае максимум вне = 2, минимум внутри = 2 — не меняем местами. Но понятно, что ответ неправильный

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

    там же перебирать надо интервалы, т.е. рассмотрим интервал [1,6], свапаем минимум внутри и максимум вне, т.е. 2 и -9, получаем сумму на интервале 12 в данном случае не имеют значения свойства начального интервала, важно лишь то, что из него можно получить

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

Can you translate the Russian language into English?

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

It was also possible to solve Problem 425B — Sereja and Table with backtracking. First of all, the required condition for the table holds if and only if for each 2x2 square inside the table it is true that either the number of 1s is 0, 2 or 4. So we start with finding all the bad squares and putting them into a set. Then try all possible changes of a single bad square (flipping a single number inside it). Since we flipped a single number, only four squares that intersect that number might have changed from bad to good or vice versa, so we should only check them. With a simple optimization this passes the time limit: 6507534

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

What does it mean by "Watched Points" int "425D — Sereja and Squares", http://codeforces.com/contest/425/submission/6573664 Here is my solution, and get WA #25. Can someone help me? Sincerely.

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

    I think by watched points, the author means the points which has already been processed.

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

425B - Сережа и таблица

Если n ≤ k, то мы можем перебрать массив x и с помощью жадного алгоритма найти наилучший y.

Что значит перебрать массив x? Если просто все его возможные значения — то это up to 2^100, что очень много.

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

    Массив x имеет размер n. Значит всего вариантов (2^n), т.к. n<=k, то число способов не превысит (2^10). Вот решение для лучшего понимания 6859654.

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

Грубая опечатка в разборе задачи Серёжа и таблица.

Таким образом мы можем просто перебрать строку и выбрав ее за x жадно посчитать y.

Таким образом мы можем просто перебрать строку и выбрав ее за y жадно посчитать x.

Строка имеет размер m а не n. Значит строка должна быть использована в качестве y.Из-за этого я долго не мог понять разбор этой задачи.

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

achievement unlocked: решение "зависло" :D

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

Can someone re-explain the algorithm of 425B — Sereja and Table? I do not understand it at all.

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

Could someone please explain why the solution to Div1B Sereja and Table works?