http://www.codeforces.com/gym/100155/problem/B
Does anyone have a clue how approach/solve the problem ?
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3831 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | gamegame | 3386 |
10 | ksun48 | 3373 |
# | User | Contrib. |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 160 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
http://www.codeforces.com/gym/100155/problem/B
Does anyone have a clue how approach/solve the problem ?
Name |
---|
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.
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).
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.
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.
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)
Pastebin
Yes, for N=2*10^6 it definitely will give TL...
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