Friday, November 22, 2002

Implementation

This is one of the easier problems of this round. The input is limited to 50 points, so there is no problem with simply checking all combinations of three points, which is simply O(n³). Once we have three points, we just have to determine if the three points form a right isoceles triangles. To determine if three points form a right triangle, we have to check and see if each of the three points is the vertex of an isoceles triangle with a right angle. It is trivial to find if the triangle is isoceles, since we can simply use the pythagorean theorem to find the length of each edge coming out of the chosen point. Then, all we have to see is if the triangle is right. You could use some complicated trigonometry to figure this out, but there is a much easier way. We know from the pythagorean theorem, that any right triagle with hypotoneuse c, has a² + b² = c². The converse is also true, and every triangle with a² + b² = c² is a right triangle. So, the solution looks something like:

int count = 0;
for(int i = 0; i<numPoints; i++)
for(int j = i+1; j<numPoints; j++)
for(int k = j+1; k<numPoints; k++){
    int a = (x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]);
    int b = (x[i]-x[k])*(x[i]-x[k])+(y[i]-y[k])*(y[i]-y[k]);
    int c = (x[j]-x[k])*(x[j]-x[k])+(y[j]-y[k])*(y[j]-y[k]);
    if((a == b && a + b == c) || (a == c && a + c == b) || (b == c && b + c == a))
        count++;
}

Implementation

In this problem, we have a graph with up to 500 * 500 = 250000 vertices. Each edge is weighted either 0 or 1. So, clearly a depth first search is out of the question, as it will take 250000² iterations in worst case. Djikstra's, however will run in time easily, with a worst case of 250000*log(250000). However, implementing Djikstra's requires using a priority queue, which is a bit of work. Instead, we can solve this problem with a breadth first search, mainting two simple first in first out queues. We start by breadth first searching from the start, (0,0), to find all locations that can be reached going through 0 harmful locations. As we do this, we maintain another queue of locations adjacent to those which can be reached going through 0 harmful locations and are not deadly. After we find all of the locations that can be reached going through 0 harmful locations, we start working on the other queue which contains all regions reachable going through 1 harmful location. So, we just continually do this, maintaining a working queue, and a frontier queue, where all vertices in the frontier queue require exactly going through exactly one more harmful location than those in the working queue. In pseudocode, where queue is just a first in first out queue, and visited could simply be an array:

queue working, frontier;
set visited;
working.add(0,0);
visited.add(0,0);
int swaps = 0;
while(working is not empty or frontier is not empty){
    if(working is empty){
        working = frontier;
        frontier = new queue;
        swaps++;
    }
    point p = working.removeFirst();
    if(p is (500,500))return swaps;
    for each(t adjacent to p not in visited){
        if(t is deadly)continue;
        else if(t is harmful) {
            frontier.add(t);
            visited.add(t);
        }else{
            working.add(t);
            visited.add(t);
        }
    }
}
return -1;

Implementation

Obviously, with the range going up to 1000000000, sorting all numbers will not work. The most straightforward way to solve this is probably to write a method, which given a target sum, and an integer, top, finds how many numbers between 0 and top, inclusive, have the given sum. This method clearly has to be sublinear, and a simple way to do it is to use dynamic programming on the number of digits, to find the number for each number of digits. You start with 1 digit, and can get each of the sums 0..9 in 1 way. Then, with n+1 digits, you can find how many number there are with a given sum, m, by taking the sum from i = 0 to 9 of the number of ways to get the sum m-i with n digits. Then, given any number you can find the number of ways to get the sum m something like this:

int count(int n, int target){
    if(n==0)return target==0?1:0;
//where dp[i][j] represents the number of ways to get the sum j, with i digits
    int digits = (int)(log(n)/log(10)+1E-9);
    int ret = dp[digits][target];
    ret += count((int)(n-Math.pow(10,digits)),target-1);
    return ret;
}

Once you have this method written, you can easily find the sum at the index with a simple linear search. You then set the index to be the original index minus the number of numbers with a sum which is between 0 and the sum-1, inclusive. This will give you the index of the number in the range that has the correct sum. After that a binary search will allow you find the exact number in logorithmic time.