You are not logged in. Please login at to post your questions!


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.


asked 17 Aug '16, 15:35

codedecode0111's gravatar image

accept rate: 0%

edited 13 Oct '16, 13:55

admin's gravatar image

0★admin ♦♦

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

skyfire's gravatar image

accept rate: 33%

edited 17 Aug '16, 17:22

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

@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) codedecode01115★

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.

answered 17 Aug '16, 18:09

adiasg's gravatar image

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

@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) noble_mushtak5★

this will pass with a few optimizations though

(22 Aug '16, 21:42) anupam_datta4★

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


answered 18 Aug '16, 09:30

mahipalsaran's gravatar image

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) geek_geek4★
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "title")
  • 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:


question asked: 17 Aug '16, 15:35

question was seen: 2,633 times

last updated: 13 Oct '16, 13:55