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
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
Q2) Assuming K < =200
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.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.
Q1)
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