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

CSC108H5S Winter 2022, Assignment 4

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 is a good step toward understanding how the problem can be solved, and 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 ith 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. Moreover, he doesn’t want the problems in the assignment to vary too much in difficulty (he finds it harder to grade the problems when that happens).

 

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

 

Output a single integer: the smallest difference in difficulties Michael can achieve.

 

Constraints

 

2 ≤ len(a) ≤ 5 × 105

1 ≤ a[i] ≤ 109

Time Limit

 

Your program has to finish running within 2 seconds on any valid input.

Sample Input 1

 

10 6 9 1

Sample Output 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.

Sample Input 2

 

7 7 7

Sample Output 2

 

0

Q2: Self-Driving Cars

 

The year is 2400. The ride-hailing giant Suber have cracked self-driving cars and have a fleet of n of them at their disposal. All of the cars are currently on Olde st (the only street in the country, which happens to be unrealistically long and perfectly straight). The ith car is currently at location d[i] kilometres from the start of the street.

 

Moreover, Suber have m garages along Olde street. The ith of them is at location e[i] kilometres from the start of the street. Each garage has infinite capacity and can hold infinitely many self driving cars; any car can be kept in any garage.

 

There’s a snowfall warning in effect and Suber have to drive all of the cars to the garages as soon as possible. In order to save electricity, they want to minimize the total distance travelled by the cars. What is the minimum total distance the cars need to travel?

 

Filename

 

Your filename for this question must be q2.py.

 

Input

 

The input consists of two lines:

 

The first line contains n integers separated by single spaces. These numbers specify the list d.

The second line contains m integers separated by single spaces. These numbers specify the list e.

Output

 

Output a single integer: the minimum total distance the cars need to travel.

 

Constraints

 

1 ≤ n, m ≤ 105

0 ≤ d[i], e[i] ≤ 109

Time Limit

 

Your program has to finish running within 2 seconds on any valid input.

Sample Input 1

 

1 0 1

2 5

Sample Output 1

 

4

Sample 1 Explanation

 

There are 3 cars at locations 1, 0, and 1; and two garages at locations 2 and 5.

The unique optimal solution is to drive all of the cars to the first garage. This way, the two cars at location 1 need to drive 1km each and the other car needs to drive 2km, for a total of 4km.

Sample Input 2

 

5 1 10

13 1 7

Sample Output 2

 

5

Q3: Interplanetary Spaceflight

 

Milan Tusk is the richest person in the universe. After devoting decades of his life to further our space exploration technologies, he’s finally ready to retire. Being a space enthusiast, the first thing he wants to do is visit n planets p1, p2, …, pn, in this order. He’s currently on planet p0.

 

Milan knows that the distance between planets pi and pi + 1 (for 0 ≤ i < n) is d[i] light years. His spaceship uses 1 tonne of fossil fuels per light year. He starts with a full tank and can fill up his tank at any of the n planets (but he must not run out in between two planets). There’s a huge cost to set up the spaceship for refuelling. Due to financial constraints (he’s not THAT rich), he can fill up his tank at most k times.

 

In order to save money and make his spaceship lighter, Milan is looking for the smallest possible fuel tank that enables him to complete his space travel and reach planet pn. What is the smallest tank capacity that enables him to do so?

 

Filename

 

Your filename for this question must be q3.py.

 

Input

 

The input consists of two lines:

 

The first line contains n integers separated by single spaces. These numbers specify the list d.

The second line contains a single integer, k.

Output

 

Output a single integer: the minimum possible fuel tank capacity (in tonnes) for Milan’s spaceship.

 

Constraints

 

1 ≤ n ≤ 100

0 ≤ k ≤ 100

1 ≤ d[i] ≤ 100

Time Limit

 

Your program has to finish running within 1 second on any valid input.

Sample Input 1

 

2 1 1

3

Sample Output 1

 

2

Sample 1 Explanation

 

The capacity should be at least 2; Otherwise, Milan can’t travel from p0 to p1.

If the capacity is 2, Milan can simply fill up his tank once on p1. Note that right before he fills up there, his tank is empty, but that’s fine because he’s already on p1.

Sample Input 2

 

1 1 1 1 1 1 1

2

Sample Output 2

 

3

Sample Input 3

 

5 5 5 5

4

Sample Output 3

 

5

Q4: Colouring Book

 

Having spent the last couple of hours grading assignments, I decide it’s time for a break. I take out my favourite colouring book, turn to a random page I haven’t coloured in yet, and lay it on my desk. I then take out all my n crayons and line them up on the desk (it’s a very long desk). The colour of the ith crayon is a string c[i] (e.g. "blue"). Many of the crayons have the same colour. In fact, no matter how many crayons I have, there are at most 30 distinct colours amongst them.

 

To start colouring, I always take a sublist (see Q1 for a definition) of the crayons laid on the desk and put away the rest (too many options can be overwhelming and can lead to indecision).

 

I take a look at the line art in front of me and wonder, “How many different colours do I need to make this look great? One? Two? Maybe three?”.

 

Now you understand my dilemma and are fully aware of my indecision. You kindly decide to help me out by telling me for every number k, if I were to use k distinct colours, what would be the minimum number of crayons I’d need to take?

 

Filename

 

Your filename for this question must be q4.py.

 

Input

 

The input consists of a single line containing n space-separated names of colours specifying the list c.

 

Output

 

Let m be the number of distinct colours in c. Then, output m space-separated integers. The kth of them (1-based) should be the minimum number of crayons I’d need to take so that there are at least k distinct colours amongst them.

 

Constraints

 

1 ≤ n ≤ 5 × 104

1 ≤ len(c[i]) ≤ 5

There are at most 30 distinct colours in c.

Time Limit

 

Your program has to finish running within 4 seconds on any valid input.

Sample Input 1

 

green red red blue red red green

Sample Output 1

 

1 2 4

Sample 1 Explanation

 

If I wanted to use only 1 colour, I could take any single crayon.

If I wanted to use 2 distinct colours, I could take a sublist of length 2 such as the sublist red blue.

If I wanted to use all three colours, the smallest possible sublist would have length 4. For example, I could take blue red red green.

Sample Input 2

 

r g z g b b r r g y g g y b

Sample Output 2

 

1 2 3 5 8

Hints

 

There are several ways to solve this problem, but not all of them are fast enough to pass the biggest test cases within the time limit.

Here’s one possible starting point: as you work through the colours, what if you knew the index of the most recent occurrence of each colour?

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.

You can import from bisect, but please don’t add additional import statements.

You can and should use helper functions to keep your code organized.

Test, test, test! The test cases that we give you are not to be considered full testing.

Please submit all of your files to MarkUs.

The final thing you should do is to open your code files in Notepad and make sure that the code displays correctly as only Python code.