Hi there! This week in Romania took place the 2014 Olympics in Informatics. I will present , as usual , the statements first and the solutions below. At final I will put links to all the problems and official solutions. There are 6 problems at my age category ( the last two highschool years ) , but I will present the solutions and the statements for my personal 3 favourites from the contest. Excuse me if you find some language/grammar mistakes. ( I try to avoid them but I'm not very good at this )

Statements

Werewolves ( day 1 )

There are 2*N villagers. Every villager has a hunch about who might be a werewolf. If you split the villagers in every possible way in two groups of N villagers , then , if there exist a suspect in both groups for every possible split , he will be the werewolf. Restrictions: 1 ≤ N ≤ 500000 , memory: 3MB. Example:

4
1 1 1 1 1 2 2 3

Solution: 1

Volume ( day 1 )

You have the heights of some portions of a field in a N * M matrix. Your task is to find the volume of water retained in the field. Restrictions: 3 ≤ N, M ≤ 752. For better understanding , let's take an example:

5 5
2 2 3 3 3
2 2 3 1 3
2 3 1 3 3
3 1 3 2 2
3 2 2 2 2

When the water is filles the field the hights will be:

2 2 3 3 3
2 2 3 3 3
2 3 3 3 3
3 2 3 2 2
3 2 2 2 2

So , the volume will be: 2 + 2 + 1 = 5

Permutation ( day 2 )

You are given a permutation of length n and m right rotations of it. There are defined two operation on every permutation of n elements : left rotation – the elements from the positions 2 to n move leftwards and the first number goes on position n — and right rotation – the same thing in the opposed sense. A right rotation of a permutation is defined as the permutation with the right rotation move applied for a certain number of times to the original permutation. Your task is to say which is the minimum number of operations to get all permutations to the same state. Restrictions: 1 ≤ n, m ≤ 100 000.

For the input data below the solution will be 5.

6 5 
3 1 4 2 6 5 
1 1 3 3 

The 5 permutation and the operation will be:

3 1 4 2 6 5 ( +1 right )
5 3 1 4 2 6 ( 0 )
5 3 1 4 2 6 ( 0 )
2 6 5 3 1 4 ( +2 left )
2 6 5 3 1 4 ( +2 left ) 

Solutions

Werewolves

During the contest I've noticed that the principle of Dirichlet can be used there. So , there need to be more than N villagers that have the same suspect. (if there are just N ,than they can be put in one group and the werewolf will not be found)

As a consequence , we have to find if there is a majoritary suspect. The majoritary vote problem is kind of a classic problem , so I will present just the optimal solution. You will abord the problem as a tournament. Every two supporters will fought and the one who remains up at the final might be the good one.

int cand = -1, k = 0;
for (int i=0;i<n;++i)
{
     int a = read();
     if (k == 0)
     {      
          cand = a;
          k = 1;
     }
     else
          if (a == cand)
               k++;
          else
               k--;
}

We will verify , after that , if the remaining suporter is the good one. Looking at the memory restriction , you will have to read the data twice ( once for finding the final candidate , once for verification ). The time complexity will be O(N) and the used memory will be O(1).

Volume

The first abordation that came to my mind during the contest was to begin either with the lowest heights or with the bigest heights.

Begining with the lowest heights we think of using sets of elements , so the best data structure used for this would be the disjoint data sets. This abordation is not very good because every time you merge two disjoint sets you will have to look for the height of the neighboring cell of the matrix. ( in the example for the cell with one you'll find the 3 as lowest neighbour ). You can continue on this abordation , but during the contest I didn't managed to get this at the good complexity. ( at complexity O(N*M*different_elements) a solution like that would have passed 70% from the tests )

Now , another abordation is to interpret the matrix as a graph. The crucial part is that the number of edges in the graph is O(N*M) ( because you have just 4 neighboring cells ). You have to find out for every cell which is the bigest element on the minimum height road from the exterior of matrix to it. In that way , you will know how much water will be in every cell. The simplest way is to use the Bellman-Ford algorithm because you have not much to think about the cost function. ( and , moreover , Bellman-Ford is very fast. ) Let's denote a[i][j] as the heights of the cells in the matrix and D[i][j] as the cost of arriving to the one matrix's cell. Here is my souce and here is how you can calculate the costs:

D[newx][newy] = min( D[newx][newy] , max( D[x][y] , a[newx][newy] ) ); ( x , y are the coordinates of the present cell , newx,newy are the coordinates of the cell where you go ).

Permutation

Even if the problem is not that complicated , I’ve enjoyed it most of all. First of all , notice that the permutation itself does not matter. You will use just the array which descriebes the states of permutations ( for the example : 0 1 1 3 3 ). Note that it would be a good idea to sort that array. Given the fact the array is a permutation you can sort it with Counting Sort:

    for (int i=1,v;i<m;++i)
    {
        F>>v;
        fr[v]++;
    }

    m = 0;
    for (int i=0;i<n;++i)
        for (int j=1;j<=fr[i];++j)
            a[++m] = i;

Let’s try to solve the problem if we have the final state of all permutations. This is very simple : you iterate through the values of the array and add to the result the minimum between the distance if you rotate the permutation just leftwards or just rightwards. Observe that you can split the array in 4 suqences ( possibly of length 0 ) for which the operations will apply :

• sequence [1,p1] – just leftwards
• sequence [p1+1,now-1] – just rightwards
• sequence [now+1,p2-1] – just leftwards
• sequence [p2,n] – just rightwards

The inequality p1 ≤ now ≤ p2 will always hold. This makes clear the fact that we have no surpassings and , therefore , the complexity can be holded at O(N). We will calculate at the first step the sequences if the center is at the first position in the array. In the following steps we’ll just look if points p1 and p2 need to be moved to the right.

    int p1 = 0;
    int p2 = 2;
    int ans = 1<<30;
    for (int i=1;i<=m;++i)
    {
        while ( p1+1 < m && a[i]-a[p1+1] > a[p1+1]+n-a[i] ) ++p1;
        while ( p2 < m && a[p2]-a[i] < n-a[p2+1]+a[i] ) ++p2;
        int now = 0;

        if ( 1 <= p1 && p1 < i )
        {
            now += sum(1,p1) + (n-a[i]) * p1;
        }
        if ( p1+1 < i )
        {
            now += ( (i-1)-(p1+1)+1 ) * a[i] - sum(p1+1,i-1);
        }

        if ( i+1 <= p2 )
        {
            now += sum(i+1,p2) - ( (p2)-(i+1)+1 ) * a[i];
        }
        if ( p2+1 <= m )
        {
            now += (a[i]+n) * (m-(p2+1)+1) - sum(p2+1,m);
        }

        ans = min(ans,now);
    }

Conclusions

From my point of view, the problems were interesting and you had something to learn from them by solving them. You can find the original statements , solutions and tests ( in Romanian ) for all age groups on this site. If you have any suggestions or different solutions for the problems please comment. I will read them next week because in this weekend I will be at the MindCoding Final. Take a look on their site. ( it's in English )