Get Time
high_school  Match Editorials
Wednesday, November 28, 2007

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

Pawns rate it discuss it
Used as: Division One - Level One:
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
  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;

FoodCollecting rate it discuss it
Used as: Division One - Level Two:
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.

KingsTour rate it discuss it
Used as: Division One - Level Three:
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.


By Rydberg
TopCoder Member