How to solve SHAIKHGN (Funny Gnomes) efficiently?

Hello Everyone,

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.

Thanks

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).

2 Likes

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.

1 Like

@skyfire: I meant the same thing you said. Thanks for confirming the testcase. ** thumbs up **

#1) An efficient matrix multiplication technique:

  • 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.
3 Likes

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.

why did u calculated 2,4,8,18…pow(2,30)? is it 'cause k is 1000000000?

@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.

if its not possible to calculate for all from 1 to k , then you do the powers of two , and use them to compute the answers efficiently.

this will pass with a few optimizations though

//