You are not logged in. Please login at www.codechef.com 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.

Thanks

asked 17 Aug '16, 15:35

codedecode0111's gravatar image

5★codedecode0111
3201215
accept rate: 0%

edited 13 Oct '16, 13:55

admin's gravatar image

0★admin ♦♦
19.8k350498541


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

link

answered 17 Aug '16, 17:11

skyfire's gravatar image

7★skyfire
762
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★
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) 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.
link

answered 17 Aug '16, 18:09

adiasg's gravatar image

3★adiasg
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) 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?

link

answered 18 Aug '16, 09:30

mahipalsaran's gravatar image

3★mahipalsaran
2389
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
Preview

Follow this question

By Email:

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

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "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:

×1,405

question asked: 17 Aug '16, 15:35

question was seen: 2,633 times

last updated: 13 Oct '16, 13:55