DKarev's blog

Searching for some RMQ and Hashing problems
By DKarev, 10 years ago, In English

Hello! These days I was learning RMQ. So now i need some problems on which I can keep training. Can you suggest me some Dynamic RMQ problems. It isn't problem if the suggestions are not from Codeforces. And if it isn't too much, can you post some problems with Hashing, please. Thanks and have a nice day ;)

P.S. Sorry if there was already some topics like this ( I didn't find them)

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

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

http://acm.timus.ru/problem.aspx?space=1&num=1989

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

    I know the hashing solution for this problem but I was always wondering if there exist other solutions for this kind of problems where you have some dynamic queries that involve replace, delete or insert and other queries that ask for equality between two substrings or even LCP?

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

This is a bit hard problem that involves hashing and dynamic data structures that allow range queries. (order statistics tree for example)

http://www.spoj.com/problems/STRLCP/

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

http://mindcoding.ro/ct/mc2014r4/pb/palarb ( there is a story at beginning , skip it ) http://www.infoarena.ro/problema/hashuri ( at ending there are some links , but unfortuantely all are in Romanian — hope Google Translate makes a good job )

→ Reply