Editorial for COCI '11 Contest 1 #6 Skakac


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

A solution with complexity \mathcal O(TN^2):

For each second, starting with 0, we compute a matrix of 1s and 0s, where a 1 denotes a square reachable by the knight in the respective second. The matrix for second 0 has 0s in all positions, except for the starting position of the knight. From each matrix, we can compute the matrix for the next second, up to second T. The next matrix is computed by mapping all 1s to all squares reachable by any of the 8 possible jumps from that square, and then zeroing out all positions blocked during the next second.

The memory complexity of this algorithm is \mathcal O(N^2), since we need only two matrices (the current and the next one) at any moment. This solution is worth 40\% of points.

A solution with complexity \mathcal O(TN):

Instead of the matrix of 1s and 0s, we will use a sequence of numbers, where each number represents a row of the matrix and its binary digits correspond to the 1s and 0s from the previous solution. For simplicity, we will continue to use the term matrix in the remainder of the description.

The mapping of 1s in all 8 directions can now be implemented using bit operations, which is more efficient than the previous solution.

The remaining problem is quickly computing the matrix of squares blocked in second t. Notice that if t is divisible by K_{ij}, then the square (i, j) is blocked during second t.

If K_{ij} is greater than 1\,000, we can simply generate all moments when the square will be blocked, since there will be less than 1\,000 such moments.

If K_{ij} is less than 1\,000, the problem can be solved using prime factorization. Notice that, if K_{ij} divides t, all prime factors of t (including the ones with exponent 0) must have greater or equal exponents than the corresponding exponents in the factorization of K_{ij}.

Let us denote by F(p^q) the matrix with a 1 in position (i, j) if q is greater than or equal to the exponent of the prime number p in the factorization of K_{ij}.

Now the matrix of squares blocked in second t can be expressed as:

\displaystyle F(p_1^{q_1}) \mathbin{\&} F(p_2^{q_2}) \mathbin{\&} \dots \mathbin{\&} F(p_k^{q_k}) \tag{1}

where p_1, p_2, \dots, p_k are all primes less than 1\,000, q_1, q_2, \dots, q_k are their exponents in the factorization of t, and \& is the bitwise AND operation.

The direct computation of the above expression (1) is slow. However, notice that at most 7 primes in a factorization will have positive exponents, while all other exponents will be 0.

Before the main algorithm, we will precompute, for each interval [x, y], the following:

\displaystyle G(x, y) = F(p_x^0) \mathbin{\&} F(p_{x+1}^0) \mathbin{\&} \dots \mathbin{\&} F(p_y^0)

The expression (1) can now be quickly computed by using F(p^q) for all primes with a positive exponent, and the precomputed G for all other primes (with exponents of 0, grouped in at most 8 intervals), combining all values with a bitwise AND.

Now that we can compute the matrix of squares blocked in second t, we can simply apply it to the current matrix of possible positions using a bitwise AND, thus obtaining the final matrix for second t.


Comments

There are no comments at the moment.