Hard Problem

I tried hard to find an elegant solution to this one but it appears that brute force is needed. The problem is that calculating every possibility for even the simple examples would easily time out, so one must still find some method for pruning the search tree. Turns out one such method exists which greatly reduces the running time.

If someone is picking after you theres no way to narrow down the numbers to choose from and will have to test them all, but what if you are the last to choose? Do you still have to try every number? Nope. For example, if this is the graph of peoples choices so far and you are last to choose:
Code:
------X--------X-------X-----X-X-----
the ONLY spots you need to check are:
Code:
-----OXO-------XO------XO----XOXO----
So your choice of moves is very limited when you or anyone else chooses last. This might not seem like it helps out a lot but lets choose an example. Say you have approximately 1000 numbers to check and you have one person after you and one person who picked before you. For each of your 1000 moves your opponant has 999 moves, to check each combo would result in 1000*999 possibilities or 999000 states to check. Now use the above trick, you'll only need to check 3 places in the last level, so for each of your 1000 moves the last player has 3 choices, resulting in only 3000 possibilites to check. 999000 vs 3000 is a HUGE difference!

So the algorithm basically goes, recursively try every solution except on the last level where you only choose based off of the above trick. To compute the score for any move, its basically the score above + the score below your number + 1.

For the score below, if you are the lowest number than the score is simply your number - 1. If not, then its (your number-previous number-1)/2. For the score above, if you are the highest number than its (range-your number) and if not its (next number-your number-1)/2.

Only one person submitted code and thats Karthur. Unfortunately I wasn't able to get his code to compile in MSVC++ due to several errors which I'm assuming are compiler dependant. His method appears to compute the correct answer although many items would time out.

So for Karthurs score I give a 9/10 with 1 point being deducted for the timeouts, plus an extra 10 snazzy points for being the only one brave enough to submit an entry for a grand total of 19 points and the contest winner for the hard solution. Congratulations! I highly encourage everyone to give this man some well deserved rep for his hard work!

My solution and his code are attached, let me know if you have any questions, and I'll have the last problem graded and reviewed very soon.