CSIE - Homework #1 - Solved

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



Tower of Hanoi is a classic mathematical game, which consists of three vertical pegs and several disks of different 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 finish the game. Since the number of remaining steps might be extremely large, you should tell him the number modulo 998,244,353.

Input

The first 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 first 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 %)

•    Sample Input

Test Group 1 (20 %)

•    n ≤ 10
Test Group 3 (20 %)

•    The current state is on the right way.

Test Group 4 (30 %)

•    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 finish the game modulo 998,244,353. Otherwise, output “-1” (without quotes).

 

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

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


Designing ADA Homework #1, the TA −1011 has come up with a dark story as a problem description. Because ADA is a course fulfilled 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 opportunity 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...”

 

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

•    1 ≤ N ≤ 2 × 106

•    1 ≤ a ≤ 109

•    0 ≤ b ≤ 109

•    −109 ≤ c ≤ 109

•  

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

Output 1 integer, the summation Xdi.

i=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 first 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.

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



Given N points (p1,p2 ··· ,pn) on a 2-dimensional (2D) plane, we define 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 first 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 %)

•    1 ≤ N ≤ 3 × 103

•    Sample Input.       • 1 ≤ xi ≤ N

•    1 ≤ yi ≤ N

•    All xi are distinct.

•    All yi are distinct.

Test Group 1 (20 %)

Test Group 3 (45 %)

•    1 ≤ N ≤ 5 × 102         • 1 ≤ N ≤ 2 × 105

•    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
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 find 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.



Problem 4 - Candies (Programming) (10 points)



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 find the maximum possible sum of the remaining candies’ sweetness and provide a solution to reach the optimal case.

Input

The first line contains two integers T, representing the number of testcases, and flag (flag ∈ {0,1}), which will be described in the output section.

Each testcase includes two lines: the first line contains an integer N (1 ≤ N ≤ 105), and the second line contains N integers a1, a2, ..., aN (|ai| ≤ 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.

•    PN ≤ 1000.

Test Group 1 (20 %)

Test Group 4 (20 %) • flag = 0.

•    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 first 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.

Sample Input 1                                                        Sample Output 1

1 0                                                                                                        8

5
3 -1 6 -7 4

Sample Input 2                                                        Sample Output 2

2                                                                                                                                                                 0 3

3                                                                                                                                                                 3

1 2 3

4

1 -2 3 -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.

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

Note: In this problem, you may assume the base, b, for logarithm has constraints b ∈ 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%) lnn! = O(lnnn)

 

(d) (3%) (lnn)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,∀n ≤ 2

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

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

Please use brute force method.

 

Please use recursion tree method.

 

Please use master theorem method.

                                                     √         √

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

Please use variable transformation method.

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

In this problem, please briefly 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 efficient algorithm for this black-box trick to give all good prizes to the designated people. The specific 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.

 

To help you solve the problem, we define 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) = {(3,2),(5,2)}, and the number of inversions is 2 (|I(B)| = 2).

Please answer the questions below.

(1)   (4pt) 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.

(2)   (3pt) Explain why your algorithm runs in O(N logN).

(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 logN) algorithm that calculates the minimum number of horizontal lines in the ghost leg when |constraints| ≤ N.

(5)   (2pt) Prove the correctness of your algorithm in the previous problem.

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 fit 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 find 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. Briefly 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. Briefly explain your algorithm and prove its time complexity.