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

# | User | Rating |
---|---|---|

1 | tourist | 3843 |

2 | jiangly | 3705 |

3 | Benq | 3628 |

4 | orzdevinwang | 3571 |

5 | Geothermal | 3569 |

5 | cnnfls_csy | 3569 |

7 | jqdai0815 | 3530 |

8 | ecnerwala | 3499 |

9 | gyh20 | 3447 |

10 | Rebelz | 3409 |

# | User | Contrib. |
---|---|---|

1 | maomao90 | 171 |

2 | adamant | 163 |

2 | awoo | 163 |

4 | TheScrasse | 157 |

5 | nor | 153 |

6 | maroonrk | 152 |

6 | -is-this-fft- | 152 |

8 | Petr | 145 |

9 | orz | 144 |

9 | pajenegod | 144 |

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/17/2024 19:29:53 (j3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

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 ifh^{k}(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(n^{2}). 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).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