Tuesday, June 17, 2008 Match summary
The match with a round number 50 was the first after a long pause. Competitors faced rather trivial easy problem, while the medium one turned out to be pretty hard. Challenge phase was very fruitful because of the tricky medium problem, most submissions on which didn't make it to the system testing. tourist from Belarus won the match with a spectacular score of 2008.89 points! He showed very solid time on all three problems and got 8 successful challenges. neal_wu from US took the second place. The winner of ROI 2008 (Russian Olympiad in Informatics) and newcomer to TCHS SergeiRogulenko got the third place. The ProblemsFunnyBirdsUsed as: Division One  Level One:
Let's model the situation described in the problem statement. All we need to know at each second is an amount of birds on a tree and the next number they are going to sing. Having this we can proceed second by second updating those two numbers appropriately. We stop when there are no more birds on a tree. Java solution follows:
This looks pretty simple, straightforward, and this is probably the first idea that comes to ones mind. But why does it work? The number of birds can be as high as one billion, so how do we know that our program will not exceed a time limit? To answer these questions we need to analyze our algorithm. Let's find out when birds will have to reset their counter and start to sing numbers they already know. After K seconds exactly S(K) = 1 + 2 + ... + K = K*(K+1)/2 birds will fly away. We want to know the maximal K such that S(K) <= N. Solving quadric equation we can see that K is proportional to square root of N. More specifically, for N=10^9 birds will restart singing after K = 44720 seconds. After restart the number of birds is not greater than K and since each second at least one bird flies away we can safely assume that the total number of seconds will not be greater than 2*K, which is under 100000 in the worst case. Now we are sure that our program is fast enough!
Exercises:
Used as: Division One  Level Two:
First, let's find minimum rectangle with sides parallel to the axes which contains all given points (inside or on the border). In other words, we find maximum and minimum coordinates, both x and y. These four values represent minimum bounding rectangle. Notice that we cannot make this rectangle smaller because in that case some points would be outside. That is why if there is a point strictly inside the rectangle we immediately return 1. If we cannot make it smaller the only possibility left to make it a square – make it bigger. We have no reason to increase the biggest side of the rectangle, only the smallest one (if they are equal we've found what we need). This idea gives the following solution:
Exercises:
Used as: Division One  Level Three:
Let's notice two important things. First, we never need to pick a row or a column more than once. And second, having chosen the rows and columns we are going to negate, we can make our moves in any order we like. The first observation gives us the following algorithm. Iterate through all subsets of rows and columns and see if the particular subset makes our matrix positive. The complexity of straightforward implementation will be O(2^(n+m)*n*m) where n and m are the number of rows and columns, respectively. Since n+m equals to 36 in the worst case, this algorithm is definitely too slow to pass. The second observation helps us to improve the algorithm and make it O(2^n*n*m) which is fast enough. Indeed, if we can choose any order of moves, we can negate rows first. After that we can see which columns are still negative and negate them (and only them). Finally, we have to ensure that our matrix is positive and update our answer. For a good example, see the solution by tourist. Exercises:

