-1

For the below challenge from a programming site, I am bit confused.

Problem Statement:

A Professor of Physics gave projects to the students of his class. The students have to form a team of two for doing the project. The professor left the students to decide the teams. The number of students in a class will be even.

Each student has a knowledge level. It tells how much knowledge each student has. The knowledge level of a team is the sum of the knowledge levels of both the students.

The students decide to form groups such that the difference between the team with highest knowledge and the one with lowest knowledge is minimum.

Input

First line of the input will contain number of test cases t; In the next t lines the first number is n the number of students in the class followed by n integers denoting the knowledge levels of the n students

Output

Your output should be a single line containing the lowest possible difference between the team with highest knowledge and the one with lowest knowledge.

Sample Input

2

4 2 6 4 3

6 1 1 1 1 1 1

Sample Output

1

0

[My Attmept]

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ProjectTeam
{
    class Program
    {
        static void Main(string[] args)
        {
            int testCasesCount = Convert.ToInt32(Console.ReadLine());
            // Solve each test case
            for (int i = 0; i < testCasesCount; i++)
            {
                String line = Console.ReadLine();
                String[] components = line.Split(' ');
                int numberOfStudents = Convert.ToInt32(components[0]);
                int[] studentsKnowledge = new int[numberOfStudents];

                // Read input

                for (int j = 0; j < numberOfStudents; j++)
                {
                    studentsKnowledge[j] = Convert.ToInt32(components[j + 1]);
                }

                // Done

                // Solve
                List<int> listOfPossibleTeams = new List<int>();
                for (int k = 0; k < numberOfStudents; k+=2)
                {
                    int knowledge = studentsKnowledge[k] + studentsKnowledge[k + 1];

                    // Create others
                    if (k >= 2)
                    {
                        int toPair = studentsKnowledge[k];
                        for (int l = k-1; l >= 0; l--)
                        {
                            listOfPossibleTeams.Add(toPair + studentsKnowledge[l]);
                        }
                        toPair = studentsKnowledge[k + 1];
                        for (int l = k-1; l >= 0; l--)
                        {
                            listOfPossibleTeams.Add(toPair + studentsKnowledge[l]);
                        }
                    }
                    //
                    listOfPossibleTeams.Add(knowledge);
                }

                listOfPossibleTeams.Sort();

                // select minimum knowledge diff

                int minumimKnowledge = int.MaxValue;
                for (int m = 0; m <= listOfPossibleTeams.Count() - numberOfStudents / 2; m++)
                {
                    int diff = Math.Abs(listOfPossibleTeams[m] - listOfPossibleTeams[m +(numberOfStudents / 2) - 1]);
                    if (diff < minumimKnowledge)
                    {
                        minumimKnowledge = diff;
                    }
                }

                Console.WriteLine(minumimKnowledge);
            }
        }
    }
}

But the above solution fails for test case:

1

8 4 2 4 2 1 3 3 7

My Code outputs 0, while the actual answer is 2.

My Approach is to create all the possible valid combinations of teams, and get their knowledge, sort all the knowledge, and select n/2(n is number of students) contiguous elements having minimum difference between the boundaries of selection. But this doesn't work.

Eventually I found the problem solved by someone in the internet, and I tried the solution and it worked. But I do not understand how does it work? The code below:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ProjectTeam
{
    class Program
    {
        static void Main(string[] args)
        {
            int testCasesCount = Convert.ToInt32(Console.ReadLine());
            // Solve each test case
            for (int i = 0; i < testCasesCount; i++)
            {
                String line = Console.ReadLine();
                String[] components = line.Split(' ');
                int numberOfStudents = Convert.ToInt32(components[0]);
                List<int> studentsKnowledge = new List<int>();

                // Read input

                for (int j = 0; j < numberOfStudents; j++)
                {
                    studentsKnowledge.Add(Convert.ToInt32(components[j + 1]));
                }
                studentsKnowledge.Sort();
                // Done

                // Solve
                int diff = (studentsKnowledge[0] + studentsKnowledge[numberOfStudents - 1]);
                int max = diff, min = diff;
                for (int k = 1; k < studentsKnowledge.Count / 2; k++)
                {
                    diff = studentsKnowledge[k] + studentsKnowledge[numberOfStudents - 1 - k];
                    if (diff > max)
                        max = diff;
                    if (diff < min)
                        min = diff;
                }
                Console.WriteLine(max - min);
            }
        }
    }
}

I do not understand how does the above code works. The above code doesn't even creates all the possible combinations. Is it using some mathematical concept which I am not able to think of, or is my interpretation of the problem wrong? Please help.

  • 2
    Your question is far too long. Can't you reduce the essential part of code to a single function, and throw all that console I/O stuff out? That would actually help yourself to focus more on the important parts. – Doc Brown Mar 13 '15 at 12:46
3

In this answer I will focus on the thinking part and less on the coding part. In other words, if the thinking is not correct, the code will probably not give the result you expected, even if the code implements your thinking faithfully.

I will just point out the flaw in the code part, without going into detail: listOfPossibleTeams contained all possible sums of pairs, without considering conflicts - if you have already paired up students A and B, it is not be allowed to pair up B and C again because that would have assigned B to two teams simultaneously. However, the array listOfPossibleTeams will contain the sums of A+B and B+C and A+C, and your subsequent use of this array did not try to detect this conflict. This is why the answer it gives was wrong.

The mathematical knowledge needed to understand this conflict is taught in Combinations

Understanding why the correct solution works is a bit more involved. The mathematical knowledge is taught in Order statistic, but typically students who are good at computer science are able to come up with an intuition about order statistic regardless of whether they learn it from school formally. (Just personal opinion; no references)

One way of intuitively thinking about the problem is this, via divide-and-conquer:

  1. Suppose the students are divided into two groups - the upper half and the lower half.
  2. Let's say pick two students from the upper half (named A and B), and two students from the lower half (named C and D).
    • Would it be better if we pair up the two from the upper half (A with B), and then pair up the two from the lower half (C with D)?
    • Or, would it be better if we pair up one from from each half, giving (A with C), and (B with D)?
  3. You will notice that it is always better to pair up one from the lower half with one from the upper half (the latter case).
  4. Now, further subdividing into more tiers, and repeat the test. Eventually you will intuitively see that pairing the highest with the lowest might be a good strategy worth trying.

Trying to prove it with theorems will involve a lot more effort. Most of the time, a beginning computer science student will just give it a try, and see if the code gives the same answers as the worked examples. In other words, not everyone go through the theoretical process when looking for a solution. Some goes with intuition and were able to cope with the assignments, at least in the introductory level.

  • Thanks for the great answer. I did realize the missing check of duplicate members occurring in multiple team while travelling back from my office, what I see now is that you have exactly pointed out the mistake. The interesting explanation is the second one, which you explain very nicely. Thanks a lot. I accept this as answer. – user47487 Mar 13 '15 at 13:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.