
Match Editorials 
TCHS SRM 46Wednesday, 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
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
attack[x1][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;
}
FoodCollecting
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
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