![]() ![]() ![]() |
![]() ![]() |
You Who?
Solution Judge's input Judge's output Clarifications Comments
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.
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.
So, for the simple two student problem above, the only legal answer is
1 2 1 2
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;
}
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.