You have to design A keyboard with 63 Keys. 3 rows and 21 columns. Keys are [A-Z], [a-z], [0-9], and [space]
Given a string of length 105 you have to arrange the keys in keyboard in a way that it minimizes the total distance travelled by the finger.
Total distance travelled by finger is: Assume your finger is initially at [1, 1], now you will type each characters from 1 finger, if your finger is at [x, y] and you moves it to [z, w] the distance travelled by finger is |x - z| + |y - w| (Manhattan distance)
To me the problem is very interesting, Any ideas what sort of algorithms are good for such approximation tasks.
Problem Link: 3rd task from Here
Apptica Any comments?
I haven't tried solving this problems, but I already thought about it a bit because I got asked about this problem via Facebook (during the contest, but answered only after).
I would simply start by experimenting with some greedy approaches. E.g. put the most common letter in the middle of the keyboard, the second most common letter right next to it, ... Or count how often each pair of letters appears in the string, and distribute the letters using these numbers as basis. Some greedy approaches might give you good results, some might not. Just experiment a little.
Afterwards you can try to improve your found solutions using heuristic strategies like 2-opt/3-opt (swapping two/three letters on the board and see if the total distance reduces). You can repeat these strategies multiple times until you get stuck at a local minimum. Afterwards you can try algorithms like Simulated Annealing to leave local minimums and you might find even better local minimums.
This should already give quite good results.
Also you should think about how to compute the total distance efficiently, so that you don't have to iterate over the complete input string each time. E.g. you can do it in O(#keys^2), but I'm sure there are even more efficient solutions. It is probably possible to compute the difference between to solutions in O(log #keys) for the 2-opt/3-opt phase.
Something completely different: If this question wouldn't been given in a competitive contest in which the program is executed at some server, I would definitely give Integer Programming a try. This question should be quite easy to model using linear inequalities and might give excellent solutions. However this approach cannot be used here, since I'm not aware of any (fast) Integer Programming library that you simply can copy into you solution.