Welcome back to DWITE everyone. First of all, I would like to welcome Cyril onto our DWITE dev team (thanks for helping us out. Hopefully you don't get too bored :P).

This round went fairly well. There was a small issue regarding #5 we forgot to clarify that words like 'Tat' aren't palindromes due to 'T' not being equal to 't'.

Also, as always, feel free to comment on the difficulty/style/etc... of the contest, and to talk about your own solutions as well.

Analyses:

#1) This was a fairly straight forward question involving reversing a string. One should be careful of cases where digits are concatenated to other letters (like '123cba'), as here the digits do get reversed as they are part of a word and don't represent a number.

#2) Since we are given that it is always possible to divide the N stacks into stacks of equal sizes, first determine what the final number of each stack will be. Let c_1, c_2, ..., c_N denote the number of coins in the N stacks, and let f denote the number of coins in a stack after all the moves have been made. Then f = (c_1 + c_2 + ... + c_N) / N, and this is always a whole number. Finally, we then count how many coins should be moved to, or from, each stack to get f coins eventually: abs(f - c_1) + abs(f - c_2) + ... + abs(f - c_N). However, this double counts the number of moves being made, as each coin that is being moved is accounted for once for the pile its been moved from and once for the pile its been moved to. Thus, we divide the value by 2 to get our required number of moves: [ abs(f - c_1) + abs(f - c_2) + ... + abs(f - c_N) ] / 2

#3) Hopefully you guys had as much fun with this problem as I did writing it up. Consider the following sub-problem: Given a line segment AB, with A(ax, ay) and B(bx, by), and a point C(cx, cy), what is the shortest distance from C to AB? If you can answer this, then all you have to do is go through the path Billy takes a line segment at a time, storing the minimum distance from the candystore to each of the segments as you go. Consider the following:
 
                             l1       l2
                          |   |        |   
                    (1) C |   |        | (2) C
                         \|   | (3) C  |    /
                          \   |        |   /
                          |\  |        |  /
                          | \ |        | /
                          |  \|        |/
        ----------------------A--------B-------
                          |
                          |
                          |
                          |
                          |
                          |

There are 3 cases (as shown above):
1) angle CAB is obtuse (i.e. > 90 degrees) in which case CA is the shortest distance from C to AB
2) angle CBA is obtuse (i.e. > 90 degrees) in which case CB is the shortest distance from C to AB
3) C is between the two lines drawn perpendicular to AB and through A and B respectively (i.e. l1 and l2). This case is the one that requires a bit of math.
Consider the following diagram of case 3:

                                       
                          |             
                          |           
                          |        C        C'
                          |       /--------/
                          |      /        /
                          |     /        /
                          |    /        /
        ----------------------A--------B-------
                          |
                          |
                          |
                          |
                          |
                          |
Create a parallelogram through A, B and C, with base AB, by drawing a line through C that's parallel to AB (let's call the 4th corner C'). Then notice that the shortest distance from C to AB is the height of the parallelogram ABCC'. Since we know that the area of a parallelogram is base*height, thus we get that:

   (Shortest distance from C to AB) * (Base of ABCC') = Area of ABCC'
<=> Shortest distance from C to AB = (Area of ABCC')/AB (since AB is the base of ABCC')

The area of ABCC' can be computed by taking the cross product of the vectors CA and AB, or in other words:

Area ABCC' = |(bx - ax)*(ay - cy) - (ax - cx)*(by - ay)|

Thus for case 3), the shortest distance from C to AB is:

|(bx - ax)*(ay - cy) - (ax - cx)*(by - ay)|       |(bx - ax)*(ay - cy) - (ax - cx)*(by - ay)|
-------------------------------------------   =   -------------------------------------------
                   AB                                    sqrt((by - ay)^2 + (bx - ax)^2)

#4) I would like to apologize to the teams who were seeking for a 'non-bruteforce' solution and didn't end up solving it. I realized that the testcases were so small that bruteforce would have worked, so I apologize for that (this question was intended to be a lot harder than that). So I'll illustrate the non-bruteforce solution here. Let n_{d}, n_{d-1}, ..., n_0 be the decimal digits of the input n from left to right (that is n = n_{d}*10^d + ... + n_0 * 10^0). The general idea is that we are going to count the number of times each of these digits were a 0 when counting from 0 to n. Let z(x) denote the number of times the xth digit was a 0 when counting from 0 to n. If the n_{x} (i.e. the xth digit of n) is not a 0, then z(x) = 10^x*a, where a is the number formed by taking the digits from n_{d}, n_{d-1}, ..., n_{x+1} (i.e. the number formed by removing the last x digits of n). And if n_{x} = 0, then z(x) = 10^x*(a-1) + b + 1, where a is as defined before, and b is the number formed by taking only the last x digits of n. You then add up all these counts, and then add 1 to account for the number 0, to get the total number of times your digits turned to a 0 when counting from 0 to n: z(0) + z(1) + ... + z(d) + 1. I know that this is confusing, so here's an example to illustrate this idea:

Lets take n = 2034. We know count how many times each of the digits was a 0 when counting from 0 to n:

z(0) (or unit's digit): The number of times the unit's digit was 0 is 10^0 * 203 = 203. The unit's digit is a 0 at 10, 20, 30, 40, ..., 2020, 2030 (so you notice that this is like counting from 1 to 203 ignoring the unit's digit).

z(1) (or ten's digit): The number of times the ten's digit was 0 is 10^1 * 20 = 200. The ten's digit is a 0 10 times (100, 200, 300, ..., 1900, 2000), and for each of these times, the unit's digit can be anything from 0 to 9 (that's where the 10^1 part of the equation comes from).

z(2) (or hundred's digit): Now, since the hundred's digit is a 0, we get that it was 0 10^2*(2 - 1) + 34 + 1 = 135 times. First we count the number of times the hundred's digit was a 0 with a first digit of < 2 (and this is just 10^2 * (2 - 1) = 100, which are 1000, 1001, 1002, 1003, ..., 1099), and then we count the number of times the hundred's digit was a 0 with first digit 2 (this is only 34 + 1, the + 1 is to account for 2000, whereas the others are 2001, 2002, ..., 2034).

z(3) (the thousand's digit): This is just 10^3*(0) = 0. This makes sense as the most significant digit could never have been a 0.

Thus when counting from 0 to 2034, the number of 0's you encounter is = z(0) + z(1) + z(2) + z(3) = 203 + 200 + 135 + 0 + 1 = 538 + 1 = 539

This is runs pretty quickly, as its time complexity is O(n*d), where d is average number of digits of the numbers from 0 up to n.

#5) There are two ways you can solve this question. One solution is to take the longest common subsequence (http://en.wikipedia.org/wiki/Longest_common_subsequence_problem) of the given word and its reverse. The other solution is to try answering a subproblem instead:
What is the longest palindrome you can form by removing any number of letters from the word formed by taking everthing from the i th letter to the j th letter of the given word? Let longest[i][j] denote this value. We'll now break this up into cases:

1) i = j
2) i th letter of the given word = j th letter of the given word
3) i th letter of the given word  != j th letter of the given word

Case #1: In this case we are dealing with a one lettered word, and clearly longest[i][j] = 1 (as any one lettered is a palindrome, we don't have to remove anything to form a palindrome).

Case #2: If this is the case, then we know for certain that the longest palindrome starts with the i th letter and ends with the j th letter. Thus the problem boils down to finding the length of the longest palindrome you can form by removing any number of letters from the word formed by taking everthing from the (i+1) th letter to the (j-1) th letter of the given word (i.e. longest[i+1][j-1]). Thus in this case longest[i][j] = longest[i+1][j-1] + 2 (the '+ 2' is two account for the fact that the longest palindrome starts with the i th letter and ends with the j th letter, as they are equal)

Case #3: If this is the case, then either the longest palindrome is formed by some letters from the (i+1) th letter to the j th letter, or by some letters from the i th letter to the (j-1) th letter. Since we want the longest palindrome, we'll take the maximum of these two values. Therefore, in this case longest[i][j] = max(longest[i+1][j], longest[i][j-1])

However, we aren't done yet. Adding all these recurrences together and creating a naive recursive function will time out (as each pair of starting and ending letters (i, j) is visited many times by the function). Thus a fix to this is storing the longest[i][j] in a 2D array and either working bottom up (i.e. dynamic programming), or creating a recursive function that makes sure not to visit a pair of starting and ending letters (i, j) more than once (i.e. recursion with memoization). The time complexity of this program is O(n^2), where n is the length of the given word.

I would like to stress that these are few of the many possible solutions that would work for this problem set. Feel free to try coding up some of these problems, the testcases are available at dwite.org.

I hoped you all enjoyed the contest.