Hello Everyone, Can someone please tell me how to solve this problem efficiently? I did a bruteforce 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 precalculated 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 precalculated values. How is there a link between solving only the binary representation of K and solving the K entirely. Thanks asked 17 Aug '16, 15:35

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 friendslist 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 friendslists of all gnomes from friendslist of gnome $x$. Denote this lists as friendslists2. 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 frienslists2 of all gnomes from friendslist2 of gnome $x$. And so on for $8, 16, ..,2$^{29}. 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 friendslisti of all gnomes from current answer. So query can be answered in $O(K*N^2 /L)$. answered 17 Aug '16, 17:11
Thanks for the explanation.If I may take an example for instance if t = 3, the binary representation is 011, (so, we know the friendlist1, friendlist2, ... , friendlist32 for all gnomes). If the gnome x is originating the message then the answer is (friendlist2 of friendlist1 of gnome x) ?
(17 Aug '16, 17:38)
2
@codedecode0111 What are you mean by friendlisti of friendlistj? For your testcase answer can be obtain as union of friendlists2 for all gnomes from friendlist1 of x.
(17 Aug '16, 17:51)
@skyfire: I meant the same thing you said. Thanks for confirming the testcase. thumbs up
(17 Aug '16, 18:00)

1) An efficient matrix multiplication technique:
2) Matrix exponentiation using precomputed values:
3) Final answer:
answered 17 Aug '16, 18:09
Did your solution get accepted? If I understand correctly this is $O(m*n^3*log(k)/64)$. I couldn't get 100 with this.
(17 Aug '16, 22:43)
@nibnalin If you look at their latest solution, you see that their solution TLEd for subtasks 2 and 4, so they only got 40 points.
(19 Aug '16, 05:49)
this will pass with a few optimizations though
(22 Aug '16, 21:42)
