alphadr's blog

ACPC 2012, Problem B [No Name]
By alphadr, 12 years ago, In English

http://www.codeforces.com/gym/100155/problem/B

Does anyone have a clue how approach/solve the problem ?

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

»
12 years ago, # |
  Vote: I like it +2 Vote: I do not like it

I've used a treap with implicit keys, but I know only a Russian article about it (link). It's really interesting for me how to solve this problem without a treap.

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

    Thank you so much :) I've never knew about treap data structure before. I'll take a look at it. Yup, I think there there are other approaches as well (I couldn't find any solutions online tho).

    → Reply
»
12 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

I've attended the ACPC onsite , and there was an analysis session after the contest. The judges mentioned two solutions , one with the data structure you mention , and another one unrelated to it. I recall it involved reading all queries in advance then processing them in a backward manner. Maybe you can contact one of the judges if you are interested.

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

My idea: lets make list of chars with additional pointers at every T positions (not only at begin and at end of the list). Now we can find ith character in O(T) operations (take largest Q such that TQ<=i and move to ith character from that pointer in i-TQ operations), and add character in O(N/T)+O(T) operations (insert new character in the list at position P, and move every pointer that is at position Q, P<=Q, to the left).

If we take T=sqrt(N), then this solution works in O(N*sqrt(N)).

upd. 3451933 — here is the code.

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

    Thank you so much :) That sounds really clever and simple indeed given the small sqrt(N), tho I think it might TLE if N limit became 2e6. btw can you please put your code on pastebin or something similar? (because gym solutions can't be viewed for problems not solved by the user)

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

I've solved it using only BIT. You just need to pre-process the queries in a reverse order so you can find the final string, then you'll already know for each query 'I' what's the position that R is suppose to be. This gives us O( |R|log²|R| ). Here is my solution: http://codepad.org/YQbQ0AOl

→ Reply