649 - You Who?

[kelvin yang]

649 You who?

I was trying to understand this problem but seemed to have some difficulties.

My understanding of the problem is as below:
Given a graph G, divide its vertices into two groups such that
1) the number of vertices in two group differ by at most 1
2) the maximum number of not-acquainted classmates for a person in a single group is minimized.

Am I understanind it wrong?
since in the output for

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

is

1 4 1 2 3 4

then I got two question:
1) I thought we are supposed to divide the class in two, but in the output there is only one assignment for a single class.
(or does it means that we only ouput the enrollment for one of the two)
2) also in the problem it states: the difference in the sizes of the classes is at most one. But in the output configuration I cannot see how the above rule is satisfied..

I'm sorry if I misunderstand the question completely,
but please some help in clarification is appreciated..

[mathgirl]

Can anyone who solved this problem help me out ?

1) What should the output be when N = 1 ?
2) What does maximal number per person mean? Is it
(I1+I2) /N
or
max (I1/N1 , I2/N2) N1 + N2 = N, I1 = introductions in Set 1 and I2 = Introductions in Set 2

Any help is appreciated.

[brianfry713]

For Input:

Code: Select all

1
1 0

My AC output is:

Code: Select all

0
0
1 1

This output should also work:

Code: Select all

0
1 1
0

The best assignment has the minimum maximum number of introductions. The teachers want to wait as little as possible for all of the introductions to be completed. There is no division or average. Minimize the maximum of any student.

[mathgirl]

Can you give your output for the following input

Code: Select all

6
1 3 4 5 6
2 3 4 5 6
3 3 4 5 6
4 3 1 2 3
5 3 1 2 3
6 3 1 2 3

1
1 0

2
1 1 2
2 1 1

7
1 2 3 4
2 2 5 6
3 2 1 7
4 2 1 5
5 2 2 4
6 1 2
7 1 3

My code gives the below output. But I am getting WA.

Code: Select all

1
3 3 5 6
3 1 2 4

0
0
1 1

0
1 2
1 1

2
4 2 3 6 7
3 1 4 5

[brianfry713]

Your output looks correct.