JOIN       TOURNAMENT LINKS: - Bracket Update
 Room 1: - Summary - Problems - Log - Photos Room 2: - Summary - Problems - Log - Photos Room 3: - Summary - Problems - Log - Photos Room 4: - Summary - Problems - Log - Photos Championship: - Summary - Problems - Log - Photos  Semifinal Room 2 Problem Analysis & Opinion Friday, November 22, 2002

Isoceles
Used as: Level 1

#### 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(n3). 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 a2 + b2 = c2. The converse is also true, and every triangle with a2 + b2 = c2 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++;
}
```

Escape
Used as: Level 2

#### 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 2500002 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;
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){
else if(t is harmful) {
}else{
}
}
}
return -1;
```

SumSort
Used as: Level 3

#### 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. By lbackstrom
TopCoder Member
Author Profile Semifinal Room 2 Chrono Logs CODING PHASE
11:00:04 AM - dgarthur opens the Level One problem
11:00:08 AM - lars opens the Level One problem
11:00:30 AM - reid opens the Level One problem
11:00:31 AM - dmwright opens the Level One problem
11:05:45 AM - reid submits the Level One problem for 193.47 points (final submission)
11:06:19 AM - reid opens the Level Two problem
11:06:30 AM - dgarthur submits the Level One problem for 190.40 points (final submission)
11:06:40 AM - dgarthur opens the Level Two problem
11:12:16 AM - dmwright submits the Level One problem for 172.39 points (final submission)
11:12:30 AM - dmwright opens the Level Three problem
11:13:06 AM - lars submits the Level One problem for 167.75 points (final submission)
11:13:17 AM - lars opens the Level Two problem
11:30:37 AM - lars submits the Level Two problem for 415.89 points (final submission)
11:30:39 AM - reid submits the Level Two problem for 352.56 points (final submission)
11:30:51 AM - dgarthur submits the Level Two problem for 353.69 points (final submission)
11:30:58 AM - reid opens the Level Three problem
11:31:06 AM - dgarthur opens the Level Three problem
11:31:10 AM - lars opens the Level Three problem
12:00:59 PM - dmwright opens the Level Two problem
12:13:41 PM - dgarthur submits the Level Three problem for 465.73 points (final submission)
12:14:12 PM - reid submits the Level Three problem for 461.94 points (final submission)

CHALLENGE PHASE
No Activity 