Join Us
Loading Similar Posts
Entering edit mode
Question 1
Network Construction
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
Question 2
Lectures at School
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
Solution
- 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_skipswhere 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.
Time(d,X) computation
- Now computing Time(d,X) for each recursive call will be costly because it will take in total O(n k k * m) for computing 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)
Pseudo Code
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)
Solution
- 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
Pseudo Code
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
Similar Posts
