TopCoder SRM 556

DIV 2 250 - ChocolateBar

http://community.topcoder.com/stat?c=problem_statement&pm=12190

You just bought a chocolate bar, each square of the chocolate bar contains a letter in the range 'a' - 'z'. You decide to give this whole chocolate bar to your friend, but he is a really picky guy... he just like chocolate bars that do not contain repeated letters. You are able to cut 0 or more bars from the beginning and the end of your chocolate bar.

You are asked to return the maximum possible length of the chocolate bar that you can share with your friend.

First we are going to explain the naive solution, because the maximum length of the chocolate bar is at most 50, we can simply iterate over all the chocolate bars beginning at index \(i\) and ending at index \(j\), where \(j \geqslant i\). For each of this chocolate bars we can store the frequency of the letters seen so far, if one of the letter frequency is greater or equal than 2, we should not consider this chocolate bar, otherwise, we  calculate the length of the chocolate bar partition which is \(j - i + 1\) and stay with the maximum length as the result. The overall time complexity of this solution is \(O(n^{3})\).

After the contest I was thinking hmmm can we do better? the answer is yes. 

The idea is the following, the new algorithm keep two pointers \(lo\) and \(hi\) the first one represent the beginning of the sequence and the later one the ending. In order to guarantee the correctness of the results, at each step we should maintain the following invariant: "the frequency of the characters between \(lo\) and \(hi\) is less or equal to 1".

Given this, at each step we try to extend our current sequence one element more if the new sequence violate the invariant, we increase the pointer \(lo\) until the invariant holds again, otherwise, continue with the next element of the sequence. Simultaneously, we keep track of the maximum length partition that maintain the invariant, we can easily calculate this with the formula \(hi - lo + 1\). The overall time complexity of this solution is \(O(n + n)\).

DIV 2 500 - XorTravelingSalesman 

http://community.topcoder.com/stat?c=problem_statement&pm=12175

You are a very particular traveling salesman, every time you move to a new city your current profit is calculate as \(P \, \mathrm{XOR}\, V_{i}\) where \(V_{i}\) is the profit cost associated with the \(i\)-th city. You are allowed to move to the same city more that one time. Return the maximal profit that you can achieve.

The main idea to solve this problem is to notice that there is not so many states to consider, we are given maximum 50 cities and each of the V_i cost  do not exceeds 1,023, which give us a total of 51,150 possible states. We can simply iterate over those states using dfs and keep the maximum profit among them.