Match summary

The last High School SRM before the second TCHS Tournament attracted 127 registrants, 15 of them newcomers. They faced a set of a tricky Easy, a Medium that had more passing solutions than Easy, and a rather simple Hard. After the system tests it turned out that only 81 people got a positive score, and 24 of them got all three problems correct.

neal_wu won the match due to 5 successfull challenges, with spencer and marcina007 rounding out the top three.

The Problems

DepositProfit

Used as: Division One - Level One:

Value 250

Submission Rate 86 / 115 (74.78%)

Success Rate 61 / 86 (70.93%)

High Score marcina007 for 246.12 points (3 mins 34 secs)

Average Score 204.85 (for 61 correct submissions)

To solve this problem, one had to simulate the process of counting monthly interest and adding it to the total balance. The trick was to do it exactly as described in the statement. The easiest way to avoid troubles with doubles imprecision was to convert amount and profit to cents, and to do the further calculations using integer arithmetics.

Java solution follows:

public class DepositProfit {
    public int depositTerm(int amount, int annualInterest, int profit) {
        amount*=100;
        profit*=100;
        int months,balance=amount;
        for (months=0; balance<amount+profit; months++)
            balance+=(balance*annualInterest)/1200;
        return months;
    }
}

TransformingArray

Used as: Division One - Level Two:

Value 500

Submission Rate 92 / 115 (80.00%)

Success Rate 65 / 92 (70.65%)

High Score yuhch123 for 495.60 points (2 mins 40 secs)

Average Score 424.11 (for 65 correct submissions)

At first glance this problem seems absolutely straightforward: perform the transformation N times, and find the smallest element of the final array. The trick is, under the given constraints such implementation is almost sure to fail. If we store the value of "the product of all elements of the array except for the current element" as a variable of integer or long integer type, we'll get an overflow during the first transformation on big arrays like {10000,9999,...,9951}. And if we store it as java.math.BigInteger or another implementation of arbitrary large numbers, we'll get time limit on tests with 100000 transformations.

There exist ways to solve this problem using simulation and a simple note:

if numbers p, a[i] and a[j] are positive and a[i]<a[j], 
then p/a[i]>p/a[j].

If during each transformation we replace each element of the array with a certain number divided by the element, we'll get an array with wrong numbers, but the indices of the smallest, second smallest, ..., greatest element in this array will be the same as in the correct one.

However, the intended solution requires to make one more observation: after one transformation the minimal element of the initial array becomes the maximal element of the resulting array, and vice versa, and two transformations, applied in row, don't change the positions of minimal and maximal elements. Therefore, all we need is to return the index of the smallest element in a for even N, and the index of the greatest element in a for odd N.

TowersAttack

Used as: Division One - Level Three:

Value 1000

Submission Rate 55 / 115 (47.83%)

Success Rate 38 / 55 (69.09%)

High Score LittlePig for 955.64 points (6 mins 10 secs)

Average Score 728.22 (for 38 correct submissions)

First, let's note that a tower t₀ is able to damage the enemy if and only if there exists a sequence of "intermediate" towers t₁, ..., t_n such that:

for i=0, ..., (n-1) the distance between towers t_i and t_i+1 is less than or equal to r.
the distance between tower t_n and the enemy is less than or equal to r.
if the tower can attack the enemy directly, the length of the sequence is 0.

Each intermediate tower halves the energy transmitted, so after passing through a sequence of n towers the energy becomes 2ⁿ times smaller. Thus, to maximize the damage done to the enemy by a tower, we need to minimize the number of intermediate towers (if such sequence doesn't exist, the damage done by this tower is 0). Since each tower can accumulate unlimited energy, individual damages can be maximized independently, and the maximum damage of all towers is equal to the sum of maximum damages of each tower.

To minimize the numbers of intermediate towers, let's represent the input data as an undirected graph, where each vertice corresponds a tower or the enemy, and a pair of vertices is connected with an edge if and only if the distance between corresponding towers (or a tower and the enemy) is less than or equal to r. Then the minimal number of intermediate towers between a tower and the enemy will be equal to the number of vertices in the shortest path between corresponding vertices.

The task of finding the length of the shortest path between vertices in an undirected graph is a typical one. In this case it is convenient to solve it either with breadth-first search (starting with the enemy vertice and finishing when we visited all vertices we could) or with Floyd-Warshall shortest path algorithm. See LittlePig 's solution as a sample of first approach, and neal_wu 's solution as a sample of second one.

By Nickolas
TopCoder Member