Algorithm Design Homework #1 Solution

Problem 1 - Tower of Hanoi (Programming) (10 points)

Problem Description

Tower of Hanoi is a classic mathematical game, which consists of three vertical pegs and several disks of di erent sizes. Robert, an extraordinarily handsome guy, is good at playing Tower of Hanoi optimally.

Once, he played the games repeatedly for a few days and nights until he was too tired and suddenly fell into sleep. After he woke up, he forgot what he had done for the current game. Moreover, he might even make some wrong moves.

You, a big fan of Robert, are eager to help him. Given the total number of disks and the game’s current state, please tell him whether he is on the right way. That is, there is an optimal solution containing the current state. Also, if he is on the right way, please tell him the minimum number of remaining steps to nish the game. Since the number of remaining steps might be extremely large, you should tell him the number modulo 998; 244; 353.

Input

The rst line of the input contains an integer n, indicating the number of disks in his current game. The disks are numbered from 1 to n (from small to big). Also, the pegs are numbered from 1 to 3 (from left to right).
The following three lines contain (ki + 1) space-separated integers: the rst integer ki of the ith line indicates the number of disks on the ith peg, and the following ki integers are the disks’ numbers from top to bottom on this peg.

3
    • 1   n = P ki   100000
i=1

    • The input is guaranteed to be a valid state of the game.


Test Group 0
(0 %)
Test Group 3 (20 %)
•
Sample Input
•
The current state is on the right way.
Test Group 1
(20 %)
Test Group 4 (30 %)
•
n  10

•
No other constraints.

Test Group 2 (30 %)

    • n  50


Output

If he had moved correctly, output an integer indicating the minimum number of remaining steps to nish the game modulo 998; 244; 353. Otherwise, output \-1" (without quotes).

Algorithm Design and Analysis (NTU CSIE, Fall 2021)    Homework #1



Sample Input 1
Sample Input 2
Sample Input 2
3


3


5



1
3

1
3

1
3


2
2
1
0


1
2


0


2
2
1
3
5
4
1

Sample Output 1    Sample Output 2    Sample Output 2

4    -1    5

























































3
Algorithm Design and Analysis (NTU CSIE, Fall 2021)    Homework #1



Problem 2 - Hellish Gag (Programming) (15 points)

Problem Description

The description is adapted from a true story.

Designing ADA Homework #1, the TA 1011 has come up with a dark story as a problem descrip-tion. Because ADA is a course ful lled with hopes and happiness, his depressing story is considered a hellish gag, and the TA is banished to the uttermost depths of the hell.

Upon noticing 1011’s arrival, Hades, the king of the underworld, decides to grant him an oppor-tunity to resurrect. \If you are able to solve this algorithm problem, you will get a chance to be back to the world.", said Hades, \Here comes the problem. 99% deceased cannot solve it..."


Given 2 arrays p; z of length N and 3 constants a; b; c. Let di be the number of j’s satisfying all of the following conditions:

    • j 2 f1; 2; : : : ; Ng

    • j 6= i

• pj >
b
pi +
c









a


a


• zj > zi










N
Please  nd the summation of di; that is,
Xi

di.






=1

However, 1011 is getting pale and turns unable to solve the problem. To ask for your help, he tells you this story by setting the exact problem in your Homework #1. Please save 1011 from the hell (so he could get back to the world and set another problem in your next ADA Homework).

Input

The rst line of the input contains 4 numbers N; a; b; c, denoting the the size of 2 arrays and the 3 constants used in the condition description.

Then, N lines follow, the i-th of which contains two non-negative integers, pi and zi, denoting the entries of two arrays.

    • 1N2106

    • 1   a  109

    • 0   b  109

    • 109   c  109

    • 0   pi; zi   109; 8i = 1; 2; : : : ; N










4
Algorithm Design and Analysis (NTU CSIE, Fall 2021)
Homework #1



Test Group 0 (0 %)
Test Group 1 (10 %)
Test Group 2 (5 %)
• Sample Input
• N   2000
• b = 0

Test Group 3 (15 %)

    • (a; b; c) = (1; 1; 0)

• [z1; z2; : : : ; zN ] is a permutation of [0; 1; : : : ; N    1].


Test Group 4 (30 %)    Test Group 5 (40 %)

• All zi’s are distinct.    • No additional constraint.


Output





N










Xi
di.





Output 1 integer, the summation










=1





Sample Input 1
Sample Input 2
Sample Input 3
4
1
0
0
4
1 1
2
4
2021
0
1111111
0
0


1
47

123 4


0
0


3
22

567 8


0
0


7
81

901 2


0
0


5
65

345 6


Sample Output 1
Sample Output 2
Sample Output 3
0



3


3





Explanation

    • In the  rst test case, (d1; d2; d3; d4) = (0; 0; 0; 0), so the required is 0 + 0 + 0 + 0 = 0.

    • In the second test case, (d1; d2; d3; d4) = (2; 1; 0; 0), so the required is 2 + 1 + 0 + 0 = 3.

    • In the third test case, (d1; d2; d3; d4) = (1; 0; 1; 1), so the required is 1 + 0 + 1 + 1 = 3.


















5
Algorithm Design and Analysis (NTU CSIE, Fall 2021)    Homework #1



Problem 3 - ADA Rectangle (Programming) (15 points)

Problem Description

Given N points (p1; p2 ; pn) on a 2-dimensional (2D) plane, we de ne two points pi and pj as a good pair if there exists a rectangle satisfying the following conditions:

    1. The sides of the rectangle are parallel to the X-axis and Y-axis.

    2. The rectangle contains these two points pi; pj only; no other points fall within this rectangle.

How many good pairs of points are there in total?

Input

The    rst line of the input contains one integer N, denoting the number of points.

The ith of the following N lines contains two integers xi; yi, indicating the coordinates of the ith point.


Test Group 0 (0 %)
Test Group 2 (35 %)
• Sample Input.
•1N3103

• 1   xi   N

• 1   yi   N

• All xi are distinct.

• All yi are distinct.
Test Group 1 (20 %)
Test Group 3 (45 %)


•1N5102
•1N2105
• 1   xi   N
• 1   xi   N
• 1   yi   N
• 1   yi   N
• All xi are distinct.
• All xi are distinct.
• All yi are distinct.
• All yi are distinct.


Output

Print the number of good pairs in a single line.


Sample Input 1
Sample Output 1
5

8
1
5

2
2

5
4

4
1

3
3




6
Algorithm Design and Analysis (NTU CSIE, Fall 2021)    Homework #1



Sample Input 2
Sample Output 2
5

4
1
1

2
2

3
3

4
4

5
5



Sample Input 3
Sample Output 3
3

3
1
2

2
1

3
3



Hint


















    1. The good pairs in Sample Input 1 are (p1; p2), (p1; p3), (p1; p5), (p2; p4), (p2; p5), (p3; p4), (p3; p5), (p4; p5).

    2. You are also encouraged to use the above picture to nd inspiration. When conquering, you can use stacks to maintain the black points, and use binary search to identify how many black points are in the gray scope.

    3. You can maintain a stack on each of the left and right sides to keep the \needed points", which are the points blocking the current point or forming a good pair with the current point you are focusing on.

    4. Instead of std::stack, you can use std::vector to maintain stack and perform binary search algorithm on std::vector directly using std::lower bound.

    5. GL & HF (Good Luck and Have Fun).










7
Algorithm Design and Analysis (NTU CSIE, Fall 2021)    Homework #1



Problem 4 - Candies (Programming) (10 points)

Problem Description

Baluteshih brings N candies to his friend, Waynetu. Those candies are lined on the table. Each candy has its own sweetness indicated by an integer. The sweetness of the candies from left to right are a1, a2, : : :, aN , respectively.

Baluteshih assigns Waynetu an interesting mission. He asks Waynetu to remove some candies from the table, so that the remaining candies on the table are alternative. Formally, we say that a sequence of candies with sweetness b1, b2, : : :, bk is alternative if bi bi+1 0 holds for all 1 i < k.

With the aforementioned rule, Waynetu hopes to maximize the sum of the sweetness of the candies on the table. Please help Waynetu nd the maximum possible sum of the remaining candies’ sweetness and provide a solution to reach the optimal case.

Input

The rst line contains two integers T , representing the number of testcases, and flag (flag 2 f0; 1g), which will be described in the output section.
Each testcase includes two lines: the    rst line contains an integer N (1    N    105), and the
second line contains N integers a1, a2, : : :, aN (jaij    109).
It is guaranteed that the sum of N does not exceed 105.

Test Group 0
(0 %)
Test Group 3 (10 %)
• Sample Input.
• flag = 1.
Test Group 1
(20 %)
• PN   1000.
• flag = 0.

Test Group 4 (20 %)



• PN   1000.
• flag = 1.
Test Group 2 (50 %)

    • flag = 0.


Output

For each testcase, please print an integer representing the maximum possible sum of the sweetness in the rst line. If flag equals 1 mentioned in the input section, please furthermore print out one optimal way in the second line: an integer k representing the number of candies remaining on the table, followed by k integers i1, i2, : : :, ik, representing the indices of candies.











8
Algorithm Design and Analysis (NTU CSIE, Fall 2021)    Homework #1



Sample Input 1
Sample Output 1
1
0
8
5


3
-16-74




Sample Input 2
Sample Output 2
2
0

3
3


3
1
2
3

4



1
-23-4



Sample Input 3
Sample Output 3
3
1

-1


1


1
1

-1


6


3


3
1
2 3
5
0 1

-1


4


1
1

-1 -2
-3 -4





Hint

    1. Since each input includes several independent testcases, please carefully clear all results of the current testcase before dealing with the next testcase.





























9
Algorithm Design and Analysis (NTU CSIE, Fall 2021)    Homework #1



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



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

Note: In this problem, you may assume the base, b, for logarithm has constraints b 2 R; b > 1.

    (1) Asymptotic Notations (10%)

Prove or Disprove.

If you think the statement is correct, you should provide a comprehensive proof.

If you think the statement is incorrect, you should disprove it or give a counterexample.


        (a) (2%) ln n! = O(ln nn)
        (b) (2%) nln c =  (cln n)
p
(c) (3%)    n = O(nsin n)

(d) (3%) (ln n)3 = o(n)


(2) Solve Recurrences (15%)

Give the tight bound (  -bound, e.g., T (n) =    (n3)) of the following recurrence equations.

Assume:    T (n) = 1; 8n    2

Note: Show your derivation thoroughly by using the assigned method.

(a) (2%) T (n) = 2T (n    1) + 1

Please use brute force method.

    (b) (4%) T (n) = T (n2 ) + T (n4 ) + T (n8 ) + n log n Please use recursion tree method.

    (c) (4%) T (n) = 4T (n2 ) + n log(n)
Please use master theorem method.
p    p

(d) (5%) T (n) =    nT (  n) + n

Please use variable transformation method.




















10
Algorithm Design and Analysis (NTU CSIE, Fall 2021)    Homework #1



Problem 6 - Ghost Leg (Hand-Written) (15 points)

In this problem, please brie y explain your solution in text. Do not use pseudo code, or you will receive penalty.

\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.
























Alan is a party host, and he distributes N prizes to N players by a ghost leg. The party attendees can get a gift based on the game result. However, Alan is not as generous as others think. Instead, he is a cunning person. Alan does not want to give any precious presents to attendees at all, so he assigns his employees to attend the party to collect good gifts and leave consolation prizes to other ignorant players.

You, as Alan’s personal assistant, please help him manipulate the gift distribution result. You have to design an e cient algorithm for this black-box trick to give all good prizes to the designated people. The speci c start must reach the planned destination as expected.

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 solutions is illustrated in Fig. 2.




11
Algorithm Design and Analysis (NTU CSIE, Fall 2021)    Homework #1


























To help you solve the problem, we de ne the property of \inversion".

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) = f(3; 2); (5; 2)g, and the number of inversions is 2 (jI(B)j = 2).
Please answer the questions below.

    (1) (4pt) Given an unsorted and unique sequence B with n numbers, please design an e cient algorithm to calculate the number of inversions jI(B)j in O(N log N) time.
    (2) (3pt) Explain why your algorithm runs in O(N log N).

    (3) (2pt) Prove that the number of exchanges when performing bubble sort on the sequence S equals the number of inversions in S.

    (4) (4pt) Describe an O(N log N) algorithm that calculates the minimum number of horizontal lines in the ghost leg when jconstraintsj N.
    (5) (2pt) Prove the correctness of your algorithm in the previous problem.

























12
Algorithm Design and Analysis (NTU CSIE, Fall 2021)    Homework #1



Problem 7 - Unfair Lucas (Hand-Written) (10 points)

Far Far Away Kingdom has a custom that all philosophers gather at a round table to keep their friendship, and they hire a chef to prepare some dishes for them. Supposed that the round table is big enough to t N philosophers, and their indices are shown in the picture below. Lucas is a chef standing in the center of the round table, and he needs to prepare some dishes for all philosophers.




























Because Lucas is not familiar with all philosophers, he decides to prepare some tasty dishes for the philosophers who are friendly and awful dishes for other philosophers. However, Lucas is afraid of being accused of his unfair treatment, so he decides to choose a contiguous part of philosophers to get tasty dishes, such that the possibility of being charged disparate treatment is minimized. (Note: The contiguous part of philosophers means that you can choose the philosophers whose indices are n; 1; 2; 3 to eat tasty dishes, but you cannot choose the philosophers whose indices are n; 1; 3; 4 because of skipping the 2nd philosopher.)

Given the friendliness value fi for i = 1; 2; 3; : : : ; N, of the ith philosopher, please help Lucas nd out a contiguous part of philosophers such that the total friendliness value of those chosen philosophers is maximized. Moreover, he hopes that at least one philosopher can have tasty dishes.

    (1) (2%) Consider 10 philosophers and their friendliness values f = [ 3; 0; 6; 4; 0; 1; 2; 3; 3; 9]. What is the maximum total of friendliness values?

    (2) (3%) Please design an algorithm with both time complexity and space complexity in O(N) in the worst case. Brie y explain your algorithm and prove its time complexity.

    (3) (5%) Now, Lucas wants to make his friends happier, so he decides to skip at most one philosopher in the contiguous part to give tasty dishes such that the maximum total friendliness value can be increased. After applying this policy, please design an algorithm with both time complexity and space complexity in O(N) in the worst case. Brie y explain your algorithm and prove its time complexity.





13