Editorial for COCI '13 Contest 4 #6 Utrka
Submitting an official solution before solving the problem yourself is a bannable offence.
Let us label as the biggest advantage Mirko can achieve on a route with at most
steps which begins in village
and ends in village
. The task is to find the minimal
such that one diagonal element in the matrix
is strictly positive. We also want to know the maximal such diagonal element in the matrix
, as it is the second required output number.
We can notice that if we know and
, we can calculate
with a procedure similar to matrix multiplication. The complexity of this procedure is
.
These observations let us use binary search for and then using fast (matrix) multiplication we calculate
. Unfortunately, the complexity of this procedure is
, which wasn't enough for
of points.
In order to achieve maximum points, it was necessary to calculate matrices for
(complexity
) and then find the minimal
in the procedure which determines its digit by digit in binary notation (from the largest to the smallest digit). The total complexity of this procedure is still
which was sufficient for
of points.
Comments