"16. 24.04.2016 11:00 Grand Prix of South Caucasus" 11:20 and contest still not opened :(
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3690 |
| 2 | jiangly | 3647 |
| 3 | Benq | 3581 |
| 4 | orzdevinwang | 3570 |
| 5 | Geothermal | 3569 |
| 5 | cnnfls_csy | 3569 |
| 7 | Radewoosh | 3509 |
| 8 | ecnerwala | 3486 |
| 9 | jqdai0815 | 3474 |
| 10 | gyh20 | 3447 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 164 |
| 3 | adamant | 163 |
| 4 | TheScrasse | 159 |
| 5 | nor | 157 |
| 6 | maroonrk | 156 |
| 7 | -is-this-fft- | 152 |
| 8 | Petr | 146 |
| 8 | orz | 146 |
| 10 | BledDest | 145 |
How to solve C? We had AC with solution in O(Ans·n·m) but it doesn't seem to be a good complexity.
How to solve it with such complexity?
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.
Nevermind, this solution is wrong.
Did you have this solution accepted? The second statement about logn steps seems to be wrong:
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).
Как решать Е?
У нас квадрат зашел за полторы секунды без особых оптимизаций. Код http://ideone.com/yei7hl
Отдельно разберём случаи p = 1, p = 0. Теперь пусть мы хотим посчитать ответ для i-той клетки. Есть два варианта: мы придём в неё слева или справа. Разберём первый случай, второй учитывается переворотом массива и переменой p, q = 1 - p местами. Получаем
(сделали i + j ходов, из них i слева, j ≤ n - i справа, но последний ход должен быть слева, иначе мы уже посетили нашу клетку раньше). Это есть 
, так как 
, то есть умноженный на i коэффициент перед xi многочлена 
(мы добавили ещё слагаемых для каждого i, но, как несложно убедиться, они всё равно нули), что есть 
(формула для суммы геометрической прогрессии). Посчитать коэффициенты числителя мы можем за O(n) с помощью предпосчитанных логарифмов факториалов, поделить тоже сможем за O(n), так как делим на линейный многочлен.
Еще идея: давайте напишем решение за квадрат, но не динамикой, а прямо комбинаторными формулами (посчитаем, какова вероятность того, что i-ую клетку закрыли на j-ом шаге событием первого/второго типа). Формулы медленные, считать придется слишком долго, надо соптимайзить. Наблюдение: большинство слагаемых очень маленькие и на них можно забить. Оптимайз: зафиксировав клетку и направление, будем перебирать, на каком шаге произошло событие; начнем с центра распределения и пойдем в обе стороны, пока слагаемые не станут слишком маленькие. В зависимости от выбора eps, в худшем случае надо будет посчитать где-то 100-120 миллионов слагаемых.
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