|
|
Show all threads Hide all threads Show all messages Hide all messages | Little Guide | Mickkie | 2042. Nikita | 21 Oct 2023 00:05 | 1 | My first attempt use string hashing to check the palindrome with Segment Tree lazy prop. O(Q*K*logK*logN), esp. for the update query and it's TLE 11 However, using Manacher algorithm with Segment Tree you can achieve O(Q*(K+lgN)) Little help: - WA#3 : You're likely answering too much. (K involved) - WA#9 : N=10^5, overflow somewhere | AC finally, but with an ugly solution | mihai.alpha | 2042. Nikita | 23 Sep 2023 17:23 | 1 | For anyone struggling with this problem, here's how I did it: segment trees with lazy updates for the dp O(sqrtN) updates for the string itself (the logN retrieval with the segment trees instead of the O(1) with the sqrt blocks retrieval was too big of a hog it seems, maybe I messed something up) Manacher for the edge cases and dp[i] = dpEven[i] + dpOdd[i] from Manacher So I used the segment trees to do most of the work, and then for the edge cases I used Manacher, so on average I'd get O(sqrt(N) + log(N) + K) for updates and O(log(N) + K) for queries. Does anyone have a less ugly solution? My source code is aroung 15kb (although I used long names for clarity) and around 550 lines long. Also I've seen people's code run a lot faster, under a second (mine ran in 2.7 s) and I was wondering how they did it. Thanks! | AC. segment_tree with brute_force | Shen Yang | 2042. Nikita | 20 Sep 2023 20:49 | 3 | I did it with sqrt(N) blocks, and got tl on 11 too | Help me please! | SProf | 2042. Nikita | 22 Feb 2016 03:36 | 1 | Can someone gives me algorithm or code ??? sabashavidze@gmail.com this is my gmail,thanks | WA#3 | wodesuck | 2042. Nikita | 18 Jan 2016 16:57 | 2 | WA#3 wodesuck 5 Jun 2015 14:08 Re: WA#3 Qantas [SESC 17] 18 Jan 2016 16:57 |
|
|
|