This topic is meant for solutions and hints to problems from problemset 2 of DASM Programming League 2004. You may post any useful questions and resources here, and I will do my best to format them in to one single document for the benifit of all.
ORDERS by Łukasz Kuszner
MaxSU wrote that using a two-direction linked list gives a TLE.
It is better to try something tree structured, it should be faster, like n log n instaead of n^2.
ORDERS by Michał Czuczman
No need for compicated structures. An array will do.
I used an algorithm based on merge sort (total 70 lines) and it ran quite quick .
HANOI by Łukasz Kuszner
I have used quite naive recurrence approach. Something like to move an n-element tower to a place k means:
find the largest disk D which is not on its place,
put everything what lies above D somewhere else,
put everything smaller than D from destination somewhere else,
move D to desired position, and so on
where moving "everything... " means to find largest disk ....
The problem was: where is that "somewhere else"? In order to determine the "quality" of some position p, I considered how many disks are lying there, what are their sizes and how far is from p to destination. I was trying to choose these p with the smallest number of disks, as small disks as possible and as close to destination as possible.
I was surprised with quite good score without serious effort.
HANOI by Tomek Czajka
I did exactly same kind of thing as Lukasz - recursive solution with a heuristic "where to move" function. I penalize for stacking things on top of each other and for being far from the goal.