| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | ecnerwala | 3649 |
| 2 | Benq | 3581 |
| 3 | orzdevinwang | 3570 |
| 4 | Geothermal | 3569 |
| 4 | cnnfls_csy | 3569 |
| 6 | tourist | 3565 |
| 7 | maroonrk | 3531 |
| 8 | Radewoosh | 3521 |
| 9 | Um_nik | 3482 |
| 10 | jiangly | 3468 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 164 |
| 3 | adamant | 161 |
| 4 | TheScrasse | 159 |
| 5 | nor | 158 |
| 6 | maroonrk | 156 |
| 7 | -is-this-fft- | 152 |
| 8 | SecondThread | 147 |
| 9 | orz | 146 |
| 10 | pajenegod | 145 |
Hi! Can i get some help with this problem? https://open.kattis.com/problems/turbo I feel like i need to get elements from a c++ set using their index, which is not possible with a normal set. Is there a better suited data structure? Thanks
https://en.wikipedia.org/wiki/Fenwick_tree This might help, i'm reaing now but just by the name of it, it s pretty obvious that it is what i needed
I think what you're looking for is famously called "finding kth smallest element". There are many ways to do it, you can search on Google and find more about it. I like to use BST, since it's easy for me to understand.
But, for this problem, I don't really think you need anything of that sort. You already know that given numbers are between 1 and N. You just need to note every numbers position in given array, and you know final position, so you know number of swaps directly.
well, yes, but after u moved 1 all the way to the left, all the number that were left of 1 before now have their position incremented by 1. how do u tackle this?
for every number u put in the right position, if it moved to the left, all the numbers left of it are basically shifted to the right by 1. And the analog thin for the big numbers, that moved to the right. What am i missing?
So, this works only because you're "sorting" the extreme ends of the array and not any random middle element.
Let's say initial position of i is a[i] (note: not necessarily a[i] in array ), then when you take i all the way to the left ( assuming it's odd phase ), all elements between i and a[i] are moved to right by 1. But now, you're never going to be concerned about going to the left of i. You can create two sets. Let's name them "before" and "after" for convenience. For every odd phase sorting, you will add 1 before a certain index, so insert that index in the set "before". Similiarly for every even phase sort, you will insert index in set "after". And for each index you can check how many times it's shifted right or left by checking how many times 1 is added to it ( number of elements in "before" after this element ). And similiarly for before
I may have written too many "before" and "after". I hope it's differentiable with the quotes.
Yes i kinda have the same idea but won t this end up in O(n^2) Worst case time?
Since u have to iterate through the set("before" or "after") to find how many elements are there. A good example is when the array is sorted in descending order at the beginning/ I was thinking u can binary search for it but u can t binary search since u can t get element by index from set.
Why do you have to iterate a set. You can use lower_bound function, because set is sorted. Basically, it's a binary search. So worst case is O(NlogN).
UPD: You can't write your own binary search ( or maybe you can, idk ), but you can use the in built lower bound function in sets. http://www.cplusplus.com/reference/set/set/lower_bound/
Fun fact: I am really curious as to how/why you were using sets if you didn't know about lower_bound function xD.
yea and lower_bound gets u an iterator and then i have to use distance which is O(n) And i cant just do lower_bound(x) — set.begin(), compiler won t let me and for good reason. Set has no random access.
Oh sorry sorry. I forgot it's a set. Lol, now I feel like such an idiot ( which I obviously am ). I'm gonna erase some of my dumb comments, you don't mind right? xD. I'll follow this post to see what is the actual intended solution.
i would n t erase. it took me couple of hours at least to realise this. i had the exact same opinion as u. but after a lot of failing i understood my thinking is actually wrong there s no shame imo, we are prone to quick and wrong assumptions
I actually didnt know about lower_bound until this morning, but i found out eventually, except it made me use distance()
i guess i used for the ordering, so basically a priority queue
Use fenwick tree to count the number of items that are present in the array (have not been removed) to the left/right of the element depending on whether it is even/odd parity, and that will be the number of swaps necessary.
Or use order_statistics_tree, of course, but this is nicer.
thanks for the closure mr purple! ultimately i think the order_statistics tree is the best approach as it yields extremely clean and concise code. Yet i'm sad as this tree eluded me during my contest 2day. People should talk more aobut it
Haha, so starting afresh, maybe you need to do the "finding kth smallest" thing here. That's the best I can think of right now.
i might ve found the magical data structure
I don't think a BIT is going to help you in this case. You have to do a range update.
UPD: Oh just read the other comment. We use it differently than adding 1 to each index. Nice.
You can solve with BIT only
Yeah I realized. Thanks a lot. Btw, I've never really understood BIT very well. Can you think of another way of solving this problem? Also, some way to understand BIT properly? Thanks a lot in advance.
Ah, well in actuality I don't understand BIT "properly". I don't know how the indexing and stuff works out. I just use it as a slightly faster and more convenient segment tree for sums.
Other way is just order statistics tree, which provides index of element in log n time. That is probably like 10 lines of code max.
I read about policy based data structure in some blog, by adamant if I remember correctly. Is that what you mean by order statistics tree? Also, thanks a lot for helping out.
Yeah, it's that one.
Okay. Thanks a lot. Will try getting used to that, because I have seen it few times now.
Auto comment: topic has been updated by mitzaku (previous revision, new revision, compare).