1998 ACM South Central USA Collegiate Programming Contest
Rice University

You Who?

Solution  Judge's input     Judge's output    Clarifications  Comments

Scenario

On the first day of first grade at Friendly Elementrary School, it is customary for each student to spend one minute talking to every classmate that he or she does not already know.  When student Bob sees an unfamilar face, he says ``You who?''  A typical response is ``Me Charlie, you who?''  Then Bob says, ``Me Bob!'' and they talk for a minute.  It's very cute.  Then, after a minute, they part and each looks for another stranger to greet. This takes time.  In class of twenty-nine or thirty mutual strangers, it takes 29 minutes; time that, according to teachers, could be better spent learning the alphabet.  Of course, it is rare to have a first grade class where nobody knows anyone else; there are neighbors and playmates who already know each other, so they don't have to go through the get-to-know-you minutes with each other.

The two first grade teachers have requested that, to save time, students be allocated to their two classes so that the difference in the sizes of the classes is at most one, and the time it takes to complete these introductions is as small as possible.  There are no more than 60 students in the incoming first grade class.

How can the assignment of students to classes be made?  Your job is to write the software that answers the question.
 

Input

The school records include information about these student friendships, represented as lists of numbers.  If there are 29 students, then they are represented by the numbers 1 to 29.  The record for a single student includes, first, his/her student identification number (1 to 29, in this example), then the number of his/her acquaintances, then a list of them in no particular order. So, for example, this record

17 4 5 2 14 22

indicates that student 17 knows 4 students: 5, 2, and so on.  The records for all the students in the incoming class are represented as the list of numbers that results from concatenating all the student records together.  Spaces and line breaks are irrelevent in this format.  Thus, this

1 1 2 2 1 1

is a whole database, indicating that there are only two students in the incoming class, and they know each other; and this

1 2 3 4
2 2 3 4
3 2 1 2
4 2 1 2

indicates that 1 doesn't know 2, and 3 doesn't know 4, but all other pairs know each other.

The database has been checked for consistency, so that if A knows B, then B knows A.

Output

Your output should begin with a number that tells how long it will take to complete the introductions in the best possible legal class assignment.  Subsequent output consists of a list of class enrollments that achieves that bound.  An enrollment is represented by the number of students in the class, and then a list of the students in the class, in increasing order.  The complete solution, then, is the number that reports the introduction time, then the list of enrollments.  There are no particular rules on output format; a list of numbers in any readable format is fine.

So, for the simple two student problem above, the only legal answer is

1 2 1 2

Sample Input

1 2 3 4
2 2 3 4
3 2 1 2
4 2 1 2

Sample Output

1 4 1 2 3 4



 

Solution

#include <iostream.h>
#include <fstream.h>
#include <stdlib.h>

typedef unsigned bitmask_t;
// represents a subset of the integers ({0, .., 31} (on most machines)
// E.g., bitmask = 00110 (in binary) represents set {1,2}
 

// tricky macros for counting the 1 bits in a word
#define l 1U

#define M (-l)
#define A(K) (l<<(K))
#define B(K) (l+A(K))
#define Z(x,K) ((x) = ((x) & M/B(K)) + ((x) & M/B(K)*A(K)) / A(K))

#define bitcount(x) \
do { \
 Z(x,1); \
 Z(x,2); \
 Z(x,4); \
 Z(x,8); \
 Z(x,16); \
} while(0)

// necessary only if you happen to shift over by the number of bits in a
// word, expecting to clear the word; this way, you'll actually do it
#define Lshift1(i) ((bitmask_t)1 << (i)/2 << ((i)-(i)/2))
 

// It is not strictly necessary to use this obscure bit twiddling either,
// but it does speed up things, and its fun
bitmask_t firstComb(unsigned k)
{ return Lshift1(k) - 1; }

#define leastItem(comb) ((comb) & -(comb))

bitmask_t lastComb(unsigned n, unsigned k)
{ return Lshift1(n) - Lshift1(n-k); }

// find the next number with the same number of 1 bits as this number
bitmask_t
nextComb(bitmask_t comb)
{
  bitmask_t hibit;
  bitmask_t lobit = leastItem(comb);
  comb += lobit;
  hibit = leastItem(comb);
  hibit -= lobit;
  while (!(hibit&1)) hibit >>= 1;
  comb |= hibit >> 1;
  return comb;
}

#define MAX_STUDENTS (8*sizeof(bitmask_t))

int main()
{

  bitmask_t unknowns_db[MAX_STUDENTS];
  unsigned i;
  // initially, everybody  knows themselves
  for (i = 0; i < MAX_STUDENTS; ++i)
    {
      unknowns_db[i] = -l;
      unknowns_db[i] &= ~(l << i);
    }

  unsigned nStudents = 0;
  // read student acquaintance graph and store as incidence bitmap
  {
  ifstream in("youwho.inp");
  unsigned studentId;
  while (in >> studentId)
    {
      unsigned nFriends;
      in >> nFriends;
 
      for (unsigned j = 0; j < nFriends; ++j)
        {
          unsigned aFriend;
          in >> aFriend;
          unknowns_db[studentId-1] &= ~(l << (aFriend-1));
        }
      ++nStudents;
    }
  }

  for (i = 0; i < nStudents; ++i)
    unknowns_db[i] &= (l<<nStudents)-1;

  unsigned* studentUnknowns = new unsigned[nStudents];
 
  // consider every possible arrangement of classes that splits evenly
  unsigned classSize = (nStudents+1)/2;
  unsigned mindontknow = classSize+1;
  unsigned minassignment = 0;
 
  bitmask_t lastAssignment = lastComb(nStudents-1, classSize);
  for (bitmask_t assignment = firstComb(classSize);
       assignment <= lastAssignment; assignment = nextComb(assignment))
    {
      unsigned maxassignment = 0;
      unsigned maxUnks[2];
      maxUnks[0] = maxUnks[1] = 0;
 
      for (unsigned studentId = 0; studentId < nStudents; ++studentId)
        {
          bitmask_t hisclass;
          unsigned classId;
          if ((assignment >> studentId) & 1)
            {
              hisclass = assignment;
              classId = 1;
            }
          else
            {
              hisclass = ~assignment;
              classId = 0;
            }

          // which students doesn't this one know?
          bitmask_t unknowns = unknowns_db[studentId] & hisclass;
          // replace unknowns by # of bits in unknowns
          bitcount(unknowns);

          studentUnknowns[studentId] = unknowns;
          if (maxUnks[classId] < unknowns)
            maxUnks[classId] = unknowns;
        }

      maxassignment = maxUnks[0]>maxUnks[1]? maxUnks[0]: maxUnks[1];
      if (mindontknow > maxassignment)
        {
          mindontknow = maxassignment;
          minassignment = assignment;
          //      cout << hex << minassignment << dec << " " << mindontknow << endl;
        }
    }
 

  cout << mindontknow << "\n";
  cout << classSize;
  for (i = 0; i < nStudents; ++i)
    if ((minassignment >> i) & 1)
      cout << " " << (i+1);
  cout << "\n";

  cout << (nStudents-classSize);
  for (i = 0; i < nStudents; ++i)
    if (((minassignment >> i) & 1) == 0)
      cout << " " << (i+1);
  cout << "\n";
  return 0;
}
 

Judge's Input

1 0
2 0
3 0
4 0
5 0

Judge's Output

2
2 1 2
3 3 4 5

Clarifications

To make this problem more tractable, the following changes are being made.  There will be exactly two classes.  There will be no more that 30 students.  The students will be divided as evenly as possible between the classes.  The loneliness of a student is the number of students in his class whom he does not know.  You are to arrange the classes to minimize the loneliness of the loneliest student.

Comments

This was the last problem that was composed, the last one to be solved before the contest, and all that showed.  I knew two days before the contest that I'd be making the clarification above, but somehow, the clarification didn't get made as the beginning of the contest as I'd hoped, and then only partially got made later, in a way that just confused things more.  Then, to top it all off, we ended up with an embarrassingly easy test case, despite my having written a program to generate random test cases.  For what it's worth, my implementation above, which just does an exhaustive search of all possible assignments in a slightly clever way, could solve the problem for 24 students in about 3 seconds; many more students than that and I wouldn't have made it under the 30 second time limit either.

Finally, this problem mostly, but many others as well, illustrates my ignorance of the problems that Pascal programmers have with input formatting.  Clarification requests kept coming in about formatting issues (is that all pairs on one line, or each pair on its own line?), and at first I didn't have a clue about why anyone cared.  Eventually, it was explained to me that Pascal programmers are at a distinct disadvantage on this front because they have to parse their own inputs in a way that C, C++ and Java programmers do not.  I guess I'll know better next time.

This problem is dedicated to Yu "Charlie" Hu.