Match summary

The last region to compete in Round 1 was also the one with most contestants. One hundred and eleven high school competitors, mostly from Europe, competed to get a positive score. At the end, all but two got their ticket to Round 2. The only red of this region, Zuza, was the favorite of the round, but he lost too many points by resubmitting the hard problem twice. tomekkulczynski got the first place with a 75 point lead over rlp. Third place went to Kalq, who rounded out the all-Polish podium. tomekkulczynski's victory also brought his high-school rating into the red, where his non-HS algorithm rating has been for some time.

The Problems

BadExam

Used as: Division One - Level One:

Value 250

Submission Rate 114 / 114 (100.00%)

Success Rate 112 / 114 (98.25%)

High Score sluga for 249.42 points (1 mins 22 secs)

Average Score 239.97 (for 112 correct submissions)

To solve this problem, you just need to follow the steps explained in the statement. First, calculate the highest mark mmax. After that, modify each mark with the formula of the statement. Then you just need to calculate the average of the marks, summing them all and then dividing by the number of students.

CountingCrowds

Used as: Division One - Level Two:

Value 500

Submission Rate 91 / 114 (79.82%)

Success Rate 85 / 91 (93.41%)

High Score icanadi for 488.20 points (4 mins 26 secs)

Average Score 364.73 (for 85 correct submissions)

The first thing to consider is what the problem is really asking you. You have to do an interpretation of the data, which means you have to decide when each person going through the door is first noticed by the sensor. If you want the minimal interpretation, you can assume that each person is under the sensor until the measure of the sensor contradicts their presence, i.e. the sensor measures a height lower than that person.

With this idea, you have to keep track of the heights of the people going through the door at each moment. And of course, you will suppose that two persons of the same height will never be under the sensor at the same moment. After each measure, you have to update the people that are under the sensor. If any person is taller than the new measure, it means that this person has already left.

tomekkulczynski implemented such an algorithm. Other solutions use an O(n^2) algorithm -- for an example, see icanadi�s solution.

FamilyTravel

Used as: Division One - Level Three:

Value 1000

Submission Rate 63 / 114 (55.26%)

Success Rate 39 / 63 (61.90%)

High Score fpavetic for 884.76 points (10 mins 32 secs)

Average Score 650.39 (for 39 correct submissions)

First of all, we need to translate the problem into a graph problem. We are asked for the shortest path from node 0 to node 1, such that the length of the edges in the path forms a decreasing sequence.

This problem can be solved in a couple of different ways. The most straightforward one was to use Dynamic Programming, a technique that is very useful in TopCoder problems. If you have not heard about it, take a look at this tutorial. We will solve it with a recursive function that will tell us how much it costs to get to node 1 from node u given that the last edge on the actual path has a length of len.

We have to be careful not to fall into a cycle of edges of the same length, which could lead us to a infinite recursion. Thus, we will have to mark which states (which combinations of node and last length) we have visited, so if we visit them again, we can stop the recursion at that level.

int shortest(int node, int len) 
{
  if ( memo[node][len] != -1) return memo[node][len];
  if ( vis[node][len] == 1 ) return infinity;
  vis[node][len] = 1;
  int ret = infinity;
  for(int i=0;i<n;i++)if(graph[node][i]!='0' && dis( graph[len][i] ) <= len )
  {
    ret = Math.Min( ret, shortest( i, dis( graph[len][i] ) ) + dis( graph[len][i] );
  }
  return memo[node][len]=ret;
}

Such a solution was implemented by fpavetic. Other contestants used a kind of breadth-first search algorithm.

By tywok
TopCoder Member