Match summary

Although 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 Problems

VegetableField

Used as: Division One - Level One:

Value 250

Submission Rate 26 / 44 (59.09%)

Success Rate 22 / 26 (84.62%)

High Score LittlePig for 247.46 points (2 mins 53 secs)

Average Score 215.01 (for 22 correct submissions)

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.

CrazySequence

Used as: Division One - Level Two:

Value 500

Submission Rate 31 / 44 (70.45%)

Success Rate 13 / 31 (4194%)

High Score neal_wu for 490.93 points (3 mins 52 secs)

Average Score 371.96 (for 13 correct submissions)

It is easy to see that the n-th 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 n-th 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
Used as: Division One - Level Three:

Value 1000

Submission Rate 11 / 44 (25.00%)

Success Rate 9 / 11 (81.82%)

High Score v3ctor for 841.63 points (12 mins 49 secs)

Average Score 666.42 (for 9 correct submissions)

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^log₁₀n 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 i-th digit of n. Both i and j will be at most O(log₁₀n), so this approach has O(log²n) complexity. Now, we can solve our problem in O( (B � A) * log²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.

By mateuszek
TopCoder Member