Need help solving a problem

6 years ago, # |

← Rev. 2 →

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.

→ Reply

6 years ago, # ^ |

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?

→ Reply

6 years ago, # ^ |

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

→ Reply

6 years ago, # ^ |

I may have written too many "before" and "after". I hope it's differentiable with the quotes.

→ Reply

6 years ago, # ^ |

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.

→ Reply

6 years ago, # ^ |

← Rev. 3 →

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.

→ Reply

6 years ago, # ^ |

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.

→ Reply

6 years ago, # ^ |

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.

→ Reply

6 years ago, # ^ |

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

→ Reply

6 years ago, # ^ |

← Rev. 2 →

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

→ Reply

6 years ago, # ^ |

← Rev. 2 →

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.

→ Reply

6 years ago, # ^ |

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

→ Reply

6 years ago, # |

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.

→ Reply

6 years ago, # ^ |

i might ve found the magical data structure

→ Reply

6 years ago, # ^ |

← Rev. 2 →

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.

→ Reply

6 years ago, # ^ |

You can solve with BIT only

→ Reply

6 years ago, # ^ |

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.

→ Reply

6 years ago, # ^ |

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.

→ Reply

6 years ago, # ^ |

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.

→ Reply

6 years ago, # ^ |

Yeah, it's that one.

→ Reply

6 years ago, # ^ |

Okay. Thanks a lot. Will try getting used to that, because I have seen it few times now.

→ Reply