Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

# CSC108H5F Fall 2022, Assignment 4

Due: To be submitted individually by Mon Dec 5, 22:00, on MarkUs

On this assignment, efficiency concerns are more important than on previous assignments. For this reason, we have provided time limits for each question. To pass a test case, your program must produce the correct output (as always) but also finish within the time limit. Some solutions, while correct, may not be fast enough. Solving the problem with such a solution, though, is far from a waste of time: it has the possibility of receiving up to 70 percent of the points, it is a good step toward understanding how the problem can be solved, and it may help you progress to a faster solution!

## Q1: Assignment Difficulty

Dan has a list of problems suitable for Assignment 4. The difficulties of these problems are stored in a list of integers a. The i-th problem’s difficulty is represented by a[i] (the higher the integer, the more difficult the problem).

Dan is too busy eating saltines to worry about Assignment 4 decisions, so he asks Michael the TA to select at least two problems from the list for the assignment. Since there are many possible subsets of the problems to consider and Michael has a life, he decides to consider only sublists (definition follows) of the list of problems.

To make grading the assignment easier, Michael wants to pick problems that don’t vary too much in difficulty. What is the smallest difference between the difficulties of the most difficult selected problem and the least difficult selected problem he can achieve by selecting a sublist of length at least 2 of the original list of problems?

Definition: A sublist of a list a is any list you can obtain by removing some (possibly 0) elements from the start of a and then removing some (possibly 0) elements from the end of it. (It’s like the definition of segment from lecture.) .

### Filename

Your filename for this question must be q1.py.

### Input

The input consists of a single line containing the integers in the list a, separated by single spaces.

### Output

Print a single integer indicating the smallest difference in difficulties Michael can achieve.

### Constraints

· 2 <= len(a) <= 500000

· 1 <= a[i] <= 10**9

### Time Limit

Your program must finish running on any valid input within 3 seconds.

10 6 9 1

3

### Sample 1 Explanation

· If Michael selects all of the problems, the maximum difficulty would be 10 and the minimum difficulty would be 1. In this case, the difference he wants to minimize would be 9.

· If he selects the sublist 6 9, the maximum and minimum difficulties would be 9 and 6 respectively and the difference would be 3.

· Note that he can’t select 10 9, as that’s not a sublist of a.

7 7 7

0

## Q2: Ginormous Campus

The UTM campus is pretty big. There are n buildings scattered around it, numbered from 0 to n-1. These buildings are so far away from each other that the only way to get from one to another is to take a campus bus.

There are m campus bus routes. The i-th one (0 <= i < m) takes you from building u_i to building v_i (but not the other way around). These buses run very frequently.

Professor Zingaro is deciding where to hold his CSC108 lectures. He believes a building x is accessible from a building y if you can get from y to x taking at most two buses. For his students’ convenience, he wants to hold his lectures in the most accessible building. Help him out by telling him how many buildings the most accessible building is accessible from. In addition, list all buildings that are the most accessible.

### Filename

Your filename for this question must be q2.py.

### Input

The first line of the input contains two space-separated integers n and m, denoting the number of buildings and bus routes, respectively.

m lines follow. The i-th one contains two space-separated integers u_i and v_i, as described above.

### Output

The output should consist of two lines. The first line should contain a single integer x denoting the number of buildings that the most accessible building is accessible from

The second line should contain a list of up to n integers, denoting the list of buildings that are accessible from exactly x buildings. List the buildings in increasing order.

### Constraints

· 1 <= n <= 10000

· 0 <= u_i, v_i < n

· u_i != v_i (i.e. no route connects a building to itself)

· For any building, there are at most 70 bus routes that end at it.

· There are no additional constraints on m or the routes.

### Time Limit

Your program must finish running on any valid input within 9 seconds.

6 5

0 1

1 2

2 3

3 4

4 5

3

2 3 4 5

### Sample 1 Explanation

· The first line indicates that there are 6 buildings and 5 bus routes.

· The bus routes are described in the next 5 lines. For instance, the second route takes you from building 1 to building 2.

· Building 0 is only accessible from itself. Building 1 is accessible from building 0 and itself. The remaining buildings are all accessible from 3 buildings, including themselves.

6 8

0 1

2 1

1 3

4 3

3 5

0 1

3 0

1 0

5

0 3

## Q3: Superheroes

Supervillains are tired of Toronto condo rental prices, so they are leaving Toronto for Mississauga.

Luckily, we have n valiant superheroes that can deal with them. The i-th superhero (0 <= i < n) has a name name[i], an intelligence score in[i], and a strength score s[i].

There are m supervillains flocking to Mississauga. After thorough investigation, Detective Zingaro has determined that the supervillains can be classified into three categories for how to deal with them:

1.

A type 1 supervillain has an intelligence score int. Detective Zingaro needs to assign a superhero whose intelligence is at least as much as int to this supervillain. Moreover, to be efficient with his resources, he must assign the superhero with the minimum intelligence who satisfies this requirement.

2.

3.

A type 2 supervillain has a strength score st. The detective needs to assign a superhero whose strength is at least as much as st to this supervillain. Similar to above, he must assign the superhero with the minimum strength that meets this requirement.

4.

5.

Finally, a type 3 supervillain has a mixed score g, meaning that the superhero x assigned to them needs to have in[x] + s[x] >= g. Again, the detective is interested in the superhero with the smallest in[x] + s[x] that satisfies this requirement.

6.

Detective Zingaro has asked for your help. For each of the supervillains, tell him the name of the superhero that should deal with that supervillain.

Note: A superhero can be assigned to multiple supervillains (or none at all).

Note: whenever there are multiple superheroes that satisfy the given requirements for a supervillain, report the one whose name is lexicographically smallest (i.e. the one that’s the smallest according to Python’s ordering of strings). It’s guaranteed that superheroes have distinct names.

Hint: Tuples of multiple elements may be helpful here. In python, you can compare two tuples (a, b) and (c, d). If a and c are different, the result is the same as comparing a and c. If a and c are equal, the result is the same as comparing b and d. You can even sort these tuples!

### Filename

Your filename for this question must be q3.py.

### Input

The first line of the input contains a single integer n denoting the number of superheroes.

The next three lines describe the superheroes. The first line contains n space-separated strings, specifying the names of the superheroes. The second line contains n space-separated integers, specifying the list in. Finally, the third line specifies the list s.

The next line contains a single integer m denoting the number of supervillains. m lines will follow describing them, one per line. Each of these lines starts with an integer t denoting the type of the villain (1, 2, or 3), followed by an integer specifying the corresponding threshold.

### Output

Your output should consist of m strings separated by spaces. The i-th one should be the name of the superhero assigned to the i-th supervillain. If no superhero meets the requirements for a supervillain, output none for that supervillain instead.

### Constraints

· 1 <= n, m <= 150000

· Intelligence scores, strength scores, and thresholds are all in range [1, 500000].

· Superhero names are between 1 and 6 characters long and contain only lowercase English letters.

· No two superheroes have the same name.

· No superhero’s name is “none”

### Time Limit

Your program must finish running on any valid input within 5 seconds.

### Sample Input 1

5

batman catman pacman peach mario

1 3 7 10 8

4 7 7 3 1

4

1 4

2 7

3 11

1 11

### Sample Output 1

pacman catman peach none

### Sample 1 Explanation

· The first line indicates that there are 5 superheroes.

· Lines 2-4 describe the superheroes. For instance, the second one is named “catman” and has an intelligence score of 3 and a strength score of 7.

· Line 5 indicates that there are 4 supervillains to deal with. These supervillains are described in the following 4 lines.

· For the second supervillain, both catman and pacman satisfy the requirements of Detective Zingaro. However, catman is lexicographically smaller than pacman, so you should report catman as the answer.

5

a b c d e

1 2 3 5 8

8 5 3 2 1

6

1 5

3 7

2 1

2 8

3 6

1 4

d b e a c d

## Important Reminders

· As we did in lecture, you should use the time limits and constraints to figure out the kind of efficiency class that will pass all test cases in time.