Editorial : Coyote & roads

kandarprjoshi

Problem Link

https://www.hackerrank.com/contests/da-iict-ipc-02-1/challenges/mr-pompom-and-make-tunnel

Explanation :

If you make a graph such that all points on the 2d plane are connected to all other points and find the minimum spanning tree then you will get a valid answer but you can not store (10^5)^2 edges in adjacency list  so you have to think about reducing the edges. There is a trick in a cost function.You want to find at least one edge for every vertex and it is minimum so we just need to consider  four possibilities. First you have to sort all the points with according to  x coordinate and add the edge between all the consecutive points then sort all the points according to  y coordinate and add the edge between all the consecutive points.Then apply typical minimum spanning tree approach on this graph. In sorting make sure that your compare method have  symmetric relation.

View original post

How to solve linear homogenus difference equatation in logarithmic time

Linear homogeneous difference equation of degree k with constant coefficient is a form:

a[n]=c1a[n-1]+c2a[n-2]+c3a[n-3]+…+ck a[n-k];

where c1,c2,…,ck are real numbers and ck!=0

Solution of this type of equations can be find applying following steps:

Step 1:

Define k*1 dimensional vector A_k with entries { a[n],a[n-1],a[n-2],a[n-3],a[n-4],…,a[n-k+1] }

Step 2:

Define another k*1 dimensional vector A_k-1 with entries { a[n-1],a[n-2],a[n-3],a[n-4],…,a[n-k] }

Step 3:

Represent A_k = (T)*(A_k-1) Here T is a linear operator matrix of dimension k*k

and  ‘*’  is the symbol of matrix multiplication

we can define T as:

T={   {c1,c2,c3,c4,…,ck},

{1,0,0,0, …0}

{0,1,0,0, …0 },

{0,0,1,0, …0 },

{0,0,0,1, …0 },

……………….

……………….

{0,0,0,….,1,0}}

now you can define

A_k=(T^k)*(A_0)

T^k can be computed by recursive squaring procedure which is O(log(n))

so by applying these three steps you can get solution of any linear homogeneous equation  in O(log(n)) .

Here is one problem of code-star which has direct application of this :

Problem:

https://www.hackerrank.com/contests/codestar-long-programming-contest/challenges/alien-2

In this problem the important constrain is that is you can only put white flowers in the bunch of K=5

The no. of sequences which have first red flower are the same as solving this problem with parameter  n-1

because if you are putting red flower at first position then rest of n-1 positions are  independent.

The no. of sequences which have first white flower are the same as solving this problem with parameter  n-5

because if you are putting white flower at first position then you have to put white flowers up to 5th position after 5th position putting flowers on rest of the positions is independent.

so your solution for the parameter n is

ans(n)=no. of n length sequences which have follow the given constraint, therefore

ans(n)=ans(n-1)+ans(n-5);

which is linear homogeneous difference equation so you can find the solution by above three steps

then,

T={ {1,0,0,0,1},

{1,0,0,0,0}

{0,1,0,0,0}

{0,0,1,0,0}

{0,0,0,1,0}}

Java implementation of this problem:

https://ideone.com/fVParM