(Note: the editorials are written in a hurry and without having solved the problems, so there may be mistakes. Feel free to correct them / inform me.)
PROBLEM LINK:
Author: Nazarbek Altybay
Tester: Sergey Kulik
Editorialist: Xellos
DIFFICULTY:
MEDIUM
PREREQUISITES:
bitset operations
PROBLEM:
Count the vertices which can be reached by moving through exactly k edges (possibly multiple times through any edge) from a given vertex in a directed graph.
QUICK EXPLANATION:
Precompute the sets of vertices reachable from any vertex in k=2^j edges. For a general k, the reachable vertices can be made by combining those sets.
EXPLANATION:
Terminology note: a path in a graph visits each vertex at most once; a walk can visit any vertex or edge any number of times.
This problem can be solved using a trick similar to that used in the LCA algorithm, sparse table or some variants of fast exponentiation - constructing a walk of an arbitrary length from walks of lengths equal to powers of 2. Suppose that we want to find the vertices at distance k from a vertex v (i.e. such that there’s a walk of length k to them), where the binary representation of k is k=2^{j_1}+2^{j_2}+\dots+2^{j_b}. Let’s find the set of vertices V_1 at distance 2^{j_1} from v; then, let’s find the set of vertices V_2 at distance 2^{j_2} from vertices in V_1 etc.; the last set of vertices (at distance 2^{j_b}) gives the ones at distance k from v. There are O(\log{K}) such steps and each step takes time O(N^2), so the time complexity would be O(N^2\log{N}) per query.
How to precompute the vertices at distances 2^j? For j=0, they’re given directly by the matrix g. For any j > 0, we can do the same as above: find vertices at distances 2^{j-1} from vertices at distances 2^{j-1} from each vertex v; those are the vertices at distance 2^j from v. Again, this takes O(N^2) for fixed v and j, so O(N^3\log{K}) in total.
We can also look at the problem using a somewhat more advanced concept: the matrix g is the adjacency matrix and the vertices at distance k from the i-th vertex are given as the i-th row of the matrix g^k - the number in the j-th column of this row is the number of walks of length k from i to j, so vertex j is at distance k from vertex i iff it’s positive. Therefore, the answer to each query can also be found using matrix exponentiation with the same time complexity.
Unfortunately, O((N+M)N^2\log{K}) is too slow. We’ll need some kind of improvement.
SPEEDING UP
The key is in storing the vertices at distance 2^j from each vertex in a more efficient way: as 1-bits in the binary representation of integers. Since a typical integer can only hold up to 64 bits, we’ll need an array of length \left\lceil \frac{N}{64} \right\rceil and if vertex i is at the given distance from the given vertex, then the i\mod 64-th bit in the i/64-th integer of this array (integer division) is 1.
This allows us to speed up the O(N^2) step: if we have a set of vertices V and want to find the vertices at distance k from at least vertex in V, we can take the bitwise OR of the above arrays (bitsets) for each vertex in V; the OR of the i-th integer in each array gives the i-th integer in the final array. Each OR can be done in constant time (and small) due to computer architecture, so the time complexity decreases ~64 times.
With O((N+M)N^2\log{K}/64) time and O(N^2\log{K}) memory, the above approach should pass within the time limit.
AUTHOR’S AND TESTER’S SOLUTIONS:
The author’s solution can be found here.
The tester’s solution can be found here.