Пожалуйста, подпишитесь на официальный канал Codeforces в Telegram по ссылке https://t.me/codeforces_official. ×

Блог пользователя alphadr

ACPC 2012, Problem B [No Name]
Автор alphadr, 11 лет назад, По-английски

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

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

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
11 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    11 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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).

    → Ответить
»
11 лет назад, # |
← Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

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.

→ Ответить
»
11 лет назад, # |
← Rev. 3   Проголосовать: нравится +1 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    11 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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)

    → Ответить
»
11 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

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

→ Ответить