143A - Help Vasilisa the Wise 2

We can enumerate the feasible integers (in fact from 1 to 9) at the left upper corner. Once this value is determined, we can immediately calculate the other three integers. Finally, we only need check whether the four integers meet all the requirements or not.

143B - Help Kingdom of Far Far Away 2

This is a straightforward implememtation problem but one needs take care of some corner cases.

143C - Help Farmer

As A - 1 must be a divisor of n, we can previously compute all the divisors of n and store them in an array. Then, we adopt the first loop to enumerate these divisors, and for each divisor v, we adopt a second loop to enumerate the divisors of n / v. Thus, we can test all the feasible combination of A, B, C, and find out the maximum and minimum values.

143D - Help General

It turns out to be a famous problem, referred to as Knight Tour problem. One can find some simple introduction in Wiki.

Without loss of generality, we assume that n ≤ m (otherwise we can swap their values). The solution consists of three cases:

1) n = 1, the answer is always m.

2) n = 2, we can put knights on columns 0, 1, 4, 5, 8, 9, ..., i.e., 4j + 0, 4j + 1 for j = 1, 2, .... After some simple calculation, one can check that we can put at most 2×(m / 4 + min(2, m%4)) knights.

3) n > 2: as there exists a simple knight tour path, we can color the nodes along the path with black and white, in an alternative manner. Then, it is obvious that the answer should be (nm + 1) / 2.

143E - Help Caretaker

The general idea is using DFS. We focus on the crossing point of “T” and enumerate each cell of the board to check whether this special point can be put there or not. Note that we should also check all the possible rotation (in fact four).

However trivial DFS leads to TLE since the search space is extremely huge. Here are two tricks that can avoid TLE.

1) record the starting position for each recursive call of DFS function: for instance, suppose that we have successfully put a “T” at the current position, and thus for the next recursive call, we should start from the next column (assuming that the enumeration is implemented first row by row and then column by column) or the first column but next row.

2) adopt branch and bound: as we have recorded the starting position for each recursive call, we can immediately calculate how many cells are still not tested, and obtain a trivial upper bound which indicates how many “T”s we can put at most. For instance, suppose that we have put t “T”s and there are still p cells to test. If t + p / 5 is not larger than the current maximum value, the call of function can be immediately terminated (or returned).