Editorial for COCI '11 Contest 1 #6 Skakac
Submitting an official solution before solving the problem yourself is a bannable offence.
A solution with complexity :
For each second, starting with , we compute a matrix of s and s, where a denotes a square reachable by the knight in the respective second. The matrix for second has s 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 . The next matrix is computed by mapping all s to all squares reachable by any of the possible jumps from that square, and then zeroing out all positions blocked during the next second.
The memory complexity of this algorithm is , since we need only two matrices (the current and the next one) at any moment. This solution is worth of points.
A solution with complexity :
Instead of the matrix of s and s, we will use a sequence of numbers, where each number represents a row of the matrix and its binary digits correspond to the s and s from the previous solution. For simplicity, we will continue to use the term matrix in the remainder of the description.
The mapping of s in all 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 . Notice that if is divisible by , then the square is blocked during second .
If is greater than , we can simply generate all moments when the square will be blocked, since there will be less than such moments.
If is less than , the problem can be solved using prime factorization. Notice that, if divides , all prime factors of (including the ones with exponent ) must have greater or equal exponents than the corresponding exponents in the factorization of .
Let us denote by the matrix with a in position if is greater than or equal to the exponent of the prime number in the factorization of .
Now the matrix of squares blocked in second can be expressed as:
where are all primes less than , are their exponents in the factorization of , and is the bitwise AND operation.
The direct computation of the above expression is slow. However, notice that at most primes in a factorization will have positive exponents, while all other exponents will be .
Before the main algorithm, we will precompute, for each interval , the following:
The expression can now be quickly computed by using for all primes with a positive exponent, and the precomputed for all other primes (with exponents of , grouped in at most intervals), combining all values with a bitwise AND.
Now that we can compute the matrix of squares blocked in second , we can simply apply it to the current matrix of possible positions using a bitwise AND, thus obtaining the final matrix for second .
Comments