Monday, April 18, 2005 Match summary
tomek strikes again! Out of the three coders who managed to solve all the problems, tomek took
a comfortable lead of almost 300 points. Ten minutes before the end of the coding phase, he
was the only one to have a submission for the 1000 point problem. Ruberik lighted the 'matches' with
blazing speed and claimed the second spot. Zis came in third, more than 100 points behind Ruberik.
The remaining top ten spots were also taken by reds. The challenge round was quite a trill, especially
for the 'MatchCounting' problem, where 151 challenging attempts had been made. As usually, the system
tests claimed even more solutions. But if you happen to be in the same room with natori, system testing
can become pretty boring. With the help of 325 points he gained from challenges, natori climbed his way
up to the fourth place. The ProblemsBarbecueUsed as: Division Two  Level One:
This problem can be reduced to a standard "find the max problem", but first you have to build
the array. One idea is to give each person a score and then, exclude the person with the highest score.
One vote received counts towards exclusion more than any number of votes given, so we can do something like: for (i = 0; i < n; i++) score[i] = 0; for (i = 0; i < voter.length ; i++) { score[voter[i]]++; score[excluded[i]] += 100; }Then, we just return the index of the person with the highest score. maxscore = score[0]; out = 0; for (i = 0; i < n; i++) { if(score[i] > maxscore) { maxscore = score[i]; out = i; } } return out;ATaleOfThreeCities Used as: Division Two  Level Two: Used as: Division One  Level One:
The first thing to do is to determine the optimal distance of connecting a city with another. In order
to do this, you compute the distance between every subway station in one city and every subway station
in the other. Then, you keep the one that is minimal. Here is the function that computes the 'distance'
between two given cities, written in Java: double go(int[] a, int[] b, int[] c, int[] d) { double ret = 1e9; for (int i= 0; i<a.length; i++) { for (int j = 0; j<c.length; j++) { double d1 = a[i]  c[j]; double d2 = b[i]  d[j]; ret = Math.min(re , Math.sqrt(d1 * d1 + d2 * d2)); } } return ret; }As there are three cities, you must find the optimal connecting distance between each of them: double d1 = go(ax,ay,bx,by); double d2 = go(ax,ay,cx,cy); double d3 = go(bx,by,cx,cy);Then, you compare the three distances already found to determine the two whose sum is minimal. return Math.min(Math.min(d1+d2,d1+d3),d2+d3);Some of the solutions that failed on this problem didn't find this minimum correctly when two of the distances were equal. DivisibilityCriteria Used as: Division Two  Level Three:
In this problem you are told a few things you probably know about the usual divisibility properties
of a number when divided by 2, 3 and 7. Then you are asked to find a general template for quickly
assessing whether or not a number is divisible with a given prime, P. This problem may look daunting
at a first glance, but as it can be seen from the first example, the construction of such a 'criterion'
is not that difficult and you can work your way out from there. But there is an even simpler and more
elegant solution: int ret[] = new int[N], mult = 1; for (int i = N1; i ≥ 0; i, mult = (mult * 10) % P) { ret[i] = mult; } return ret;MatchCounting Used as: Division One  Level Two:
This problem proved to be a little unusual, since it required a different set of skills. But as with all
the problems, it is helpful to have an overall look first. long nr=0; digits = n / 7 + 1; prefix = n % 7; if (prefix == 0) nr = 10; if (prefix == 1) nr = 1; if (prefix == 2) nr = 200; if (prefix == 3) nr = 20; if (prefix == 4) nr = 2; if (prefix == 5) nr = 6; if (prefix == 6) nr = 8; while(nr < 1000000000000000000L) nr = nr * 10 + 8; size = 19; while (size > digits) { nr /= 10; size; } return nr;Don't forget that intuition is a powerful weapon... There is no guarantee that a very thoughtful dynamic programming approach is less error prone than a good guess! HiddenTriangles Used as: Division One  Level Three:
A good observation to make is that with any three given segments, you can form at most one triangle.
From this, the first idea that comes to mind is to iterate through all the possible sets of three segments
and count whether or not it is possible to make a triangle. To do this, you take all the three combinations
of two out of three segments and check their point of intersection. If you get an intersection in all the
cases and the intersection points do not coincide, a triangle has been found! 
