SHAIKHGN - Editorial

(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:

Practice
Contest

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.

RELATED PROBLEMS:

1 Like

Please Update the author’s and tester’s solution links.

" the last set of vertices (at distance 2jb2jb) gives the ones at distance kk from vv ".
Could someone, please explain why this is so? I understand that we require paths of length exactly equal to ‘k’. But why the highest power?