Can someone please tell me how to solve this problem efficiently? I did a brute-force by doing a fast matrix exponentiation on the initial adjacency matrix but it was too slow. I saw the solution of xorfire where he just pre-calculated the answer for k = 0 to k = 30 (the maximum bits required to represent 1e9) and later for each input K he found the bit positions in K where it’s 1 and solves it only for these positions by using the pre-calculated values.
How is there a link between solving only the binary representation of K and solving the K entirely.
Consider who will receive a message with joke after 1 minutes, if the creator of joke was gnome with id x. This is a simple friends-list of gnome i. Consider who will receive a message with joke after 2 minutes, if the creator of joke was gnome with id x. It will be a union of friends-lists of all gnomes from friends-list of gnome x. Denote this lists as friends-lists-2. Consider who will receive a message with joke after 4 minus, if the creator of joke was gnome with id x. It will be a union of friens-lists-2 of all gnomes from friends-list-2 of gnome x. And so on for 8, 16, ..,229. This phase can be realized in O(K*N^3 /L). Where K = Log(MaxQueryTime) and for example L = 32.
Next for each query T. In moment t = 0, only x gnome can receive a message - it is a current answer, then for each i-tlh 1-bit in T need to do update, for this unite friends-list-i of all gnomes from current answer. So query can be answered in O(K*N^2 /L).
The square n x n matrix A (adjacency matrix) is made only of 1’s and 0’s.
The standard multiplication technique for matrices is an O(n^3) method.
For matrix C = A*B, C[i][j] = OR(A[i][k]\ AND\ B[k][j]) for k from 1 to n.
By storing columns in A and rows in B as binary numbers, we can get C[i][j] by checking if any bit in ( (ith row of A) OR (jth row of B) ) is set.
This would get down the complexity for matrix multiplication to O(n^3 / 64).
#2) Matrix exponentiation using pre-computed values:
Pre-compute and store values of A^1,A^2,A^4,A^8… till A^(2^30) by repeated squaring.
To compute A^k, find out the positions at which bit is 1 in binary representation of k. Start out with an identity matrix and multiply only with those matrices corresponding to the bit which is set. If ith bit is set, multiply with A^(2^i).
This has a complexity of O(n^3 * log(k) / 64)
#3) Final answer:
The ith row of A^k will have 1 at jth column if there is a walk of length k from i to j.
Checking the xth (joke creator’s) row in A^k will give the answer.
Thanks for the explanation.If I may take an example for instance if t = 3, the binary representation is 011, (so, we know the friend-list-1, friend-list-2, … , friend-list-32 for all gnomes). If the gnome x is originating the message then the answer is (friend-list-2 of friend-list-1 of gnome x) ?
@codedecode0111 What are you mean by friend-list-i of friend-list-j? For your testcase answer can be obtain as union of friend-lists-2 for all gnomes from friend-list-1 of x.