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

opencup.ru GP of S. Caucasus?
Автор rsFalse, история, 9 лет назад, По-русски

"16. 24.04.2016 11:00 Grand Prix of South Caucasus" 11:20 and contest still not opened :(

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

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

How to solve C? We had AC with solution in O(Ans·n·m) but it doesn't seem to be a good complexity.

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

    How to solve it with such complexity?

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

      Build prefix-function automaton for string m. Then for each state and each initial keyword find the state when you will be after feeding to it strings α, h(α), h(h(α)) and so on. Then check each time if hk(1) from initial state leads you to the terminal state.

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

    Nevermind, this solution is wrong.

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

      Did you have this solution accepted? The second statement about logn steps seems to be wrong:

      1 -> 2 3
2 -> 2 2
3 -> 4 4
4 -> 5 5
...
499 -> 500 500
500 -> 3 3
S = 2 500

      Here, the target string is being made directly of 1 (and you can't go deeper), and you need about 500 steps to reach the target.

      Anyway, the answer could be O(n2). This is a tight bound: there is a proof on the upper bound, and a testcase could be constructed. In the testcase above you've fixed the left side of the target string and had to make N-2 moves to reach the right side. Now make the similar construction on the both sides: you'll reach the left part every P-th move, and the right part every Q-th move (P+Q = N-1). Thus the answer is LCM(P, Q) + O(1).

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

Как решать Е?

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

    У нас квадрат зашел за полторы секунды без особых оптимизаций. Код http://ideone.com/yei7hl

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

    Отдельно разберём случаи p = 1, p = 0. Теперь пусть мы хотим посчитать ответ для i-той клетки. Есть два варианта: мы придём в неё слева или справа. Разберём первый случай, второй учитывается переворотом массива и переменой p, q = 1 - p местами. Получаем (сделали i + j ходов, из них i слева, j ≤ n - i справа, но последний ход должен быть слева, иначе мы уже посетили нашу клетку раньше). Это есть , так как , то есть умноженный на i коэффициент перед xi многочлена (мы добавили ещё слагаемых для каждого i, но, как несложно убедиться, они всё равно нули), что есть (формула для суммы геометрической прогрессии). Посчитать коэффициенты числителя мы можем за O(n) с помощью предпосчитанных логарифмов факториалов, поделить тоже сможем за O(n), так как делим на линейный многочлен.

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

    Еще идея: давайте напишем решение за квадрат, но не динамикой, а прямо комбинаторными формулами (посчитаем, какова вероятность того, что i-ую клетку закрыли на j-ом шаге событием первого/второго типа). Формулы медленные, считать придется слишком долго, надо соптимайзить. Наблюдение: большинство слагаемых очень маленькие и на них можно забить. Оптимайз: зафиксировав клетку и направление, будем перебирать, на каком шаге произошло событие; начнем с центра распределения и пойдем в обе стороны, пока слагаемые не станут слишком маленькие. В зависимости от выбора eps, в худшем случае надо будет посчитать где-то 100-120 миллионов слагаемых.

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

How to solve problem H ? I have solved it from the dual problem of the linear optimization but I am not shure I can prove that my integer solution is optimal. Answers in russian are acceptable

→ Ответить