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

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

A. Для решения задачи можно было вывести одни из следующих формул:
res = abc - (a - 1)(b - 1)(c - 1), res = ab + bc + ca - a - b - c + 1, или какую любо аналогичную.
Кроме того, задачу можно было решить за O(a + b + c) — аккуратно спускаться от верхнего слоя к нижнему и суммировать общее число плиток.

Автор — Ripatti .

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

Нетрудно понять, что граф состоит из цепочек, циклов и отдельных вершин. Каждую из этих компонент можно легко покрасить нужным образом в 2 цвета, кроме одного случая: циклы нечетной длины. Таким образом, для решения задачи необходимо выкинуть по 1 вершине из каждого нечетного цикла. После данной операции у нас может остаться нечетное число вершин — тогда выкинем еще одну. В итоге получим граф из четного числа вершин, состоящий из цепочек, четных циклов и отдельных вершин. Такой граф легко раскрасить нужным способом.

Авторы — Gerald , Ripatti .

С. Первое решение: разбор случаев.
1. k = 1. Здесь для n ≤ m + 1 нужно 3 сотрудника, а для n > m + 1 — 2 сотрудника, кроме одного хитрого случая: для n = 2, m = 2, k = 1 ответ 4.
2. k > 1. Для n = m ответ 2k + 1, для всех остальных случаев ответ 2k.
Во всех случаях легко построить сами решения, а так же вручную доказать их корректность.

Второе решение: жадность.
Заведем массив достаточно большого размера, в котором будем хранить текущее число работников в каждый из первых несколько дней. Теперь просто будем идти по нему слева направо от 1го для до n + m-го и нанимать работников так, чтобы все было хорошо. А именно: нанимаем работника если в текущий день персонала меньше k или же если в следующий день персонала 0 человек (этот работник нужен чтобы передать ключ).
Можно показать, что это решение работает за O((n + m)k).
Это решение так же работает и для случаев n < m, но за более большую асимптитику.

Авторы — Gerald , Ripatti .

D. Для каждого сектора отсортируем все перемычки по расстоянию от центра паутины. Теперь для каждого сектора при помощи трех указателей (один для данного сектора, 2 для соседних) посчитаем число плохих ячеек. Собственно, все. Главное не запутаться.

Решение за , где m — общее число перемычек.

Автор — Ripatti .

E. Цифровой корень почти всегда равен самому числу по модулю k - 1. Единственное расхождение для цифровых корней 0 и k - 1 — для них обоих число по модулю k - 1 будет 0. Но цифровой корень 0 мы можем получить только из числа вида 00...00, количество которых можно посчитать отдельно. Отсюда легко понять как вычислить количество подстрок с нужным цифровым корнем, зная число подстрок, равных по модулю некоторому числу.

Теперь давайте поймем как получить число подстрок нужного модуля. Будем идти по строке слева направо и поддерживать для каждого модуля количество префиксов с таким модулем в массиве dp[] размера k. Пусть текущая позиция i. Тогда число подстрок с модулем b, оканчивающихся в позиции i, равно числу префиксов левее позиции i с модулем (x - b)mod(k - 1), где x — модуль подстроки s[1... i]. Т.е. просто dp[(x - b)mod(k - 1)].

Чтобы это решение прошло по времени, массив dp[] следует заменить на какой нибудь ассоциативный массив. Например, на std::map в языке С++ или на хэштаблицу.

Итого решение за O(nz), где z — сложность доступа к массиву ( для std::map или O(1) для хэштаблицы).

Автор — Ripatti.

 
 
 
 
  • Проголосовать: нравится
  • +40
  • Проголосовать: не нравится

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

Вопрос по задаче В: как понять, что делать, если у нас 2, 3 или больше треугольников имеют общую вершину?

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

    Видимо, так не бывает — благодаря свойству, что у каждого студента не более двух врагов. (Или я не понял о чём вообще речь...)

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

D. Раз уж мы сортировали, то не ухудшая асимптотику можно искать бинпоиском границы в соседних, что вроде проще.

С. Как такая асимптотика получается в жадном решении и почему при n < m она другая, что-то не очень понял

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

    Кажется понял: подразумевается видимо O((n + m) + ans * n) = O(( n +m)k), если просто отмечать что в следующие n дней мы работаем. Если поддерживать очередь концов дней работ вроде бы получается O(n + m + ans) = O(n + m + (n+m)k) всегда и =O(n + m + k) в нашем случае

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

      В C есть общая стратегия: в первый день нанять k работников, далее, пока нужно, в n·t день нанимаем одного, чтобы передал ключ, и в n·t + 1 берём ещё k - 1 человек. Ответ можно за О(1) посчитать. Отдельный случай — k = 1, там совсем просто.

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

Прекрасный тур, задачи были крайне интересны, даже учитывая, что они здесь всегда такие. Хотя я полтора часа и проторчала с D, так и не пройдя на нем все претесты, впечатление осталось приятное. Спасибо составителям за 2 прекрасных часа!

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

В кой-то веки совсем очевидная E :) Которую я написал только сейчас, надо действительно читать все задачи :(

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

Как доказать формулы в А?

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

    написать общую формулу в духе k = x(a2 + b2 + c2) + y(ab + bc + ac) + z(a + b + c) + q и быстро подобрать коэффициенты)

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

    Ещё способ — см. http://codeforces.ru/blog/entry/5061?locale=ru#comment-101668 Я делал точно так же, только не посчитал нужным об этом писать...

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

    Это наверное не доказательство, но я выводил формулу так:

    • Сначала найдем количество в верхнем левом параллелограмме с размерами b на c. Это будет b·c.

    • Прибавим к ответу "дуги" снизу, длина которых b + c - 1. Таких "дуг" будет a - 1.
    • Т.е. получим формулу: b·c + (b + c - 1)(a - 1). Если её раскрыть, то получится a·b + b·c + c·a - a - b - c + 1.

    Как-то так :)

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

    Например, посмотреть на данный шестиугольник как на сумму трех "прямоугольников". Картинка

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

      можно посмотреть на эту картинку в 3D, тогда получим 3 грани параллерепипеда. Это то же самое, что параллелепипед размера abc без углового параллелепипеда (a-1)(b-1)(c-1). Отсюда очевидно идет моя 1я формула...

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

    это было

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

Мне еще во время соревнования показалось, что задача С намного легче задачи В...

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

Почему никто не применил анти-жаба-квиксорт в D? Судя по беглому анализу решений, осталось бы только 4 АС: 2009123, 2009269, 2010726, 2012646.

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

Почему цифровой корень числа почти всегда равен числу по модулю (k-1)?

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

    Мне тоже пришлось немного подумать, чтобы это понять. Пусть дано число ankn + an - 1kn - 1 + ... + a0. Каждый из членов aiki можно представить в виде ai(k - 1 + 1)i. Разложим это по формуле бинома Ньютона и заметим, что каждый член, кроме последнего члена ai·1, даёт остаток 0 по модулю k - 1. Суммируя по всем i, получаем

    Продолжая по цепочке, придём к утверждению авторов.

    P.S. Почему CF не распознаёт \pmod? :-/

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

      Спасибо, понял.

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

      После разбора узнаем, что d(x) = x % (k-1) (кроме граничных случаев). Ваши выкладки доказывают правоту этого равенства.

      Возникает вопрос: Как участники получили это равенство во время контеста? 1) Это известный факт? или 2) Участники имеют прокаченную мат.часть, чтобы выводить такие вещи самостоятельно?

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

        Это известный факт( по крайней мере, для меня), да и доказывается это легко.

      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится +4 Проголосовать: не нравится
        1. Как минимум для десятичной системы это известный факт.
        2. Если для других систем счисления это не так, то как тогда вообще решать эту задачу? о_О
        3. Значит, и для других систем тоже так.
»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Какими тестами ломали по задаче B div2. 2012128 - а то не могу у себя ошибку найти.

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

Люди, помогите. В задаче В на моем компиляторе (Visual Studio C++ 2010) тесты из примера проходят, отсылаю на проверку через 2005 студию и GNU C++ — Runtime error 1. Что это может быть?

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

    freopen'ы убери, надо использовать stdin/stdout

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

    Вы где-то вылазите за пределы массива ( я так думаю ). А лучше сделайте ссылку на ваш submit. UPD: разобрались.

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

in the tutorial for B its said that : "So, you should drop one vertex from every odd cycle. After that you can get odd number of vertices" can we remove vertex arbitrary??? or we should select the vertex that is in maximum number of odd cycles? for example according to the tutorial we can remove any vertex of following graph at first step: my graph: 5 6 1 2 1 3 1 4 1 5 2 3 4 5 if at first step i remove node 2 or 3 or 4 or 5 after that the graph is still non-bipartite so i should remove one more vertex for example 4 or 5 if at first step i removed 2 or 3 then after removing this two node the graph has odd vertexes but if at first step i remove vertex 1 the new graph is bipartite with even number of vertexes! my main question is : shouldnt we remove the vertex that is in maximum number of odd cycles? thanks in advance!

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

    The problem statement says that no vertex has more than two connections. This means that it can't participate in more than one cycle. In this setting, it doesn't matter which one of a cycle's vertices is removed.

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

    hey safecomp I posted here another explanation of problem B, you can take a look it may help.

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

      tanks ,but with explanation of andreyv i got it! :D , i just didn't read the problem statement carefully ;)

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

thanks

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

In the posted solutions here for C I think that there are some mistakes: First solution:
Case 2- k > 1. If n = m, answer is 2k + 1, otherwise answer is 2k. Is it true???? What about n=3 m=9 k=3?? The solution here is 13 != 2*3=6

I think that this case should be: if k > 1 and m > n the answer is: k*(1+ceil(m/n)) + ((m%n==0)?1:0) if k > 1 and n>m the answer is: 2*k

Second solution: I don't understand what does "This solution also works correctly for cases n < m, but then it has bigger complexity and requires more time" means!! I think it has the same complexity no matter n and m

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    1. The problem statement mandates m ≤ n.
    2. I think it was meant that this solution is slower than the one with case analysis.
    • »
      »
      »
      7 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      Sorry I didn't notice that!!! But the problem is more interesting if m could be greater than n!! :)

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

Can someone please provide a proof of the result of question A — Tiling with Hexagons ?