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 Problems

FunnyBirds

Used as: Division One - Level One:

Value 250

Submission Rate 54 / 56 (96.43%)

Success Rate 52 / 54 (96.30%)

High Score tourist for 249.52 points (1 mins 14 secs)

Average Score 234.48 (for 52 correct submissions)

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:


public class FunnyBirds {

  

  public int gameTime(int n){



    int res = 0;



    while ( n > 0 ){



      int nextNumberToSing = 1;



      while ( n >= nextNumberToSing ) {        

        n -= nextNumberToSing;

        ++nextNumberToSing;

        ++res;

      }



    }

    return res;

  }

}

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:

Can you solve this problem better than O(sqrt(N))?
How is the number of restarts depend on N?

SquareCovering

Used as: Division One - Level Two:

Value 500

Submission Rate 48 / 56 (85.71%)

Success Rate 11 / 48 (22.92%)

High Score K.A.D.R for 429.59 points (11 mins 54 secs)

Average Score 318.66 (for 11 correct submissions)

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:


public class SquareCovering {

  

  final private int INF = 1000000;

  

  int left, right, top, bottom;

  

  boolean thereAreNoPointsInside(int[] px, int[] py){

    for (int i = 0; i < px.length; ++i)

      if  (px[i] > left && px[i] < right && py[i] > bottom && py[i] < top) return false;

    return true;

  }

  

  public int getMinimalSide(int[] px, int[] py){

    

    left = INF; right = -INF; top = -INF; bottom = INF; 

    

    int n = px.length;

    

    for (int i = 0; i < n; ++i) {

      left = Math.min(left, px[i]);

      right = Math.max(right, px[i]);

      bottom = Math.min(bottom, py[i]);

      top = Math.max(top, py[i]);

    }

    

    if (!thereAreNoPointsInside(px, py)) return -1;

    

    int w = right - left, h = top - bottom;

    

    if (w == h) return w;

    

    int diff = Math.abs(w - h);

    

    if (w < h){

      left -= diff;

      if (thereAreNoPointsInside(px, py)) return h;

      

      left += diff; right += diff;

      

      return thereAreNoPointsInside(px, py) ? h : -1;

    } else {

      bottom -= diff;

      

      if (thereAreNoPointsInside(px, py)) return w;

      

      bottom += diff; top += diff;

      

      return thereAreNoPointsInside(px, py) ? w : -1;

    }

  }

}

Exercises:

What if we were to find any smallest covering square, not necessarily with sides parallel to the axes. How would you solve the problem in that case?

PositiveArray

Used as: Division One - Level Three:

Value 1000

Submission Rate 23 / 56 (41.07%)

Success Rate 12 / 23 (52.17%)

High Score tourist for 930.54 points (7 mins 52 secs)

Average Score 588.12 (for 12 correct submissions)

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:

Prove or disprove that the answer will never be greater than (n+m)/2
Can you solve this problem in O(2^n*(n+m)) time (assuming n<=m)?
What if we were looking for a non-negative array, i.e. the one with each row and column's sum strictly greater than zero. Is that going to change the solution?
In non-negative array problem, show that the answer can't be -1.

By it4.kp
TopCoder Member