CareerCup

If you are familar with KM algoirthm (Solving Maximum Weighted Bipartite Matching), this question seems to be every easy.

generate three virtual schools with the same coordinates for each school, then apply the KM algoirthm for the given 9 school and 9 students. The weight is the distance from the student to the school.

here I am giving recursive approach (only basic idea)... there must be some DP solution for this question also...

int Min_dist(int *sc_dist, int p, int n1, int n2, int n3 , int sum_total)
{
        if(n1<3||n2<3||n3<3)
             {
             sum_total+=min(n1<0?min_sum(sc_dist, p-1,++n1,n2,n3, sum_total+sc[0][p]):INT_MAX,  min_sum(sc_dist, p-1,n1-1,++n2,n3, sum_total+sc[1][p]), min_sum(sc_dist, p-1,n1,n2,++n3 , sum_total+sc[2][p]));
             }
             return sum_total;

}

What about iterating through all the possible distributions of 9 students in 3 groups ?

Apply kruskal with deleting high weighted edges and considerering each student should have atleast one edge and each school three.

I seriously doubt on Krushkal's approach:
Lets reduce the problem to 2 school each with one child for example ..
School coordinate S1: (0,0), S2: (3,0)
Student cord St1: (1,0) and St2: (-3,0)

Now u will get the result as (S1, St1) and (S2, St2) total distance = 7
On contrary (S1, St2) and (S2, St1) makes total distance = 5

One more thing :I forgot to mention in the question that the required time complexity should be lesser than O(n^3):

DP solution:

Sum(i) - Minimum distance of all students upto i, satisfying the condition atmax 3 students in school.

Sum(i) = min { for all k = 0 to i-1, {sum(k) + for all school s = 1 to 3, d[k][s] if count[s] < 3}}

Order of the solution is O(n^2*S) - ( n- Number of students, S- number of school )

May not be an optimal solution,
9 students and 3 schools

Calculate distance between each student and each school

27 possiblities,
Sort them based on the distance for each school and pick the first 3 students for each school.

Create three tasks for each school and this becomes linear assignment.

Minimum spanning tree optimized with Kruskal or Prim.

This comment has been deleted.

Could you please explain what will happen in case when A(1,0) , B(-1,0) ,C(0,1) and one stud cord is (0,0) . In this case , all the distance is same and suppose it is minimum and it has to be included in all the three schools to get the minimum for each school. What is suggested in this case?

Algo shld be lik below...
1.Create 3 virtual school
2.cretae 9 virtual students
3. use 3 array for fiding the distance of each student from 3 school use student id as index
4.when we got 3 array create 3 Binary tree.
5. find min in those 3 trees.& assign student to the school having minimum distance.
6.delete the node in other two trees.
7.Keep doing it untill all student are assigned...

We can have checks for max student as 3 in school in step 5 & can get 2nd min distance...

Plz comment...

euclidean minimum spanning tree