rsFalse's blog

opencup.ru GP of S. Caucasus?
By rsFalse, history, 8 years ago, In Russian

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

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it +6 Vote: I do not like it

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

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How to solve it with such complexity?

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Nevermind, this solution is wrong.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      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).

      → Reply
»
8 years ago, # |
← Rev. 3   Vote: I like it +18 Vote: I do not like it

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

→ Reply