Entering edit mode

Click here to Practice

Submit Problem to OJ

The developers of Hackerland want to construct a network of servers across the country to scale their applications. The country of Hackerland can be represented as a large coordinate grid and the developers have installed n servers across the country. The *ith* server is located at coordinate (x[i],y[i]).

The cost of connecting any two servers indexed i and j is mint( *|x[i]-x[j]|,|y[i]-y[j]|* ) where |a| represents the absolute value of an integer a.

Given the arrays x and y of *n* integers each, find the minimum cost of constructing the network such that every server is reachable by every other server via some direct or indirect connections.

**Example:**

Suppose *n* = 3, x = [2, 4, 8], and y = [6, 10, 9].

The servers are located at (2,6), (4, 10), and (8,9). It is optimal to connect the first and the second servers and the second and the third server at costs min( |2-4|, |6-10| ) = 2 and min( |4-8|, |10-9| ) = 1 respectively. Hence the minimum total cost to construct the network will be 2+1=3.

**Function Description**

Complete the function *getMinCost* in the editor below.

*getMinCost* has the following parameters:

*int x[n]*: The x-coordinates of the servers *int y[n]*: The y coordinates of the servers

**Returns**

*int*: the minimum possible cost to construct the network such that every server is reachable from every other server

**Constraints**

- 2 <= n <= 10^5
- 0 <= x[i],y[i] <= 10^9
- There can be multiple servers at the same coordinates

Click here to Practice

Submit Problem to OJ

A student in Hacker School is provided with an n days schedule in which each day, up to *m* hours of lecture classes take place.

The schedule of the school is given by a binary matrix *schedule[][]* where *scheduled[i][j]* = '1' denotes that there is a lecture on the *jth* hour of the *ith* day and *schedule[i][j]* = '0' denotes that there is no lecture on the *jth* hour of the *ith* day.

In a single day, if the student attends the first lecture at the *xth* hour and the last lecture at the *yth* hour, then it takes them *(y-x+1)* hours of time to attend school on that day. The student is allowed to skip at most *k* lectures in total for all the *n*-days. Find the minimum total amount of time (in hours) the student needs to attend school, including all the *n* days if the lectures to be skipped are chosen optimally.

**Example**

Consider *n = 1, m=5, schedule[][] = ['10001']* and *k-1*.

The student can skip the last lecture of the first day, that is, *schedule[0][4]*. Then, they only have to attend one lecture at the *0th* hour, so the total time spent at school = 1, which is the minimum possible. Thus, the answer is 1.

**Function Description**

Complete the function *getMinimumTime* in the editor below.

*getMinimumTime* has the following parameters:

*int schedule[n][m]*: an array of binary strings each of length m which denotes the schedule of the school

*int k*: an integer that denotes the number of lectures the student can skip

**Returns**

*int*: an integer that denotes the minimum total time the student is required to attend the school

**Constraints**

- 1 <= n,m <= 200
- schedule[i][j] = '0' or '1'
- It is guaranteed that the length of each schedule[i] (0 <= i < n) is equal to m.

Entering edit mode

Q2) **Assuming K < =200**

- The question can be solved by Dynamic Programming.
- Let
**f(d,max_skips)**represent minimum total time to attend the school till*d*and atmost*max_skips*classes can be skipped. - Suppose we skip
**X**classes on the*d_th*then we could define the recursion as follows: `f(d,max_skips)=min(f(d-1,max_skips-X)+Time(d,X)) over all 0 < =X < =max_skips`

where Time(d,X) represent minimum time to attend class on th*d_th*day if we can skip atmost**X**classes on*d_th*day.

- Now computing Time(d,X) for each recursive call will be costly because it will take in total
**O(n**for computing*k*k * m)**f** - Therefore we could precompute
**Time(d,X)**by suppose if we are at day**d**and we could skip atmost**X**lectures , since cost is just the right most attending lecture hour - left most attending lecture hour + 1 . Therefore we would just skip some prefix of classes at**day d**and suffix of classes at**day d**because that will eventually affect the answer only. - Let's suppose if at day
**d**at**h[1],h[2],...h[m]**there were classes , and we want**minimum(h[j]-h[i])**,**m-j+i-1<=X**which can be computed by taking each**i**and find optimal**j** - Hence it will take
**O(n***m*k)

```
int f(int day,int max_skips)
{
if(day completed ) // < 0 if 0-based indexing and <=0 if 1-based indexing
return 0;
if(dp[day][max_skips]!=-1)
return dp[day][max_skips];
int ans=1e9;
for(int X=0;X<=max_skips;X++)
{
ans=min(ans,f(day-1,max_skips-X)+Time[day][X]);
}
return dp[day][max_skips]=ans;
}
computeTime()
{
for( day in 1...n) //1-based indexing
{
list pos // consisting of hours on which lectures are there.
//i.e schedule[day][hour]=1;
for(X in 0...k)
{
if(X >= size(pos))
Time[day][X]=0;
else
{
Time[day][X] = pos.last() - pos[0] + 1;
for(j in [0,...,size(pos)-1])
{
int left_remove=j;
if(left_remove>X)
break;
int more=X - left_remove;
int R= p-1 - more;
Time[day][X]=min(Time[day][X],pos[R]-pos[j]+1);
}
}
}
}
}
```

Finally answer would be **f(n-1,k)** if 0-based and **f(n,k)** if 1-based.

Entering edit mode

Q1)

- First of all imagine it as a graph problem where there is an
**edge**between**i,j**where**1 < =i,j < =n**and cost of this edge is given as*min(abs(x[i]-x[j]),abs(y[i]-y[j])*and you have to find the**Minimum Spanning Tree(MST)**of the constructed graph(because you want the graph to be connected with minimum cost). - But implementation of above mentioned would take
**O(n^2)**. - So for optimization let's suppose if there were just
**x coordinates**that we could do it by sorting the indices according to**x coordinates**and add edge between the adjacent indices, because obviously that would be minimum cost achievable. - Now if there are
**x,y coordinates**then do the same for both coordinates, now the graph is constructed , find the cost of**MST**of newly constructed graph. - MST cost could be calculated by
**Kruskal Algorithm**

```
Graph G;
Maintain array index storing indexes from 1 to N//index array is 1-based.
sort index according to X coordinate
for(int i=2;i < =n;i++)
{
//add edge between adjacent indices
G.addEdge(index[i-1],index[i],weight=abs(X[index[i]]-X[index[i-1]]))
}
sort index according to Y coordinate
for(int i=2;i < =n;i++)
{
//add edge between adjacent indices
G.addEdge(index[i-1],index[i],weight=abs(Y[index[i]]-Y[index[i-1]]))
}
```

Finally answer would be cost of MST of G

Loading Similar Posts