There's an array of values from 1 to n. It isn't sorted. We have to sort it, but there are only to ways to move: third element to beginning or last element to beginning. How to do that ?
Name:
Anonymous2010-11-02 7:03
>>39 5/10, a commendable effort. I wondered what it was doing until I noticed the swap.
Anyway, you can do an insertion sort in Θ(n2).
Name:
Anonymous2010-11-03 8:41
Samefag from >>40 here
I'm just curious how to do that
Simplify the operations a bit; last → first is just rotation; use that to seek, and you have just one operation: move any element two positions forward.
For even sized arrays this lets you move any element anywhere, for odd-sized arrays you have to first rotate the element to the correct modulo-2 position, and you'll end up with a sorted or almost sorted array.
A more interesting question is how to prove the unsolvable cases can't be solved. I found an invariant using the Lehmer code — probably, but it's kind of a pain to make a formal proof.
Name:
Anonymous2010-11-04 11:01
>>46
What do you mean by 'correct modulo-2 position' ?
>>53
This is the fourth of five. The three before it are laughable and doable by either tree search or even simple Haskell list comprehension and mapping/Prolog hacks, if the provided memory is sufficient. The third one is a joke; I'm assuming I'm too tired and missing something.
>>55,57
Remember folks, if you dislike his post or his blog, it's because you're "insecure" or "uneducated." Heaven forbid he could actually be a douche.
>>60
I'll take a knowledgeable, interesting ``douche'' over someone whose only contribution to /prog/ consists of whining in every fucking thread because Xarn once called him a name.
>>54
Bear in mind that these are for kids from 16 to 19 years old, and this is only first of three rounds. Yeah, they are easy, but I would really like to see, how do you solve them using search trees in reasonable time complexity.