Secret Santa

View as PDF

Submit solution

All submissions

Best submissions

Points: 15

Time limit: 1.0s

Memory limit: 16M

Author:

Alex

Problem types

PEG Test - December 2014

PEG is hosting its first annual Secret Santa! To preserve secrecy amongst the Santas, Alex numbers the $N$ ~N~ $(1 \le N \le 30)$ ~(1 \le N \le 30)~ PEG students from $1$ ~1~ to $N$ ~N~. Their names will henceforth correspond to these numbers. In Secret Santa, everybody's name is placed into a hat. Alex carries the hat around the classroom, and each person draws a name from the hat that is guaranteed to not be their own. Each person keeps their selection a secret, and must send a gift to that person later on.

Ben's job during the name draw was to follow Alex around and write down which person drew which person, in case anybody forgets their selection and later comes to ask. However, amidst all his university application papers, Ben has lost the sheet that recorded each person's selection. PEG members are naturally forgetful. As expected, a few days before the gifting and reveal, many students reported that they've forgotten the name of the person they've drawn. When all these people went to consult Ben, he became visibly distraught. Drastic action must be taken. So, Ben went around and secretly asked everybody to give a list of names of their possible partners.

Each person gives Ben a list of names of people that might be their partner. Clearly, for someone who remembers their partner's name, this list will contain exactly one name. For someone who hasn't a clue who their partner is, this list will contain everybody's name. It is guaranteed that a person's list will contain their partner. Using these hints, Ben would like to determine one valid way to reassign names to those who have forgotten, such that everybody in PEG has a distinct secret Santa.

Input Specification

Line $1$ ~1~ will contain a single integer $N$ ~N~, specifying the number of students.
For the next $N$ ~N~ lines, each line will correspond to a student. More specifically, line $i+1$ ~i+1~ will describe the list of possible partners given by student $i$ ~i~.
For each of these lines, the first number on the line will describe how many people are on the list, and then the actual list will follow on that line. For example, a line containing 4 10 11 12 13 means that the student's potential selection could've been either one of students $10$ ~10~, $11$ ~11~, $12$ ~12~, and $13$ ~13~.

Output Specification

Output a single line containing $N$ ~N~ space-separated integers, describing the Secret Santa configuration. Student $i$ ~i~ (for $1 \le i \le N$ ~1 \le i \le N~) is the secret Santa of the $i$ ~i~-th integer on the line. It is guaranteed that a solution, although not necessarily unique, will exist. You may output any such solution.

Sample Input

Sample Output

2 3 1 5 4

Explanation

Student $1$ ~1~ knows for sure that his choice is student $2$ ~2~. Student $2$ ~2~ forgot whether he picked student $3$ ~3~ or $5$ ~5~. Student $3$ ~3~ knows for sure that he picked student $1$ ~1~. Student $4$ ~4~ completely forgot, so it could've been anybody of $1$ ~1~, $2$ ~2~, $3$ ~3~, or $5$ ~5~. Student $5$ ~5~ knows for sure that he picked student $4$ ~4~. In other words, we don't know the choices for students $2$ ~2~ or $4$ ~4~. We DO know that if $2$ ~2~ picked $3$ ~3~, then $4$ ~4~ must have picked $5$ ~5~, or if $2$ ~2~ picked $5$ ~5~, then $4$ ~4~ must have picked $3$ ~3~. So another valid answer is 2 5 1 3 4.

Comments

0

Garklein commented on March 9, 2024, 2:22 p.m.

Any PyPy3 code submitted to this question errors with "failed initializing", anyone know why?

2

weewoo14 commented on March 9, 2024, 2:44 p.m.

The memory limit for this problem is 16 MB. Whenever you run PyPy3, it will always run with a higher memory amount, around 50 MB. Therefore, PyPy3 fails to initialize, given the 16 MB memory limit. (something like this)

0

Garklein commented on March 12, 2024, 3:30 p.m.

I see, thanks!

0

htoshiro commented on March 10, 2024, 12:12 a.m.

orz weewoo