×

# How to solve SHAIKHGN (Funny Gnomes) efficiently?

 0 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 asked 17 Aug '16, 15:35 320●1●2●15 accept rate: 0% 0★admin ♦♦ 19.8k●350●498●541

 4 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, ..,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 friends-list-i of all gnomes from current answer. So query can be answered in $O(K*N^2 /L)$. answered 17 Aug '16, 17:11 7★skyfire 76●2 accept rate: 33% 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) ? (17 Aug '16, 17:38) 2 @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. (17 Aug '16, 17:51) skyfire7★ @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:

• 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)$

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

31
accept rate: 0%

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) 6★

@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)
 0 why did u calculated 2,4,8,18...pow(2,30)? is it 'cause k is 1000000000? answered 18 Aug '16, 09:30 238●9 accept rate: 8% 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. (21 Aug '16, 04:36)
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×1,405

question asked: 17 Aug '16, 15:35

question was seen: 2,633 times

last updated: 13 Oct '16, 13:55