Wednesday, December 19, 2007 Match summaryThe 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 ProblemsDepositProfitUsed as: Division One - Level One:
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:
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. TowersAttackUsed as: Division One - Level Three:
First, let's note that a tower t0 is able to damage the enemy if and only if there exists a sequence of "intermediate" towers t1, ..., tn such that:
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.
|
|