2016 Canadian Computing Olympiad
Day 1, Problem 1 - Field Trip
As a special treat for your kindergarten class, you're taking them on a field trip to a magical place of wonder.
Your class has N students, numbered from 1 to N for convenience. There are M direct, two-way friendships that exist between the students. Each student is friends with at most two other students.
Aside from the M direct friendships, students may also be acquainted with one another. Two students i and j are acquaintances if they're friends, or if there exists a third student k who is an acquaintance of both students i and j. For example, if (1, 2), (2, 3), (3, 4) and (4, 5) are pairs of students with a direct friendship, then person 1 and person 5 are acquaintances.
You're getting ready to order buses for the trip, but there are two issues. Firstly, the transportation company insists that every bus you order must be filled exactly to its capacity of K students. They won't allow you to order a bus if you intend to put fewer than K students on it! Secondly, the students are picky about their travelling conditions. Each student i will refuse to get on a bus unless both of the following conditions are met:
- All of the other students getting on that bus are acquaintances of student i;
- All of student i's acquaintances are getting on that bus.
Unfortunately, it looks like you might not be able to bring your whole class on this trip after all. However, you'll do whatever it takes to get as many students as possible on buses. As it turns out, "whatever it takes" may involve putting an end to a friendship or two, for the greater good. You may choose to sever 0 or more of the M friendships amongst the students, which will of course also have an effect on which students are acquainted with one another.
Determine the maximum number of students which can be brought on the trip, such that they're loaded onto buses with exactly K students each, and every student is satisfied with their bus allocation. Furthermore, since you're feeling generous, determine the minimum number of friendships which you can sever in order to be able to bring that many students along.
The first line contains three space-separated integers N, M and K (1 ≤ N ≤ 106; 0 ≤ M ≤ 106; 1 ≤ K ≤ N).
The next M lines contain information about the friendships. That is, each of these M lines contain two space-separated integers Ai and Bi (1 ≤ i ≤ M) describing that students Ai and Bi are friends (1 ≤ Ai, Bi ≤ N, Ai ≠ Bi). Note that no friendship is specified twice (that is, no two unordered friendship pairs are equal to one another).
For 3 of the 25 marks available, N ≤ 1000.
The output consists of two space-separated integers printed on one line. The first integer is the the maximum number of students which can be brought on the trip. The second integer is the minimum number of friendships which must be severed in order to bring that many students.
8 5 2 1 4 8 2 4 5 6 2 3 5
If the friendships between student pairs (8,2) and (4,5) are severed, then 3 buses can be filled as follows:
- Bus 1: Students 1 and 4
- Bus 2: Students 2 and 6
- Bus 3: Students 3 and 5
Point Value: 10 (partial)
Time Limit: 3.00s
Memory Limit: 64M
Added: May 14, 2016
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3