Match Editorials

Match summary

The match attracted 97 registrants, 19 of them newcomers. Coders faced a tricky medium and not so difficult hard - it resulted in 9 people getting all three problems correct and 7 with easy and hard.

In a tough race, thanks to fast solutions for all problems, ahyangyi won the match, followed by spencer with less than 4 points behind and Quelloquialism who took the third place.

The Problems

Value	250
Submission Rate	66 / 84 (78.57%)
Success Rate	59 / 66 (89.39%)
High Score	Quelloquialism for 247.61 points (2 mins 47 secs)
Average Score	201.21 (for 59 correct submissions)

This was a pretty straighforward problem. All we have to do is iterate through all pawn positions and mark the squares that are threatened. Then, we just need to count the number of empty and marked squares on the board. Here goes a sample Java solution:

public int pawnsAttack(String[] pawns){
  
  int [][] attack = new int[10][10];
  
  for(int i = 0; i < pawns.length; i++){
    int x = pawns[i].charAt(0) - 'a' + 1;
    int y = pawns[i].charAt(1) - '0';
    // mark occupied squares
    attack[x][y] = -100;  
    // mark threatened squares
    attack[x-1][y+1]++;
    attack[x+1][y+1]++;
  }
        
  int res = 0;
  
  for(int i = 1; i <= 8; i++)
    for(int j = 1; j <= 8 ;j++) if(attack[i][j] > 0) res++;
        
  return res;
}

Value	500
Submission Rate	34 / 84 (40.48%)
Success Rate	13 / 34 (38.24%)
High Score	spencer for 492.37 points (3 mins 32 secs)
Average Score	353.13 (for 13 correct submissions)

This task turned out to be the most difficult one, although it has a simple greedy solution.

Suppose we want to finish gathering food with n+x workers. It is easy to see that to collect most units of food, we have to hire x workers as quickly as possible. So, the best solution, with n+x workers at the end, consists of two parts:

1. In first rounds, if you have enough food and less than x extra workers - hire new ones
2. When you have x extra workers just collect food till you get enough units.

Clearly, we will never need to use more than neededFood workers, so we can try every possible value of x. Simple simulation for every possible x was enough to pass all the system tests (see spencer's fastest solution). We can also solve this task in linear time using results for x to x+1 and integer division.

Some coders tried dynamic programming as well. There is also other greedy approach - see Nikelandjelo's solution for clean implementation of this idea.

Value	1000
Submission Rate	29 / 84 (34.52%)
Success Rate	16 / 29 (55.17%)
High Score	momtchil for 874.64 points (11 mins 5 secs)
Average Score	667.58 (for 16 correct submissions)

Another chess problem, but this time a more complicated one. At first, this problem seems to have O(1) solution. Unfortunately, it could be too complicated to implement without any mistakes. Instead of this, we will use simple BFS procedure.

Let's denote king's starting position with K, pawn A's starting position with PA and pawn B's starting position with PB. Let's assume we have an optimal king's path. There are 2 possibilities:

1. The king doesn't capture B. Then, he moves to A's square as quick as possible, avoiding squares threatened by either of the pawns.
2. The king captures B. In this case, the king moves to B's square as quick as possible, avoiding squares threatened by either of the pawns. Then, he captures B and moves to A's square as quick as possible, avoiding squares threatened by A.

It's easy to see that the king can always follow at least one of this two possibilities. So, all we have to do is to take better result from BFS(X, PA) and BFS(X, PB)+BFS(PB, PA) (remember to avoid appropriate threatened squares).

Nevertheless, most coders used dynamic programming to solve this task. For a reference, see ahyangyi's solution.