AzorAhai's blog

Problems on palindromic Tree, treaps and dp optimization using convex hull?
By AzorAhai, history, 8 years ago, In English

Hi guys, Could anyone give me a good list of problems on palindromic Tree and treaps specially implicit treaps and reverse intervals and dp optimization tricks because I can't find good problems on those topics .. Thanks in advance.

  • Vote: I like it
  • +13
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
8 years ago, # |
  Vote: I like it -58 Vote: I do not like it

Google please.

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

For palindromic tree — problems 2057-2061 from timus.

Solutions of all those problems are in Michail Rubinchik's paper (http://arxiv.org/abs/1506.04862v2)

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

thanks so much BekzhanKassenov they are great problems ... could you please help me with problems on the other 2 topics

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

You mentioned treaps and DP optimisation, here's a problem that needs both: Misha and Gym. Though not convex hull trick, it needs a neat knapsack optimisation. TL is slightly strict, use fast I/O.

Here's another treaps problem: Maintaining a sequence. You should see this blog for more.

→ Reply