Algorithm Design Homework #2 Solution

Problem 1 - Glass Bridge 2.0 (Programming) (12 points)

Problem Description

Improved from the fth game in Squid Game (2021), Glass Bridge 2.0 is another deadly game played on an n m grid, where contestants have to reach the goal cell by jumping from a square glass to another. To better describe the environment, we use (i; j) to denote the cell on the i-th row and on the j-th column. The starting cell is located on (1; 1) while the goal one is located on (n; m). For each of the remaining cells, the cell (i; j) satis es exactly one of the following states:

    • The cell is placed with a square glass with a given risk value, since the glass may be smashed when you step on it. To make the game more exciting, there may be a bundle of banknotes on that piece of glass. Considering the revenue and risk, the expected pro t could be modeled as ai;j if one jumps onto the glass.

    • The cell is empty, since a previous contestant has smashed the glass there. In other words, the cell is now impassable { if one steps on this cell, she/he will fall into a horrible abyss immediately.

You, as the next contestant to move on, are going to reach the goal cell by jumping from one cell to another. A jump from (x; y) to (x0; y0) is valid if all of the following conditions hold:

    • The cell (x0; y0) is placed with a square glass.

    • x  x0   n

    • y   y0   m
• 1    (x0    x) + (y0    y)    k

Currently standing on the starting cell, (1; 1), you would like to rst realize if it is possible to reach the goal cell with those currently existing glasses. If so, please come up with a jumping path such that S, the sum of expected pro t over all cells on your path, is maximized.

Input

The    rst line of the input contains 1 integer T { the number of test cases. Then, in each test case:

    • The rst line is an empty line. This may make it more friendly for you to distinguish between test cases with your naked eyes.

    • The second line contains 3 integers n; m; k, denoting the size of the grid and your jumping ability.

    • Then, n lines follow, the i-th of which contains m strings or integers, the j-th of which is:

{ 0, if (i; j) = (1; 1) or (n; m).
{ ai;j, if the cell (i; j) is placed with a square glass.

{ \X" (without quotation marks), if the cell (i; j) is empty.












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



Constraints

    • 1T100

    • 1   n; m  106

    • 2   nm  106
X
    • nm  106

• 1    k    n + m    2

    • 456; 456; 456; 456   ai;j   456; 456; 456; 456

    • You may obtain up to 10:2 points from this problem even if your solution is not fully accepted.


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

• Sample Input    • n; m    30    • n; m    30

• k = 1


Test Group 3 (45 %)

Test Group 4 (15 %, Bonus Subtask)
•
n; m  30
or  T = 1 and n; m  400

• No additional constraint

Output

For each test case:

    • In the rst line, please output a string s. s = Passable if it is possible for you to reach the goal cell with those currently existed glasses. Otherwise, s = Impassable.

    • If s = Passable, you have to specify your jumping path. In the second line, please output S, the maximized sum of the expected pro t. In the third line, please output L, the length (including the starting and goal cells) of your path planned. Then L lines follow, the i-th of which should contain 2 integers, xi; yi, denoting the i-th coordinate in your path. Note that you don’t have to minimize the length of your path. If there are multiple solutions, you may print any.

Hint

    1. Since each input includes several independent test cases, please carefully clear all results of the current test case before dealing with the next one.

    2. In Sample Input 1, the rst and second test cases are exactly the same. However, the Sample Output comes up two di erent paths to answer the same test case. This is just a demonstration on the special scoring method.

    3. Test Group 4 may be a challenging subtask. This could be viewed as a bonus subtask since you are still able to obtain 50 points from programming problems even without solving it. Nevertheless, you are encouraged to give it a try because it’s solvable without any advanced data structure or algorithm { what you need is just an ingenuity!





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



Sample Input 1
Sample Output 1
5


Passable



-1
3
3
1
5
0
0
0
1 1
-10-1
1 2
X-10
2 2



3 2
3
3
1
3 3
0
0
0
Passable
-10-1
-1
X-10
5



1 1
3
3
1
1 2
0
-7 X
2 2
X X
20
2 3
0
10
0
3 3



Impassable
3
3
2
Passable
0
-7 X
13
X X
20
4
0
13
0
1 1



1 2
5
7
9
2 3
0
X
XXXXX
3 3
X X
XXXXX
Passable
X X
X -456456456456 X X X
-456456456456
X X
XXXXX
3
X X
XXXX0
1 1



3 4



5 7


Behind the Scene

Some wise words from YP, one of the lead TAs, upon knowing the Test Group 4 in this problem:






















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



Problem 2 - ADA Removal Game (Programming) (15 points)

Problem Description

Consider an array A containing N elements. For each operation, you can choose 2 or 3 contiguous elements, whose pairwise greatest common divisor is greater than 1, and remove them from the array. After removal, the remaining parts of the array are concatenated. Meanwhile, you earn points by doing this operation, and the point is calculated by adding up the greatest common divisor of each pair of adjacent elements you removed.

Formally, consider an array A of length N, you can choose two integers i; k such that 1 i i+k 1 N; k = f2; 3g where gcd(Ax; Ay) > 1; 8i x y i+k 1. Remove Ai; : : : ; Ai+k 1 from the array and
of
i+k  2

P
get
gcd(Ap; Ap+1) points. After the operation, the new array becomes A1; : : : ; Ai  1; Ai+k; : : : ; AN
p=i
length N    k.

You can perform the above operation multiple times until the array is empty. Please nd the maximum total points you can receive to eliminate the entire array, and determine whether it is possible to do so.

For example, array [2; 3; 12; 6; 4] can be totally eliminated by removing (3; 12; 6) and (2; 4) in order, which gets 11 points. Or, it can also be removed by (3; 12) and (2; 6; 4), which gets 7 points. There is no other way to remove the entire array. Hence, the answer should be the greater one 11.

Input

The    rst line contains an integer indicating N, where 2    N    500.

The second line contains N space-separated positive integers ai, where 2    ai    109.

Test Group
0
(0 %)
Test Group 3 (30 %)
• Sample Input
•N  100
Test Group
1
(10 %)
Test Group 4 (40 %)
•N  10


• No other constraints.

Test Group 2 (20 %)

    • 2jai; 8i


Output

Please output an integer indicating the maximum points. If it is impossible to eliminate the entire array, output 1.


Sample Input 1
Sample Output 1
5



11
2
3
12 6
4





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



Sample Input 2
Sample Output 2
5





23
10 9

3 10
10

Sample Input 3
Sample Output 3
6





13
2
3
6
12

6 4

Sample Input 4
Sample Output 4
5





-1
2
3
8
6
4




















































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



Problem 3 - IOICamp (Programming) (15 points)

Problem Description

IOICamp is a competitive programming training camp held by NTU CSIE students. Xiao Feng, an IOICamp sta , is full of enthusiasm to dedicate himself to making it better.

One day, Baluteshih, the general coordinator of IOICamp, assigned N tasks to Xiao Feng. Con-cretely, the ith task consists of xi units of work. Each unit of work costs one day for Xiao Feng to complete. Besides, Xiao Feng can not do two di erent tasks in one day simultaneously. Because of Baluteshih’s requirements, Xiao Feng can only work on the ith task between sith day and eith day (inclusive).

To encourage Xiao Feng to nish as much work as possible, Baluteshih gives him some bene ts. For the ith task, if Xiao Feng completes yi units of work, he will get pi yi bonus from Baluteshih. Note that Xiao Feng can still get the bonus from Baluteshih even if he didn’t nish all units of work in the one task. Please help Xiao Feng to calculate the maximum bonus he could receive from his kindly boss, Baluteshih :).

Input

The rst line of the input contains only one integer N, denoting the number of tasks assigned to Xiao Feng.

In the following N lines, the ith line contains four integers si; ei; xi; pi, describing the information of the ith task.

constraints

    • 1   N   3000.

    • 1   si   ei   109.
• 1    xi    ei    si + 1.
    • 1   pi   109.

Test Group 0 (0 %)

    • Sample Input.

Test Group 1 (15 %)

    • s1    s2    : : :  sN .

    • e1    e2    : : :  eN .

    • pi = 1; 81   i  N.

Test Group 2 (40 %)

    • pi = 1; 81   i  N.











Test Group 3 (15 %)

    • s1    s2    : : :  sN .

    • e1    e2    : : :  eN .
• xi = ei    si + 1; 81    i    N.

Test Group 4 (30 %)

    • No other constraints.








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



Output

Print one integer denoting the maximum bonus Xiao Feng could receive if he arranges the work optimally.

































































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



Sample Input 1
Sample Output 1
3



4
1
3
2
1

1
5
1
1

2
4
1
1



Sample Input 2
Sample Output 2
5



55
6
7
2
6

1
10

3 6

6
8
2
8

3
8
1
9

1
9
7
2



Sample Input 3
Sample Output 3
5



67
9
10

1 5

5
15

6 7

4
6
2
8

1
6
1
3

3
9
1
1



Sample Input 4

Sample Output 4
10


741483180481768
317828572
952962709
511194031
474210
139065667
594136128
184836056
727043
145449199
856665845
135232964
221941
185367317
719253355
508496356
303732
286924029
536237215
174723858
743784
448407424
788782769
294918233
970051
128701901
369779350
133590454
996886
268148730
724234276
442825804
255091
658359136
999211180
190588357
715619
114934339
328552693
120729904
373197


Hint

    1. It might be useful to solve Test Group 2 before solving the rest of the problem. If you encounter some di culties, please try to solve it rst.

    2. It is recommended to use C++ Standard Template Library (STL) data structures, such as std::stack, std::queue, std::priority queue, std::list, std::vector, and std::set. They can reduce your coding complexity.






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



Problem 4 - Restricted Candies (Programming) (10 points)

Problem Description

The de nition of an alternating sequence is slightly di erent from that of in Homework 1.

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 alternating. Formally, we say that a sequence of candies with sweetness b1, b2, : : :, bk is alternating 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.

However, Ltf0501 comes and interrupts the mission. Because he wants to make this mission more interesting, he gives Waynetu an additional restriction, that is, Waynetu needs to leave exactly k candies on the table. Moreover, for each k between 1 to N, Waynetu needs to determine whether it is possible to leave exactly k candies on the table; if so, Waynetu also need to maximize the sum of the sweetness for that k value.

Please help Waynetu nd the maximum possible sum of exactly k remaining candies’ sweetness for each k between 1 to N.

Input

The rst line contains two integers T , representing the number of test cases, and flag (flag 2 f0; 1g), which will be described in the output section.
Each test case 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; ai 6= 0).
It is guaranteed that the sum of N within the same input    le does not exceed 105.

Test Group 0 (0 %)

    • Sample Input.





Test Group 1 (20 %)

    • flag = 1, a1 > 0 and aN > 0.
    • P N   1000.

Test Group 2 (20 %)

    • P N   1000.

Test Group 3 (30 %)

    • flag = 1, a1 > 0 and aN > 0.

Test Group 4 (30 %)

    • No additional constraints.

Output

For each test case, please print N integers in a line, separated by spaces. The ith number represents the maximum possible sum of the sweetness when Waynetu leaves exactly i candies on the table. If it is impossible to leave exactly i candies on the table, just output 0 for the ith number.


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



If flag = 1, then you can get Accepted when you have at least bN2 c correct answers for each test cases.


Sample Input 1
Sample Output 1
1
0
6 5
8 2
5
5




3
-16-74






Sample Input 2
Sample Output 2
2
0

3 0
0

3


3 1
2
-2
1
2
3



4





1
-23-4





Sample Input 3
Sample Output 3
3
1


0


1



5
0
0
1



0
0
0 0
3






5
-1 1




4






1
2
3
4





Hint

    1. Since each input includes several independent test cases, please carefully clear all results of the current test case before dealing with the next one.

    2. In Sample Output 3, you will get Wrong Answer if flag = 0. The Sample Output is just a reminder for the special scoring method.

    3. It is recommended to use C++ Standard Template Library (STL) data structures, such as std::stack, std::queue, std::priority queue, std::list, std::vector, and std::set. They can reduce your coding complexity.

















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



Problem 5 - Toyz’s Dog (Hand-Written) (30 points)

You, Asiagodtone, as known as Toyz’s dog, notices that someone smelled strange, so you decide to trace him. With your big fat nose, you keep tracking that strange smell. After a long trip, you nally arrive at a smoky place. There is a castle surrounded by a moat, and the only path to get into the castle consists of N 1 oating stones in front of the gate. Each stone will sink to the deep when you step on it. You have to choose some stones as a route so that you can go into the castle and then catch the odd-smelling guy. When leaving, you have to go through all the remaining stones to prevent the enemies in the castle from chasing you. That is, you could only step on each stone once and you should let all of them sink to the bottom after leaving the castle.

Subproblem (a)

Assuming that the initial place is S0 and the castle is located at SN . The N 1 stones are numbered as S1 to SN 1. When you jump from Sa to Sb, you spend E(a; b) energy. It does NOT guarantee that E(a; b) E(a; c) + E(c; b). Note that you are too fat to turn around your body on the stone. For example, N = 3, your possible path can be:
f !  !  !  !
S0
g

S0
S1
S2
S3



f !  !  !  !
S0
g

S0
S1
S3
S2



f !  !  !  !
S0
g

S0
S2
S3
S1



f !  !  !  !
S0
g
:
S0
S3
S2
S1



Now, you want to design a dynamic programming algorithm to nd the smallest cost of the entire trip in O(N2) time complexity. Note that your should let dp(i; j) as the minimal cost of the trip, where your last point on the way you go is Si and your rst point on the way you left is Sj and then

minus E(i; N) + E(N; j). Under dp(i; j) state, you should already choose S0 to Smax(i;j) to your path no matter the stone is on the way go or left.

    (1) (6%) Please recursively de ne dp(i; j) and prove your correctness and time complexity.

    (2) (6%) With the recursive function you de ned in question (1), please solve the problem in O(N) space complexity.

    (3) (6%) Please get the optimal path in the same space complexity as question (2).

Subproblem (b)

After the capture, you surprisingly nd out that the man is your master, Toyz. However, you still send him to the jail for the justice. Unfortunately, his friend, R-code, helps Toyz escape from the jail and then ee back to his castle. This time, he set a smoke bomb at each stone on the way to the castle. Whenever you stand on a stone Sn, the bomb can be triggered and causes Dn damage on you. Luckily, you nd a switch that can turn o all the bomb trap in the castle, so you will be safe when leaving the castle.

Assuming that you have initial Health Points H, when you stand on Sn on the way to castle, your Health Points would be reduced by Dn. Under this additional constraint, please design a dynamic programming algorithm to nd the smallest cost of the entire trip, as in the subproblem (a), while keeping your Health Points greater than zero.

    (1) (6%) Please modify your de nition of dp function to solve the problem in O(HN2) time.

    (2) (6%) Please prove the correctness and the time complexity of your de nition.




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



Problem 6 - Howard’s Desiring Order of Courses (Hand-Written) (20 points)

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

Howard Wang, as known as rap god, started his rst semester in the CSIE department last au-tumn. When he was 18, he set a goal for his college life, \Having a girlfriend." However, due to COVID-19 pandemic and lack of courage, he is still not familiar with most of his classmates, let alone making any female friend. L.Y.P., who is his best friend and a natural charmer, gave him an advice, \How about enrolling in courses with the maximum number of girls?". Following the advice, Howard started to arrange his timetable of the upcoming semester. He collected essential information all CSIE courses and marked his preference of them. As Howard’s friend, please help him nd the maximum satisfying value he can reach by arranging a desiring order of those courses.

Assuming that there are n courses in the CSIE department, which are C1 to Cn. For each course Ci, Howard marked his preference of the course with Pi. Moreover, the maximum satisfying value is de ned as the maximum number for that could be formed by concatenating some of the course preference values (in digits) in any order. For example, if there are three courses C1; C2; C3 in CSIE, which P1 = 2 and P2 = 40 and P3 = 2, the maximum satisfying value will be 4022.

Lastly, there are some assumptions as follows, which are used in the following problems.

Assumption 1 Preference of the course is always a single digit number, that is 8 1 i n, Pi 2 [0; 9].

Assumption 2 Preference of the course is always an integer, that is 8 1    i    n, Pi 2 N.
Assumption 3 The maximum satisfying value should be a multiple of 3.

Please answer the following problems.

    (1) (2%) Given preference value of 6 courses P = [1; 0; 9; 81; 4; 12], can you nd the maximum satisfying value under no assumption and under Assumption 3, respectively?

    (2) (2%) Please give a O(n log(n)) algorithm to nd the maximum satisfying value under Assump-tion 1.

    (3) (2%) Please give a O(n log(n)) algorithm to nd the maximum satisfying value under Assump-tion 2.

    (4) (4%) Please give a O(n) algorithm to nd the maximum satisfying value under both Assump-tion 1 and 3 (If you get full points on this problem, you will automatically gain full points of

(2).)

There are still problems on the next page!















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



W.H.Y., Howard’s another friend, decided to further help him by his rich experience. \How about considering some courses from the college of management? There are more girls and elites!", said W.H.Y.. Howard accepted his advice and also collected information of courses in college of manage-ment. To balance his daily life, he also collected n courses from college of management, which are E1 to En. Same as the rst time, Howard also marked his preference of each course from college of man-agement Ei with a preference value Mi. For easier understanding, there are now total 2n distinct courses from CSIE and college of management, each has n courses, which are C1 to Cn and E1 to En, respectively. For those courses in CSIE, each has a preference value Pi; for those in college of management, each has a preference value Mi. Same as the rst part, you’re also asked to nd the maximum satisfying value he can reach by arranging a desiring order of those courses. In case you forget what is maximum satisfying value, the maximum satisfying value is de ned as the maximum number for that could be formed by concatenating some of the course preference values (in digits) in any order.

However, the time is limited. Howard can only put at most total k courses in his desiring order of courses. Moreover, he performed sorting this time, which preserves the relative order of the courses from the same department. That is, in the desiring order, the courses from CSIE should have the same relative order as C1 to Cn, and the courses from management should have the same relative order as E1 to En. To simplify the problem, the preference of courses is always a single digit number, that is 8 1 i n, fPi; Mig 2 [0; 9].

For example, if n = 3, k = 4, the preference value of courses are Pi = [3; 6; 4], Mi = [8; 5; 7], the maximum satisfying value will be 8764.

    (5) (2%) Assuming n = 5, k = 5, given preference value of courses Pi = [3; 4; 6; 5; 0], Mi = [9; 0; 5; 8; 3], can you nd the maximum satisfying value?

    (6) (8%) Please give a O(kn2) algorithm to  nd the maximum satisfying value given Pi and Mi.


































14