Wednesday, August 1, 2007 Match summaryAlthough TCHS SRM 36 attracted only 44 coders, it featured a very interesting competition. As the easy problem was a bit tougher than usual this time, half of the participants ended up with 0 or even a negative score. The medium was rather straightforward, but one had to be very careful with implementation, while the hard proved to be quite standard with an 81.82% success rate (though only 11 coders managed to submit it). neal_wu won the match due to the 4 successful challenges (despite failing 2 others). Close behind was v3ctor (who was on top after the coding phase), followed by anastasov.bg, who was one of the 2 lucky guys that had their brute force medium solution passed. The ProblemsVegetableFieldUsed as: Division One  Level One:
Here, the constraints were low enough to just brute force over all possible plots and check to see if each meets our requirements or not. From those that met the requirements we will simply choose the biggest. We just need to count the different kinds of vegetables that grow on each plot we generate. See LittlePig's fastest submission for reference. CrazySequenceUsed as: Division One  Level Two:
It is easy to see that the nth number in the sequence is equal to k if and only if: k * (k – 1) / 2 < n <= k * (k + 1) / 2 .The reason for this is that there are k * (k – 1) / 2 numbers less than k in the sequence and k * (k + 1) / 2 numbers less than or equal to k (if you don't understand why, see Wikipedia's article on Arithmetic progression). We need to find the smallest k such that n <= k * (k + 1) / 2. This is enough to solve the problem using binary search: public int nthNumber (String N) { long n = Long.parseLong(N), lo = 1, hi = 2000000000; while (lo < hi) { long mid = (lo + hi) / 2; if (mid * (mid + 1) / 2 >= n) hi = mid; else lo = mid + 1; } return (int)lo; }After playing a bit with our initial condition we can find out that the nth number in the sequence is equal to floor( sqrt( 2n ) + 0.5 ). So we can solve the problem in a constant time (assuming that we can compute a square root in a constant time). This is also a reason why the brute force approach runs in O( sqrt(n) ) time. During the match it turned out that if this approach is written carefully it can pass all the system tests (and it did in two cases). Both these solutions make exactly 1414213562 iterations under 2 seconds. It’s amazing, isn’t it?
CoolNumber
How can we check if a given number is cool? We have to check if there exists a subset of digits that sum up to the half of the sum of all the digits. The most obvious way is to check all the possible subsets of digits with recursion. For a number n, there are 2^{log10n} possible subsets that are equal to O( cubeRoot(n) ). So, if we would like to check all the numbers between A and B using this approach, we would end up with a solution of O( (B – A) * cubeRoot(B) ) time complexity. That doesn’t satisfy us for sure, so we have to think of a different method. This different method is dynamic programming. Let A[i][j] be true if out of i first digits of n we can choose a subset that sum up to j and false otherwise. It’s now obvious that A[i + 1][j] = A[i][j – digit[i + 1]] OR A[i][j] , where digit[i] is the ith digit of n. Both i and j will be at most O(log_{10}n), so this approach has O(log^{2}n) complexity. Now, we can solve our problem in O( (B – A) * log^{2}B ) time, which is more than enough. See v3ctor's solution for a clean implementation. You can also check the very inventive memoization of the naive approach in tranquilliser's solution. 
