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

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

664A - Сложный НОД

Идея задачи — GlebsHP

В этой задачи нужно было рассмотреть два случая:

  1. a = b — отрезок состоит из одного числа, следовательно все числа из этого отрезка делятся на a и не делятся ни на какое число большее, чем a.
  2. a < b — в этом случае НОД(a, a + 1, a + 2, ..., b) = НОД(НОД(a, a + 1), a + 2, ..., b) = НОД(1, a + 2, ..., b) = 1.
Code

663A - Ребус

Идея задачи — gen

Для начала давайте определим, существует ли решение ребуса. Для этого достаточно знать только количество положительных элементов (первый элемент всегда положительный и все знаки вопроса, перед которыми стоит  + ) и количество отрицательных элементов (все знаки вопроса, перед которыми стоит  - ). Обозначим эти количества как pos и neg, тогда минимальная сумма, которую мы можем получить — это min = (1 · pos - n · neg) (все положительные вопросики заменяем на минимальное значение 1, а все отрицательные — на максимальное n), аналогично, максимальная сумма равна max = (n · pos - 1 · neg). Тогда решение существует тогда и только тогда, когда min ≤ n ≤ max.

Пусть мы определили, что решение существует, теперь будем будем постепенно заменять вопросики числами. Пусть мы уже заменили некоторый префикс вопросиков на числа и получили там сумму S, текущий вопросик имеет знак sgn ( + 1 или  - 1) и справа (но не считая текущий) осталось pos_left положительных и neg_left отрицательных элементов. Текущий элемент мы заменим на число x. Как проверить, что мы можем заменить текущий вопросик на x? Точно так же, как мы вначале определяли, существует ли решение вообще. Мы можем найти минимальную и максимальную суммы, которые мы сможем получить — min_left = (S + sgn · x + pos_left - n · neg_left) и max_left = (S + sgn · x + n · pos_left - neg_left) соответственно, тогда мы можем заменить текущий вопросик на число x, если min_left ≤ n ≤ max_left. Как найти подходящее значение x? Можно честно решить систему неравенств, а можно просто перебрать все n значений.

BONUS Пусть k — количество знаков вопроса в ребусе. Докажите, что асимптотика решения с перебором (для примера, смотрите реализацию ниже) — O(k2 + n), а не O(k · n).

Code

662D - Международная олимпиада

Идея задачи — Alex_2oo8

Давайте посмотрим на сокращения, которые получают первые олимпиады. Первые 10 олимпиад (с 1989 до 1998 года соответственно) получают сокращение из одной цифры (IAO'9, IAO'0, ..., IAO'8) — на данный момент все одноцифренные сокращения заняты. Следующие 100 олимпиад (1999 - 2098) получат скоращение из двух цифр (так как последние две цифры у 100 подряд идущий чисел попарно различны). Аналогично, следующие 1000 олимпиад получат сокращения из трех цифр и так далее.

Теперь решим задачу в обратную сторну (по сокращению определим год). Пусть данное сокращение имеет длину k цифр, тогда мы знаем, что до нашей олимпиады прошли все олимпиады с сокращениями длины (k - 1), (k - 2), ..., 1, то есть 10k - 1 + 10k - 2 + ... + 101 = F олимпиад и наша олимпиада была одна из 10k следующих. То есть наша олимпиада проходила в один из годов между (1989 + F) и (1989 + F + 10k - 1), так как мы получили отрезок из 10k подряд идущих чисел, то ровно одно число из этого отрезка будет иметь последние k цифр совпадающие с нашим сокращением, этот год и будет соответствовать нашему сокращению.

Code

662B - Покраска графа

Идея задачи — gen

Решим задачу отдельно для перекраски всего в красный и перекраски всего в синий, и выберем лучший из этих двух вариантов. Далее рассмотрим задачу для перекраски всех ребер в красный.

Понятно, что бессмысленно выбирать одну и ту же вершину дважды, так как во второй раз мы просто поменяем цвета назад, поэтому наша задача — разбить вершины на два множества S и T, где S — это вершины, которые мы выберем для перекраски, а T — вершины, которые мы не будем трогать (все оставшиеся). Пусть вершины u и v соеденены красным ребром, тогда, чтобы цвет ребра остался красным, обе вершины u и v должны принадлежать одному множеству (обе S или обе T). Если же вершины u' и v' соеденены синим ребром, то они должны принадлежать разным множествам (мы хотим поменять цвет этого ребра ровно один раз, значит одна из вершин принадлежит S, а вторая — T).

Теперь наша задача — это 0-1 покраска графа, которую можно решить, к примеру, DFS-ом или BFS-ом. Так как граф может быть несвязный, то необходимо обрабатывать компоненты по одной. Если для какой-то компоненты 0-1 покраски не существует, то получить все ребра красного цвета мы не сможем. Если же для каждой компоненты у нас нашлась 0-1 покраска, то в множество S нам следует добавить меньшую из 0-1 долей, так как мы хотим минимизировать размер множества S.

Code

662A - Азартный Ним

Идея задачи — GlebsHP

Первый игрок не может выиграть только если xor-сумма всех чисел равна 0. То есть задача состоит в том, чтобы посчитать количество способов разложить карточки так, чтобы xor-сумма верхних чисел равнялась нулю.

Пусть , a . Пусть карточки с номерами j1, j2, ..., jk лежат числами b вверх, а все остальные — числами a, тогда xor-сумма такой концигурации равна , то есть . То есть мы хотим посчитать количество подмножеств ci с xor-суммой S.

Заметим следующую особенность — если мы заменим в нашем множестве c1 на , то ответ не изменится. Вместо {c1, c2} мы теперь можем взять , а вместо c2. Поэтому мы можем выполнить следующие преобразования и ответ не изменится:

  1. Выберем число cf, в котором старший бит — еденица, если все элементы нули, то завершаемся
  2. Заменим все остальные ci, в которых старший бит тоже еденица на
  3. Удалим число cf из множество
  4. Повторим действия 1-5 для оставшегося множества
  5. Добавим cf обратно в множество

После такого преобразования мы получим множество из k нулей и n - k чисел со свойством, что старший еденичный бит в этих счилах строго убывает. Как теперь проверить, можем ли получить xor-сумму S? Так как у нас осталось только одно число со старшим битом равным еденице, то старший бит зависит только от того, возьмем мы это число или нет. Так как мы знаем, каким этот бит должен получится в нашей xor-сумме, то мы можем однозначно определить, берем мы это число или нет. Аналогично продолжаем по всем следующим битам. Если в конце мы не получим подмножество с xor-суммой S, то эту xor-сумму получить невозможно (то есть второй игрок не может победить). Если же мы получили xor-сумму ровно S, то количество таких подмножеств будет 2k, так как про n - k ненуллевых чисел мы уже однозначно определили, которые из них нам нужно взять, а из оставшихся k нулей мы можем выбрать произвольное подмножество и xor-сумму это не изменит. В данном случае вероятность победы второго игрока составляет , то есть ответ равен .

Code

662C - Двоичная табличка

Идея задачи — Alex_2oo8

Для начала рассмотрим медленное решение за O(2n · m). Давайте переберем все варианты по строчкам, каждую строчку мы либо будем инвертировать, либо не будем. Всю эту информацию можно сжать в битмаску — число от 0 до (2n - 1), где i-тый бит равен 1, если мы будем инвертировать i-тую строчку и 0, если не будем. Каждую из m колонок мы тоже можем сжать в битмаску над n битами (биты соответствуют значению в данной колонке на каждой из n строчек), обозначим битмаску для i-той колонки как coli. Пусть маска строчек, которые мы будет инвертировать — это mask, тогда после того, как мы инвертируем все соответствующие строчки, в i-той колонке битмаска изменится на . Пусть содержит еденичек, тогда мы можем получить в этой колонке либо (n - k) еденичек (если инвертируем i-тую колонку), либо k (если не будем инвертировать). Тогда для зафиксированной маски строчек mask минимальное количество еденичек, которое может остаться в табличке, равно .

Теперь мы хотим научиться считать последнюю сумму быстрее, чем за O(m). Заметим, что нас не интересует само значение маски , а только количество еденичек в ней (от 0 до n). Поэтому мы можем сгруппировать все колнки по значению , пусть dp[k][mask] — это количество таких i, что , тогда мы можем посчитать сумму для фиксированной маски mask за O(n).

Осталось только научиться быстро считать значения dp[k][mask]. Эти значение можно считать при помощи динамического программирования. dp[0][mask] можно легко посчитать за O(m) для всех mask — просто пробегаемся по всем колонкам и увеличиваем соответствующее значение dp[0][coli] на 1. Для k > 0, coli и mask отличаются ровно в k битах, переберем один из этих битов (бит, в котором будет отличие) и обозначим его за p. Тогда coli и отличаются ровно в (k - 1) битах. Казалось бы, количество таких колонок равно , но нет, так как мы лишними учли все колонки, в которых coli и отличаются в бите p (то есть бит p совпадает у mask и coli). Снова, последнее количество почти равно dp[k - 2][mask], за исключением тех колонок, которые отличаються в бите p от mask. Пусть , продолжая (что-то вроде принципа включений/исключений) мы получим, что количество, которое нас интересует равно dp[k - 1][next] - dp[k - 2][mask] + dp[k - 3][next] - dp[k - 4][mask] + dp[k - 5][next] - .... Что мы получим просуммировав такие значения по всем битам p? Мы получим dp[k][mask] · k, так как каждую колонку мы посчитаем ровно k раз (в каждом из битов, где есть отличие).

Таким образом, мы научились считать все значения dp[k][mask] за O(2n · n3) следующим образом:

Это все еще слишком медленно, но пересчет динамики можно ускорить до O(2n · n2), к примеру, следующим образом:

  

BONUS А вы можете решить эту задачу еще быстрее?

Code

662E - Взламывать или не взламывать

Идея задачи — Alex_2oo8

Первое наблюдение — так как взламывать можем только мы, то суммарный балл любого другого участника не может превышать 9000 (3 задачи по 3000 баллов), поэтому, если мы можем взломать как минимум 90 решений, то мы гарантированно можем занять первое место (только от взломов мы уже получаем 9000 баллов).

Теперь давайте решать задачу, зная, что количество потенциальных взломов не превосходит 90. Для начала — переберем конечную разбалловку (все 63 вариантов). Теперь для каждой из задач мы можем однозначно определить, сколько взломов по ней мы сделаем (максимальное количество, после которого стоимость задачи будет такой, какую мы сейчас зафиксировали). Зная и конечную разбалловку, и количество наших взломов, мы можем посчитать свой суммарный балл. Теперь у нас есть участники, у которых мы ничего не можем взломать, на них мы уже никак повлиять не можем, поэтому можем уже посчитать, сколько из них нас обгоняют. Осталось не более 90 участников, у которых мы можем что-то взломать. Нас интересуют только те из них, кто на данный момент (пока мы у них ничего не взломали) нас обгоняют. Мы хотим как можно больше из них "скинуть" вниз. Эту задачу можно решать при помощи динамического программирования:

dp[p][i][j][k] — максимальное количество учасников среди первых p, которых мы можем "скинуть" вниз, взломав суммарно i раз по первой задаче, j по второй и k по третьей.

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

dp[p + 1][i + 1][j][k + 1] = max(dp[p + 1][i + 1][j][k + 1], dp[p][i][j][k] + 1)

BONUS А вы можете решить эту задачу, если за каждый успешный взлом дают 10 баллов, а не 100?

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

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

А можно поподробнее о том, как мы в задаче С избавились от цикла по f?

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

    Добавил еще одну строчечку в разбор, надеюсь, преобразования посередине теперь должно быть проще восстановить.

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

В задаче С почему правильное такое решение?

Переберем в какой цвет перекрашивать.

Для каждой компоненты отдельно решим 2-SAT, где x[i] — выбираем вершину, !x[i] — не выбираем. Найдем какой-то вектор-решение. Проверим его, и его иверсию. Вот тут не понятно, почему решений всегда 2?

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

    Зафиксируем одну вершину, тогда все остальные находятся однозначно

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

    Покраска 0-1 графа -- это очень частный случай 2-SAT. У этой задачи всегда 0 или 2 решения.

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

А не могли бы вы дать хорошую оценку на время работы задачки E?

То, что написано в разборе, лучше чем 63·90·303·8 > 4·109 я сходу оценивать не умею (8 от того, что мы перебираем маску взломов. Думаю, от нее избавиться несложно, но даже с этим останется 5·108, и это только чистое количество переходов, которые еще как-то надо делать).

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

    Ответил чуть ниже в английской ветке.

    На счет "и это только чистое количество переходов, которые еще как-то надо делать" — переход в данном случае является одной строчкой, в коде из разбора это dp[ci][i][j][k] = max(dp[ci][i][j][k], dp[li][i - ii][j - jj][k - kk] + 1);, причем доступ к памяти здесь очень последовательный, а не в разнобой, да и вообще весь массивчик занимает 2 · 303 · 4B = 216KB (то есть вся память, с которой мы работаем находится достаточно близко), то есть обработка переходов в данном случае имеет очень маленькую константу.

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

The new feature for showing code is really awesome :D

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

In problem To Hack or not to Hack, won't the official approach be too slow? since If I understand correctly, the dp part take O(90^4*2^3), and the enumeration part takes O(6^3), which, when multiplied, is very large

upd: after some rethinking the dp part actually takes O(90*(triple(a,b,c):(a+b+c<90))*8), which the number of triple is around 125580, so it still looks pretty large.

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

    More or less formal approximation of the complexity: 90 hacks is an actual worst case only for scoring 3000 - 3000 - 3000, so, if we have fixed the scoring to be, say, 1000 - 500 - 1500 and we are still allowed to make at least 30 hacks overall, the dynamic programming won't take any time at all, as we are only processing participants that are initially above us, but with 30 hacks and considered scoring we are already taking the first place. So, for scoring 1000 - 500 - 1500 we can approximate the maximal number of hacks on each problem as 10 - 5 - 15 respectively. Thus the total complexity can be approximated as 30 · (5 + 10 + 15 + 20 + 25 + 30)3 · 7 = 243'101'250, in worst case we will have 30 participants with all 3 problems hackable (this way we have an additional factor of 7 for subset of problems that we will hack).

    In practice, it is impossible to design a testcase, where we will have exactly the maximal number of hacks allowed for all of 63 potential scorings. I have just tried some nearly worst cases and the maximal number of DP transitions (taking the solution from the editorial) I was able to achieve is 104'533'689 on the following test case:

    24
    0 0 0
    -1 -1 -1
    -1 -1 -1
    ...
    -1 -1 -1
    

    The reference solution takes approximately 200 ms on this test case.

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

IS There any other approach for problem Rebus ? if you someone know he would help me a lot?

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

    Correct me if I'm wrong. I solved this problem by using binary search. First, at the left side, let's say the number of positive integers is A and that of negative B. Then we can now say that the sum of positive integers(counted A) equals n+abs(negative intergers). All numbers should be -n~n(except 0). So the right side of my form should be in range [n+B*1 ~ n+B*n]. If we suppose one value V in that range, it can be split into A segments. Let's give value (int)V/A to the first of left side. After then, we have only value V-(int)V/A and (A-1) segments. By trying them, we can now figure out if it is possible. First condition : if V/A is larger than n, =>No Second condition : value returned 0 but still have segments => NO Third condition : Have no segments but sill have V > 0 =>No By this, we can adjust V.

    But my question is, I set V just like n+b, n+b*2, n+b*3, ...n+b*n but accepted. Can anyone prove or disprove it's ok or not?

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

Can Someone Explain 662A - Азартный Ним.

Not able to get the editorial

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

Hi !

for the Bonus of problem 'Rubus' I think it can be proved that the code given in the solution works in O(N + K) and not O(n + k^2)

correct me if I am wrong

thanks !

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

I notice that in the tags for 'E. Binary Table', there are 'divide and conquer', and 'fft', would somebody please provide some explanations on that? Thanks in advance.

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

    In fact, it can be solved with an algorithm similar to FFT. It's FWHT — Fast Walsh-Hadamard Transform — an algorithm to calculate the XOR convolution: c[x] = Sum[y = 0 .. 2^n-1] a[y] * b[x XOR y], in O(2^n * n) time.

    Let a[x] be the number of x appeared in the columns, b[x] = min(popcount(x), n-popcount(x)), then the answer for mask is ans[mask] = Sum[x = 0 to 2^n-1] a[x] * b[x XOR mask], which is exactly the XOR convolution and can be calculated with FWHT in O(2^n * n) time.

    Perhaps the one who added the tag couldn't find this algorithm and chose a similar one.

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

can someone please explain about 0-1 graph coloring and some resources to learn it. This topic is quite new to me. Thanks in advance :D

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

    A 0-1 coloring of a graph is a way to color its vertices such that for every edge, the vertices connected by this edge have different colors. You can find if there is a 0-1 coloring of a connected undirected graph using DFS or BFS. Just start from any vertex and say its color is 0, for example. For every vertex adjacent to it that hasn't been visited yet, call dfs for it, and color it the opposite color of the vertex that's being processed now. If after this, there's still an edge that has both endpoint vertices colored the same way, then there's no 0-1 coloring for this graph. Here's how i code it: https://pastebin.com/DVuvH2Rc