Jan_Kuipers is the new Algorithm Champion
Discuss this match
Friday, June 29, 2007
Introduction by Olexiy
Jan_Kuipers is the Algorithm Champion of the 2007 TopCoder Open. Check out Petr's analysis on this year's finals. Congratulations!
There are two important points to realize about this problem:
Given a sorted combined list of the times in the input arrays, you can calculate by what factor you can increase your money in each interval independently. For each interval, if the slopes are both negative you would hold on to all your money (a factor of 1.0). If either stock is positive, you pick the stock with the greater slope and compute the factor as the ending price of the chosen stock divided by its starting price. If the interval is bounded on either end by the other stock changing price, and you are not explicitly given your chosen stock's price at the beginning and/or end of the interval, you just need to compute it by linear interpolation.
Your final profit is $1000 times the product of the factors for each interval, minus your $1000 initial investment.
Let Z[i] be a quantity of all binary, repeating free strings of length i: Z = 2, Z = 2, Z = 4, Z = 6, Z = 12, ...
We should proof that Z[2*n + 1] = 2*Z[2*n] (odd case), and Z[2*n] = 2*Z[2*n-1] - Z[n] (even case).
In the odd case: let's consider the odd string that has some prefix which is equal to a suffix. Let its length be L. If L > n then another shorter prefix with the same property exists, and so on.
This is an example:
01010 => 01010 01010 01010
Thus, if the odd string is not a repeating free it contains a prefix (with length <= n) equals to a suffix. But it means that if we delete the middle character from the string, the resulting string will be non-repeating free too. Obviously that the inverse fact is also correct. If we insert 0 or 1 in the middle of any, even repeating free string, the result will be repeating free too. Therefore, Z[2*n+1]=2*Z[2*n].
In the even case: similarly, if the even string is not repeating free, it has a prefix with length not greater than n and equals to a suffix. Thus we can insert 0 or 1 on the left hand of the middle character in the odd repeating free string. In the most cases the result will be repeating free too. For example, we had XXXYXXX, after inserting the character Z we get XXXZYXXX.
One exception is the resulting string, consisting of two equal halves (XXXZ == YXXX). This exception takes place in Z[n] cases (there are 2^n such strings, but in 2^n-Z[n] of those cases the previous odd-length string has a prefix/suffix with length less than n). So, Z[2*n] = 2*Z[2*n-1]-Z[n].
All these approaches help us to create a function which returns a quantity of repeating free strings matching for the given pattern (it consists of '0', '1' and '?'). For example (odd case): count('?1?0?') = 2*count('?10?'), count('1?100') = count('1?00'). In the even case, we should intersect the left and the right parts of the pattern, and subtract from the result the count(X), where X is an intersection.
To find k-th lexicographical string we should fill the pattern from the left to right and analyze the correspondent quantities.