ADA- Homework 1 Solved

Problem 1 - ADA Meetup (Programming) (10 points)

Problem Description
N people are lining up to enter a meetup held by the Aged Drivers Association, also known as the ADA. Each person is characterized by two parameters: a preference index pi and a friendliness factor fi. The former indicates what a person likes, and the closer two people’s indices are, the more similar their tastes are, and vice versa. The friendliness factor, on the other hand, indicates how friendly a person is. A person with a higher friendliness factor is more tolerant to people with different tastes. As we all know, old drivers tend to argue about which kinds of cars are better for driving. Therefore, when the i-th person enters the room, the person will only greet those whose tastes the person considers tolerable.

More formally, person i will greet the person j if and only if i > j and |pj − pi| ≤ fi. WillyPillow, being a weeb with no friends to greet, decides to count the number of greetings that takes place.

Input
The first line of the input file contains an integer indicating N.

The second line contains N integers separated by spaces, with the i-th integer indicating pi, the preference index of the i-th person.

The third line contains N integers separated by spaces, with the i-th integer indicating fi, the

friendliness level of the i-th person.

Test Group 0 (0 %)                                                                     Test Group 2 (15 %)

•    Sample Input               • 1 ≤ N ≤ 5 × 103

•    0 ≤ pi,fi ≤ 109

Test Group 1 (10 %)

Test Group 3 (75 %)

•    1 ≤ N ≤ 106

•    0 ≤ pi,fi ≤ 109  • 1 ≤ N ≤ 106

•    |fi − 5 × 108| ≥ 5 × 108                       • 0 ≤ pi,fi ≤ 109

Output
Please output an integer indicating the number of greetings that takes place.

Sample Input 1                                                        Sample Input 2
5                                                                                                           10

18 0 14 8 12                                                                                            17 17 10 10 0 1 6 6 17 13

9 8 14 4 11                                                                                               12 16 18 12 16 6 6 16 15 16

Sample Output 1                                                     Sample Output 2
5                                                                                                           35

Hint
Because the input files are large, please add

•     std::ios base::sync  with stdio(false);

•     std::cin.tie(nullptr); to the beginning of the main function if you’re using std::cin.


Problem 2 - Maximum Subarray Revisited (Programming) (10 points)

Problem Description
WillyPillow has recently learned about the famous Maximum Subarray Problem in the Algorithm Design and Analysis course. However, this problem had already been studied by many people for a long time, which makes it less challenging to solve for WillyPillow. Therefore, he quickly came up with the dynamic version of the maximum subarray problem, but was not able to solve it. Since WillyPillow has no friends to discuss with, you decide to help him with the modified task.

Formally speaking, you are given an integer array A of length N and Q updates. The i-th update is specified by two integers pi,vi, meaning that the pi-th entry of A is updated to vi. You should output the answer to the Maximum Subarray Problem on the modified array after each update. Recall that the answer to the Maximum Subarray Problem is

 !

In particular, if the answer is negative, you should output 0 instead.

Input
The first line of the input contains two integers N and Q, representing the length of the array and the number of updates, respectively.

The second line contains N integers, representing the original array A.

Q lines follow, the i-th of which contains two integers pi,vi, representing an update of Api into vi.

•    1 ≤ N,Q ≤ 5 · 105

•    |Ai| ≤ 109

•    1 ≤ pi ≤ N

•    |vi| ≤ 109

Test Group 0 (10 %)                                                                   Test Group 3 (10 %)

•    N,Q ≤ 2000    • N,Q ≤ 105

Test Group 1 (20 %) Test Group 4 (30 %) • N,Q ≤ 5000 • No other constraints.

Test Group 2 (30 %)

•    Q = 0

Output
Output Q + 1 lines. The first line should contain the answer before any updates. The rest Q lines should contain the answer after each update, following the chronological order.

Sample Input 1                                                        Sample Output 1

10 10                                                                                                   10

-1 -5 -10 0 7 -1 4 -6 -3 -4                                                              4

5 -4                                                                                                      10

3 10                                                                                                     10

5 -5                                                                                                      10

10 8                                                                                                     8

3 -2                                                                                                      10

8 1                                                                                                        9

10 7                                                                                                     9

1 -7                                                                                                      9

3    4         16

4    9

Hint
It may be useful to store the recursion tree of the Divide and Conquer approach to the classic maximum subarray problem.

Because the input files are large, please add

•     std::ios base::sync  with stdio(false);

•     std::cin.tie(nullptr); to the beginning of the main function if you’re using std::cin.

Problem 3 - Good Subpermutations (Programming) (15 points)

Problem Description
A continuous segment [l,r] of a permutation P is good if the value of (Pl,Pl+1,...,Pr) is also continuous. That is, if we collect Pl,Pl+1,...,Pr into a new list B and sort it, then B1 = B2 − 1,B2 = B3 − 1,...,Bi−1 = Bi − 1,...,B|B|−1 = B|B| − 1 hold.

Given a permutation P of length N, count the number of good segments. Note that a sequence A of N integers is called a permutation of length N if 1 ≤ Ai ≤ N for all 1 ≤ i ≤ N and Ai 6= Aj for all 1 ≤ i 6= j ≤ N.

Input
The first line contains an integer N indicating the length of the permutation, where 1 ≤ N ≤ 5 · 105. The second line contains N integers Pi indicating the input sequence. It’s guaranteed that the input sequence is a permutation of length N.

Test Group 0 (10 %)

•    N ≤ 200

Test Group 1 (10 %)

•    N ≤ 2000
Test Group 3 (50 %)

•    N ≤ 105

Test Group 4 (10 %)

•    No other constraints.
Test Group 2 (20 %)

• N ≤ 5000

Output
Print an integer indicating the number of good segments in the given permutation.

Sample Input 1                                                        Sample Output 1

5                                                                                                           15

1 2 3 4 5

Sample Input 2                                                        Sample Output 2

5                                                                                                           10

5 1 2 4 3

Sample Input 3                                                        Sample Output 3

10                                                                                                         26

7 6 5 8 9 10 1 2 3 4

Sample Input 4
20

1 2 3 4 10 9 8 7 6 5 11 14 13 12 20 19 18 17 16 15

Sample Output 4

81

Hint

The following observation might be useful:

• The value of a set of numbers S is continuous if and only if

 


Problem 4 - Different Strings (Programming) (15 points)

Problem Description
You are given two strings S1 and S2, and you have 3 string operations:

•    Insertion of a single character. If a = uv, then inserting a character x between u and v produces uxv.

•    Deletion of a single character. For example, deleting x changes uxv to uv.

•    Substitution of a single character. For example, substituting x for a character y 6= x changes uxv to uyv.

Your goal is to use these operations to make all the corresponding characters in these two strings different. To be more specific, we need to change  and , such that:

 ] for 0 

You need to output the minimum number of operations needed to change the two strings.

Input
There are two lines, which are S1 and S2.

•    S1 and S2 contain only uppercase and lowercase alphabets.

•    |S1|,|S2| ≤ 2000

Output
An integer indicates the minimum number of operations needed.

Subtask 1 (25 %)

•    S1 and S2 contains only alphabet “A”.

Subtask 2 (25 %)

•    S1 and S2 contains only alphabets “A” and “B”.

Subtask 3 (50 %)

•    No other constraints.

 

Sample Input 1                                                        Sample Input 2

abcdcdc                                                                                            AAAAA

abcddc                                                                                              AAAA

Sample Output 1                                                     Sample Output 2

2                                                                                                           4

Problem 5 - Time Complexity & Recurrence (Hand-Written) (15
points)

Note: In this problem, if you use any theorem not covered by the lectures, slides, and the textbook, you should prove it first.

(1)   Asymptotic Notations (5%, 1% each)

True or False.

If your answer is True, no explanation is needed.

If your answer is False, give a counterexample, or briefly explain the reason.

Note: All functions (f(n), g(n)) mentioned below are non-negative and increasing.

(a)     f(n) + g(n) = O(min(f(n),g(n)))

(b)    ef(n) = O(eg(n)) implies f(n) = O(g(n))

 )), then f(n) + g(n) = Θ(f(n))

(2)   Solve Recurrences (10%)

Give the tight bound (Θ-bound, e.g. T(n) = Θ(n3)) of the following recurrence equations. Assume: T(n) = 1,∀n ≤ 1

Note: Show your derivation thoroughly. Following hints is strongly recommended.

 

(hint: use the transformation 

 

(hint: expand the equation to observe the pattern; recall 

Problem 6 - Controllable Ghost Leg (Hand-Written) (20 points)

“Ghost Leg”, known in Japan as Amidakuji (“Amida lottery” because the paper was folded into a fan shape resembling Amida’s halo), is a method of lottery designed to create random pairings between two sets of the same number of prizes. This is often used to distribute prizes to people, where the number of prizes is the same as the number of people.

Ghost Leg consists of vertical lines with horizontal lines connecting two adjacent vertical lines; the horizontal lines are called “legs”. Note that “legs” cannot touch other legs. The number of vertical lines equals the number of people, and at the bottom of each line there is an item - a prize that will be paired with a player. The general rule for this game is: choosing a line on the top, and following it downwards. When a horizontal line is encountered, the player needs to transit to another vertical line and then continue going down. The procedure is repeated until reaching the end of the vertical line, and then the player gets the corresponding prize. Therefore, choosing the line decides which prize you get. You can refer to the link for more details: https://en.wikipedia.org/wiki/Ghost_Leg.

 

                           The example of one ghost leg.                       Example of finding the prize if A is chosen.

You, the host of the party, want to distribute N prizes to N players by ghost leg. In addition, you plan to perform some black-box tricks on this game so that the person choosing a specific start must be able to get a specific prize you planned.

Here comes a problem: Now given a ghost leg board without any horizontal lines, you have k constraints, which assign k starting points with their corresponding prizes. What is the minimum number of horizontal lines to be added in order to satisfy all k constraints?

For example, you have a ghost leg without any horizontal lines as Fig. 1, and the constraints are {(c should go to 1), (b should go to 4)}. Thus, the answer should be 3, and one of the solution is illustrated in Fig. 2.

 

                        Fig 1. An empty ghost leg if N = 4                     Fig 2. A solution meets all the constraints

Before solving this problem, “inversion” is introduced for helping you find the solution.

Inversion Given a sequence of unique numbers B = b1,b2,...,bn, an inversion is a pair of numbers bi and bj in this sequence such that i < j and bi > bj . Let I(B) be the set of inversions in B. For example, if B = 1,3,5,2, I(B) = {(3,2),(5,2)}, and the number of inversions is 2 (|I(B)| = 2).

(1)   Given an unsorted and unique sequence B with n numbers, please design an efficient algorithm to calculate the number of inversions |I(B)| in O(N logN) time. (7 points)

(2)   Explain why your algorithm runs in O(N logN). (5 points)

(3)   Prove that the number of exchanges when performing bubble sort on the sequence S is equal to the number of inversions in S. (2 points)

Controllable Ghost Leg

(4)   Describe a O(N logN) algorithm that calculates the minimum number of horizontal lines when |constraints| = N. You are required to prove the correctness in this problem. (2 points)

(5)   Describe a O(N logN) algorithm that calculates the minimum number of horizontal lines when

|constraints| ≤ N. You are required to prove the correctness in this problem. (4 points)

Problem 7 - Folding Blocks (Hand-Written) (15 points)

“Folding Blocks” is a puzzle game, in which you need to unfold the blocks in order to fill the whole space. When you unfold a block, the block is extended with the same size to the unfolding direction. You can play the 2D version of this game here: https://www.crazygames.com/game/ folding-blocks-puzzle.

Here we play the puzzle on a 1D board, where the whole space can be viewed as a line illustrated below. If a 2-length block initially fills 3-4 positions, and now we unfold it to the right side, it will fill 3-6 positions of the board. Similarly, if we unfold it to the left side, it will fill 1-4 positions of the board.

Now given the length of the board, denoted as N, and the initial status (each block’s length and position), please decide whether this puzzle can be solved. Note that the given position of the block is its leftmost side and a puzzle is solved once all positions are filled after unfolding without overlapping or out-of-board blocks.

 

Fig 1. You can unfold the block to the left or right, but you cannot overlap other blocks or make blocks out of board when unfolding.

 

Fig 2. There’s an example puzzle and solution.

(1)   Let’s start with a special case which has only a block on the board initially. Derive a method which can determine whether the problem is solvable in constant time. (Assume the time complexity of a logarithmic operation (log) is O(1)) (2 points)

(2)   Assume there is only one block on the board initially. Design a O(logN) algorithm to output the sequence of unfold operations that solve the puzzle if it is solvable. (1 point)

(3)   Assume there is only one block on the board and the distance between the block to the left and right boundaries are d1 and d2, respectively. Prove that there are O(d1 + d2) possibilities of the status after unfold operations. You can think of a status as a binary array representing whether each position is occupied. (3 points)

(4)   Let’s now consider the general case which can contain more than one block initially. Please design a DP algorithm to solve the problem in O(N) time. (5 points)

(5)   Explain your algorithm in (4) in terms of the properties of overlapping sub-problems and optimal substructure. (2 points)

(6)   Prove that the time complexity of your DP algorithm is Θ(N). (2 points)