Scribd
Upload
52 views3 pages

Bus Assignment Problem Solutions

The document describes a bus assignment problem where students must be assigned to buses in a way that respects all given opinions, and asks the reader to determine the number of possible assignments. Students are numbered 1 to n and buses 1 to k. There are m opinions, which can specify that two students cannot be on the same bus or that if one student is on a bus, the other must be too or neither can be. The input provides n, k, m and the opinions, and the output must state the number of ways to assign students to buses respecting all opinions.

Uploaded by

mohammodhasan396
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
52 views3 pages

Bus Assignment Problem Solutions

The document describes a bus assignment problem where students must be assigned to buses in a way that respects all given opinions, and asks the reader to determine the number of possible assignments. Students are numbered 1 to n and buses 1 to k. There are m opinions, which can specify that two students cannot be on the same bus or that if one student is on a bus, the other must be too or neither can be. The input provides n, k, m and the opinions, and the output must state the number of ways to assign students to buses respecting all opinions.

Uploaded by

mohammodhasan396
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Bangladesh Olympiad in Informatics bus

National Round Day 2 T asks


28-29 April, 2023 English

The Wheels on the Bus


South-park Elementary is going on a picnic. There are n students and k buses to transport them to
the picnic spot. The students are numbered from 1 to n, and the buses are numbered from 1 to k .

To ensure that all students are happy, Mr. PC Principal has asked for their opinions. There are a total
of m opinions, each of which can be of two types:

1 x y: student x and student y cannot sit on the same bus.


2 x y z : if student x is in bus z , then student y must also be in bus z , or vice versa. In other
words, either both students are in bus z or neither of them is in bus z .

Your task is to determine the number of ways to assign each student to a bus such that all of the
opinions are respected. Two assignments are considered different if there is at least one student who
is assigned to different buses.

Note that a bus can be empty, meaning that no student is assigned to it. It can also have all the
students assigned to it.

Input
Read the input from the standard input in the following format:

line 1 : n k m
line 1 + i (1 ≤ i ≤ m ): this line describes opinion i and follows one of the following formats:
1 x y
2 x y z

Output
Write the output to the standard output in the following format:

line 1 : the number of ways to assign each student to a bus such that all the opinions are
satisfied

Constraints
1 ≤ n ≤ 17
2 ≤k≤5
0 ≤ m ≤ 12 ⋅ n ⋅ (n − 1) ⋅ (k + 1)
​

1 ≤ x, y ≤ n, x = y, and 1 ≤ z ≤ k

bus (1 of 3)
No two opinions are the same.

Subtasks
1. (9 points) k = 2
2. (21 points) All opinions are of type 2 .
3. (22 points) 1 ≤ n ≤ 13
4. (48 points) No further constraints.

Examples

Example 1

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

The correct output is

2‎

If, in an assignment, the student i is assigned to bus bi , we denote that assignment by the sequence
​

(b1 , b2 , … , bn ) . Then two possible assignments for each students are:


​ ​ ​

(1, 1, 2, 2)
(2, 2, 1, 1)

The following are examples of invalid assignment:

(1, 1, 1, 1) because student 2 and 3 are in the same bus.


(1, 1, 2, 1) becuase student 4 is in bus 1 but student 3 is not in bus 1 , violating the opinion 3 .

Example 2

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

The correct output is:

bus (2 of 3)
0‎

There is no suitable assignment that satisfies all the opinions.

Example 3

4 3 5
1 1 3
2 1 2 1
2 1 4 3
1 4 3
2 2 3 2‎

The correct output is:

7‎

bus (3 of 3)

You might also like