### rsFalse's blog

By rsFalse, history, 8 years ago,

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

• 0

 » 8 years ago, # |   +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.
•  » » 8 years ago, # ^ |   0 How to solve it with such complexity?
•  » » » 8 years ago, # ^ |   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.
•  » » 8 years ago, # ^ | ← Rev. 2 →   0 Nevermind, this solution is wrong.
•  » » » 8 years ago, # ^ |   +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).
 » 8 years ago, # | ← 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