CCC '11 J5 - Unfriend - Olympiads Online Judge

CCC '11 J5 - Unfriend

View as PDF

Submit solution

All submissions

Best submissions

Points: 7

Time limit: 1.0s

Memory limit: 256M

Problem type

Canadian Computing Competition: 2011 Stage 1, Junior #5

Mark invited some people to join his social network. Some of them invited new people, who invited new people, and so on. Now there are $N$ ~N~ people in the network, numbered from $1$ ~1~ to $N$ ~N~. Mark has decided to remove some people and keep others. There is one restriction: when removing a person, he will also remove the people s/he invited, and the people they invited, and so on. Mark will never remove himself, and we do not allow people to be invited by more than one person. Mark can also decide to not remove anyone.

How many different sets of people can be removed?

Input Specification

The first line contains a single integer $N$ ~N~ $(N \le 6)$ ~(N \le 6)~, the number of people in the network. Next are $N-1$ ~N-1~ lines telling us who invited each person. To be precise, line $i$ ~i~ in this set $(1 \le i \le N-1)$ ~(1 \le i \le N-1)~ contains a single integer $j$ ~j~ (with $j > i$ ~j > i~), which indicates that person $j$ ~j~ is the person who invited person $i$ ~i~. Person $N$ ~N~ is Mark.

Output Specification

Output a single integer, the number of possible sets of people that can be removed.

Sample Input 1

3
3
3

Output for Sample Input 1

Explanation for Sample 1

The first number of the input indicates there are three people in the network. The next line tells us that Person 1 was invited by Mark, while the last line tells us that Person 2 was also invited by Mark. The sets of people that can be removed are $\{\}, \{1\}, \{2\}, \{1, 2\}$ ~\{\}, \{1\}, \{2\}, \{1, 2\}~.

Sample Input 2

Output for Sample Input 2

Explanation for Sample 2

There are 4 people in the network. Here is a table of who invited who:

Person inviting	Invited
1	none
2	none
3	1
4	2,3

The possible sets are $\{\}$ ~\{\}~, $\{1\}$ ~\{1\}~, $\{2\}$ ~\{2\}~, $\{1,2\}$ ~\{1,2\}~, $\{1,3\}$ ~\{1,3\}~, and $\{1,2,3\}$ ~\{1,2,3\}~. Notice that the sets $\{3\}$ ~\{3\}~ and $\{2,3\}$ ~\{2,3\}~ are not possible, since when you remove $3$ ~3~, you must also remove $1$ ~1~.

Comments

15

Evanhyd commented on Nov. 20, 2020, 10:25 p.m. ← edit 3 →

Can person 2 invited by person 3, and person 3 invited by person 2?

Edit: No, it can't. Because person 3 can only be invited by a person who has a higher number than 3.

$j$ ~j~ (with $j > i$ ~j > i~), which indicates that person $j$ ~j~ is the person who invited person $i$ ~i~

8

kobortor commented on Feb. 17, 2015, 2:02 a.m. ← edited →

Mark is always person $N$ ~N~ right?

58

Xyene commented on Feb. 17, 2015, 2:45 a.m.

From the statement, yes: "Person $N$ ~N~ is Mark."