JOIN
 Match Editorials
TCHS09 Online Round 1
Saturday, January 3, 2008

## Match summary

Round 1 of 2009 TCHS Tournament attracted 399 competitors, which is more than twice the number of participants in 2008 TCHS Tournament. With at most 500 advancers to Round 2 it was enough to get a positive score to advance, and nearly 90% of the participants managed to accomplish this. The round was much easier than a regular HS match, and some competitors were done with all 3 problems in as little as 20 minutes.

decowboy took the lead after the coding phase due to the fastest total time on the problems, with tourist and Zuza closely following. The challenge phase brought neal_wu +25 points and the win. decowboy and tourist took second and third places, respectively.

# The Problems

SubwayTrip
Used as: Division One - Level One:
 Value 250 Submission Rate 353 / 386 (91.45%) Success Rate 329 / 353 (93.20%) High Score merc90 for 249.44 points (1 mins 20 secs) Average Score 201.92 (for 329 correct submissions)

If you stand still, it will take you L/Ve minutes to reach the bottom of the escalator. If you prefer to walk instead, it will take you L/(Ve+Vy) minutes, so you will arrive to the station t1=(L/Ve - L/(Ve+Vy)) minutes earlier. This will allow you to catch an earlier train if it arrives not earlier than t1 minutes before the moment of your arrival to the station if you choose to stand on the escalator. As follows from the statement, the probability of this event is equal to t1/T.

Note that if t1 is greater than T, you will catch an earlier train for sure, so the probability of this event is 1 instead of t1/T. Most of the failed submissions on this problem either didn't consider this special case or processed it in a wrong way.

BankLoans
Used as: Division One - Level Two:
 Value 500 Submission Rate 336 / 386 (87.05%) Success Rate 312 / 336 (92.86%) High Score xiaowuc1 for 492.96 points (3 mins 24 secs) Average Score 384.67 (for 312 correct submissions)

Since the debtors turn out to be unreliable independently, the expected profit for the set of loans is simply the sum of expected profits for each individual loan. If the debtor turns out to be unreliable, he returns no money, and the bank loses the amount loaned out to him. If the debtor is reliable, he returns both the base amount of the loan and the interest, so the bank gets a profit equal to the amount of the interest. Thus, the expected profit for each loan is PROB/100 * (-AMOUNT) + ( 1 - PROB/100 ) * ( INTEREST ).

To find out the value of PROB for the loan, one had to map the value of CLASS for the loan to a corresponding value of PROB using the information given in riskClasses. This could be done either by using a map with CLASS as a key and PROB as a value or in a more straightforward manner - by storing CLASS and PROB in different arrays and iterating through them to find the wanted CLASS.

MazeReconstruction
Used as: Division One - Level Three:
 Value 1000 Submission Rate 237 / 386 (61.40%) Success Rate 219 / 237 (92.41%) High Score v3ctor for 964.24 points (5 mins 30 secs) Average Score 719.54 (for 219 correct submissions)

First, let's have a look at the representation of the position in the maze and moving between positions. The position in the maze can be described with three parameters: x and y coordinates of the cell (its row and column, respectively) and the direction you're facing. A convenient way to describe the direction is a pair (dx, dy), dx and dy being the changes in x and y coordinates that will take place if you move one cell in this direction (thus, facing south corresponds to (1,0), west - to (0,-1) etc). The three kinds of moves are represented as follows:

• moving forward 'F' updates the coordinates without changing the direction: xF = x + dx, yF = y + dy;
• turning left and right 'L' and 'R' updates the direction without changing the coordinates: dxL = - dy, dyL = dx or dxR = dy, dyR = - dx.
The first part of the problem is to find the size of the maze and the coordinates of your initial position within it (the direction you're facing is already known). This can be done as follows: set the initial coordinates to (0,0) and simulate the process of walking through the maze while storing minimal and maximal values of each coordinate for all visited cells. The number of rows and coulmns of the maze will be equal to (xmax - xmin + 1) and (ymax - ymin + 1), respectively. After adjustment to the new coordinate system (with (0,0) being the north-west corner of the maze) your initial position will be (-xmin, -ymin).

After this, a template of the maze can be created, as a String[] of required size filled with 'X'. The initial coordinates are set to (-xmin, -ymin), and the process of walking through the maze is repeated once more, this time the visited cells being marked with '.'.

Alternatively, we could have stored the coordinates of the visited cells during the first simulation, and for each stored cell (x, y) mark the cell (x - xmin, y - ymin) in the template as visited.

By Nickolas
TopCoder Member