Algorithm Design Homework #3 Solution

Problem 1 - ADA Adventurer (Programming) (11 points)

Problem Description

ADA Road, a prosperous country, was established by the ancestors’ wisdom long time ago. This country consists of N cities indexed from 1 to N and (N 1) roads. Each road connects two di erent cities, and all cities are connected. More formally, for any two di erent cities, a path exists from one to another along the given roads, and the distance between two cities is de ned as the number of roads on this path.

To become a valiant ADA adventurer, you decided to visit this country. After arriving at the ADA Road, you discovered that the distance of some city pairs is too large, so villages need to pay lots of e ort to reach one from another. To help the villages and get the experience points, you would like to help them resolve this problem. The only stu allowed is to rebuild at most one road. That is, you can only remove at most one road from this country, and nd a new pair of cities to build a road between them. The target is to minimize the farthest distance after rebuilding the road. Notice that you should avoid making some pairs of cities disconnected. Can you nd the best way to complete it to win villages’ reliance?

Input

The    rst line only contains one integer N, describing the number of cities in ADA Road.

In the next N 1 lines, each line contains two di erent integers a; b (1 a; b N), describing a road connecting city a and b.

It is guaranteed that there exists a path from one city to another one for any pair of cities.


Test Group 0
(0 %)
Test Group 2 (30 %)
• Sample Input.
• 2
N   1000.
Test Group 1
(20 %)
Test Group 3 (50 %)
•2  N  50.
• 2
N   2  105.

Output

Print one integer in a line, indicating the farthest distance after rebuilding the road.




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



Sample Input 1
Sample Output 1
5

3
5
1

4
1

5
3

2
3

Sample Input 2
Sample Output 2


6

3



6
5

1
3

3
2

4
5

6
3

Sample Input 3
Sample Output 3
10

4
8
3

2
8

7
9

6
5

4
6

9
1

3
10

3
5

2
9
































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



Problem 2 -


P


kingdom (13 points + Bonus 2 points)

Problem Description

P

kingdom, a prosperous country, was established by the wisdom of the ancestors a long time ago.

This country consists of N cities indexed from 1 to N and M directed roads. Each road ei connects two di erent cities ui and vi, indicating that you can visit city vi from city ui.

As a resident in the P kingdom, able to visit all other cities in the P

you nd that there are speci c cities where residents may not be kingdom.

In order to meet everyone’s daily needs, you have to solve this problem by building new directed roads. Now you can propose a list of roads that need to be built and minimize the number of roads on the list.

Input

The rst line contains two integers T , representing the number of test cases, and f lag (f lag 2 f0; 1g), which will be described in the output section.

Each test case consists of two parts: the rst line contains two space-separated integers N; M, representing the number of cities and the number of roads, respectively.

Each line of the following M contains two space-separated integers ui and vi, indicating a road connection from ui to vi.

    • 1   N   1000
• 0    M    min(1000; N    (N    1))
    • 1   ui   N

    • 1   vi   N

    • ui 6= vi

It is guaranteed that the sum of N does not exceed 3000 and the sum of M does not exceed 3000.


Test Group 0
(0 %)
Test Group 2 (30 %)
• Sample Input.
• f lag = 0




Test Group 3 (20 %)


• ui < vi
Test Group 1
(30 %)

• f lag = 0

Test Group 4 (20 %)



• ui < vi

• No additional constraints.





Bonus Group (2 points)

    • N; M   100000

    • The sum of N does not exceed 100000 and the sum of M does not exceed 100000.


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



Output

For each testcase, print an integer on the rst line representing the number of roads K that need to be built.

If the f lag mentioned in the input section is equal to 1, please furthermore print the following K lines: each line contains si and ti, representing building a road from si to ti in the list. If there are multiple ways to match this condition, you can print any of them.


Sample Input 1    Sample Output 1

1 0    2

    • 2

1 2

3 4


Sample Input 2
Sample Output 2
2
1
3

5
2
2
3
1
2
4
5
3
4
5
1
3
3
0


    • 2

2 3

3 1



































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



Problem 3 - I Want It All!!! (Programming) (13 points)

Problem Description

Xiao Feng and Baluteshih are learning graph theory together from Waynetu, a legendary grand-master in graph theory. To make sure that they have good learning e ciency, Waynetu decided to assign homework to them. The homework is described as follow:


Given a weighted connected undirected graph, please    nd a spanning tree of it.

Xiao Feng and Baluteshih are working on this homework together. Xiao Feng loves shortest-path trees, so he would like to nd a shortest path tree starting from vertex 1. However, Baluteshih loves minimum spanning trees, so he would like to nd a minimum spanning tree of the given graph. Please help Xiao Feng and Baluteshih to nd a spanning tree that satis es both of their preferences simultaneously or determine that it is impossible.

Input

The rst line contains two integers N; M, describing the number of the vertices and the edges of the graph. The vertices are indexed from 1 to N.

In the next M lines, the ith line contains three integers ai; bi; ci, describing an undirected edge with index i which connects the vertices ai and bi with weight ci.

It is guaranteed that the input forms a connected graph.


Test Group 0 (0 %)

    • Sample Input.


Test Group 1 (40 %)

    • 1   N   105.
    • 0M3105.
    • 1   ai; bi   N; ai 6= bi.


    • 1   ci   109.

    • All ci are distinct.

Test Group 2 (60 %)

    • 1   N   105.
    • 0M3105.
    • 1   ai; bi   N; ai 6= bi.
    • 1   ci   109.

Output

If Xiao Feng and Baluteshih cannot nd the same spanning tree of the input graph, please print \No" (without quotes) in the rst line.

Otherwise, please print \Yes" (without quotes) in the    rst line. In the second line, please print

    • 1 integers, describing indices of the chosen edges of the spanning tree. If there are multiple choices of the spanning trees, you may print any of them.











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



Sample Input 1
Sample Output 1
5
6

Yes

1
2
1
1 2
3 4
1
3
2


2
5
3


2
4
4


1
5
5


3
4
6




Sample Input 2
Sample Output 2
7
9

Yes



5
7
3
1 2
3 4
5
9
3
2
4




1
4
18




3
4
17




2
5
10




1
5
49




1
3
35




3
5
14




6
5
19






Sample Input 3
Sample Output 3
4
4

No
1
2
3

1
3
5

2
4
3

3
4
1



Sample Input 4
Sample Output 4
4
5

Yes

1
2
2
1 2
4
1
3
2


1
4
4


2
4
2


3
4
2




Hint

    1. You may want to nd \a shortest-path tree that forms a minimum spanning tree" instead of nding \a minimum spanning tree that forms a shortest-path tree".

    2. Test Group 1 can only help you verify the correctness of your shortest-path tree and minimum spanning tree. Try not to regard it as a hint for full credit.





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



Problem 4 - Cats! (Programming) (13 points)

Problem Description

    BB loves cats! There are N cats in his garden, and the cats are labeled from 1 to N. BB’s garden can be seen as a straight line, and the ith cat is initially located at x-coordinate xi.

Every once in a while, BB will place some food somewhere in the garden, which attracts some of the cats nearby. More precisely, there are Q sequential events, the jth of which is of one of the two types:

    • BB placed some food at x-coordinate pj, and attracted all cats within radius rj. That is, every
cat within [pj    rj; pj + rj] moved to pj.

    • The tjth cat moved to x-coordinate x0j

Unfortunately, BB feels like his garden might be a bit too crowded after some of the events. The cats might feel uncomfortable due to this. To try resolving this problem, BB would like to rst know the crowdedness of his garden. He de ne crowdedness be the number of pairs (i; j), i < j, such that the ith cat and the jth cat are at the same location.

Please help BB    nd out the crowdedness after each event.

Input

The rst line of the input contains two positive integers N and Q, denoting the number of cats on BB’s garden and the number of events, respectively.

The second line contains N space-separated integers x1; x2; : : : ; xN , denoting the initial x-coordinate of the cats.

Then Q lines follows. The j-th line of which is of one of the following two forms:

    • 1 pj  rj: BB placed some food at pj with radius rj.

    • 2 tj  x0j: The tjth cat moved to x0j.

Note that the events happen one by one (i.e., the jth event happens under the e ect of all previous
    • 1 events).

        ◦ 1  N;Q  105

        ◦ 0   xi; pj; rj; x0j   109

        ◦ 1   tj   N

Output

Please output Q lines, where the jth line denotes the crowdedness of BB’s garden after the jth event.







8

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




Test Group 0
(0 %)
Test Group 1 (10 %)

•
Sample Input
• N;Q  100

Test Group 2
(20 %)
Test Group 3 (30 %)

•
N; Q  5000
• There are only events of type 1.

Test Group 4 (40 %)

    • No Additional Constraint


Sample Input 1
Sample Output 1
5
6



1
3
1
4
1
5
3
2
3
6


1
1
2
1


3
2
2
7


2
1
3
2


10
2
4
7



1
5
2





Sample Input 2
Sample Output 2
8
5






2
1
1
2
3
5
8
13
21
3
1
10

4




11
1
3
1





11
1
3
2





28
1
8
4






1
12

9







Hint

    1. STL is your good friend:

        ◦ Use std::map or std::set to maintain the cats in ascending order of their x-coordinate.

        ◦ Use std::vector or std::list when you need arbitrary length array.

        ◦ Go to Cpp Reference if you don’t know how to use an STL container or function.

    2. Be careful NOT to use std::endl since it might be very slow. Use 'nn' instead.

    3. Let c be an std::map or std::set. Be careful NOT to use std::lower bound(c.begin(), c.end(), x). Use c.lower bound(x) instead.

    4. You should try to prove the time complexity of your code.

    5. The test data in Test Group 1 might be a lot weaker than other test groups. Passing this test group does not guaranteed your code is bug-free.




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



Problem 5 - Shi-Hei Robots (Hand-Written) (20 points)

Note: In this problem, you don’t have to write pseudocode as long as you clearly explain your method. If there are mistakes in your pseudocode, you will receive an additional penalty. You don’t have to prove the time complexity of your method unless the problem description asks you to do so.

Stanley, Wang Jung Tsan (王榮燦), a famous video game streamer and a previous world champion of an online game, has always been accused of purchasing robots to boost his number of stream viewers. In fact, there are some \robots" watching him streaming | they are so-called \Shi-Hei robots." \Shi-Hei robots (史黑機器人)" is a group of evil villains whose ultimate goal is to defame Stanley by convincing people that Stanley is buying robots. To be convincing, they always comment robot emojis in the chatroom so that they look like real robots. One day, you accidentally discover a secret of \Shi-Hei robots": if a group member sees another group member that he/she knows to spam in the chatroom, he/she will continue commenting robot emojis, and eventually, they will be unstoppable. However, simply banning all of them is not feasible since Stanley is merciful and does not want to ban many people. As a MOD (moderator) of Stanley’s streaming channel, you must decide which member of \Shi-Hei robots" should be banned so that the villain group can be split into as many sub-groups as you can. If you can nd out which member should be banned, you will receive a precious reward from Stanley | \Stanley Smile (王榮燦笑)".

More precisely, we use G(V; E), an undirected graph, to denote the relationship among members of \Shi-Hei robots". The goal is to nd out the single vertex v 2 V whose removal from the graph split the graph into as many di erent connected components as possible.

In the following part of this problem, we will use s(v; G) to denote the number of connected components in the graph G after removing vertex v from G. You may assume that the initial graph G (before removing vertex) is connected, has at least two vertices, and is represented using the adjacency lists. Recall that you can output the neighbors of v in O(deg(v)) time and deg(v) in O(1) time for any vertex v 2 V when using the adjacency-list representation.

Here are the de nitions of some terminologies used in this problem: For a tree T (V; E) with root vertex r, \the ancestors of vertex v" denotes all vertices on the path from r to v, and \the descendants of vertex v" denotes any vertex x such that v is an ancestor of x. Every vertex is both ancestor and descendant of itself. \Child of vertex v" denotes any descendant x of v such that edge (x; v) 2 E.

    (1) (3 points) Let T be a DFS tree of G with root r 2 V . That is, T = (V; ET ), where ET is a subset of E, connecting all vertices in G. Given T , please brie y describe how to nd s(r; T ) in O(1) time complexity and prove the correctness.

    (2) (4 points) Let v be a vertex other than the root r (i.e. v 6= r). Suppose that there is no edge fu; wg 2 E where u; w 6= v, and u is an ancestor of v in T , and w is a descendant of v in T . Please brie y describe how to nd s(v; G) in O(1) time complexity and prove the correctness.

    (3) (5 points) Let DT (w) denotes in tree T , the set of descendants of vertex w 2 V including w itself. Also, for a set S V , let NG(S) denotes in graph G(V; E), the set of \neighbors of vertices in set S", i.e. NG(S) = fy 2 V : 9x 2 S s.t. fx; yg 2 Eg.

De ne upT (w) := miny2NG(DT (w)) depthT (y). That is, upT (w) denotes in tree T , the minimum depth of \any neighbor in G of any descendant of w in T ".

Suppose v is an arbitrary vertex that is not the root in T , with children w1; w2; ; wk. Please show how to compute s(v; G) as a function of k; upT (w1); upT (w2); ; upT (wk), and depth(v). Please prove the correctness of your method as well.

    (4) (8 points) Given G, please design an algorithm that computes s(v; G) for all vertices v 2 V with time complexity O(jV j + jEj). Analyze its time complexity and prove the correctness.

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



Problem 6 - Lost in Pekoland (Hand-Written) (30 points)

Note: In this problem, if you’re asked to provide an algorithm, you should prove both its correctness and its time complexity, and you don’t have to write pseudocode as long as you can clearly explain your method. You can directly use any algorithm taught in class

Pekoland, a place full of hopes and dreams, is an amusement park constructed by "Usada Kensetsu," a construction corporation founded by its CEO, Usada Pekora. The park comprises numerous cele-brated landmarks, including a magni cent Castle, the grand Pekora Gundam, some formidable roller coasters, and a creepy monument of a mysterious gure, Yagoo. With these features, Pekoland has long been an appealing tourist attraction around the continent.

One day, Pekora wants to build some railways so that it can be more convenient to commute between the sites in her park. Suppose that the Pekoland’s layout G looks like a set of sites denoted as V connected by a set of roads denoted as E, each road connects exactly two di erent sites with both of its two endpoints and can be traveled from both directions, every two sites are connected by at most one road, and for any two di erent sites a and b, one is always able to go from a to b by walking through a series of roads in E.

Part I

Pekora decides to transform some of these roads into railways, but she notices that each road
    • has its own width w(e); suppose a path is a series of roads (v0; v1)(v1; v2) : : : (vn 1; vn) where all (vi; vi+1) 2 E; we de ne the width of a path as the minimum width of the roads it consists of. Pekora hopes that after the railway construction, for any pair of sites s and t, one can travel from s to t entirely through railways by some of the widest path between them, that is, if E0 is the subset of roads being

transformed, then at least one of the widest path between s and t on G(V; E) is still included in G0 (V; E0 ), but since they only have limited funds, she hopes jE0 j can be as small as possible. Please help her nd the set E0 that meets her needs.

    (1) (3 points) Give a O(E log V ) algorithm that  nds the maximum spanning tree of G.

    (2) (5 points) Prove that for any pair of sites s and t, the maximum spanning tree of G contains some of their widest path. Conclude that Pekora can nd the required set E0 in O(E log V ) time complexity.

Part II

Months later, Usada Kensetsu became so much richer and transformed all roads into railways. Now every road e has its length d(e), which is a positive real number. To get to any site from her castle as quickly as possible, Pekora wants to nd a shortest path from her castle s (which also belongs to V ) to every other site. Luckily, some of her employees had learned some algorithms and know how to nd the shortest path from s to all the other sites for her. However, she nds out that sometimes when a road gets reconstructed, its length can be lengthened or shortened, and it may in uence the shortest distance of a site from s. She becomes curious that at a moment, which roads have the property that the change of its length would alter the shortest path distance from s to some sites v 2 V ?

We de ne that a road e is upwards critical if increasing d(e) by any positive real number " would increase the shortest path distance from s to at least one site v 2 V; and is downwards critical if decreasing d(e) by any positive real number " would decrease the shortest path distance from s to at least one site v 2 V:


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



    (3) (5 points) Prove that a road (u; v) 2 E is downwards critical if and only if there is a shortest path from s to u or v that ends at (u; v):

    (4) (5 points) Referring to the claim above, make a claim of the if and only if condition of being upwards critical and prove your claim.

    (5) (6 points) Using the above claims, give an O(E log V ) time complexity algorithm that deter-mines all upwards critical roads and all downwards critical roads respectively.

Part III

Since that Pekora is very naughty and likes to prank others, she has set up several traps in her amusement park. As a result, Pekoland is also considered to be a dangerous place to go by many. One day Pekora notices that every site v 2 V is graded by a dangerous value k(v) 0 by travelers. It comes to her that it may be fun to build a new roller coaster that sets o from some v 2 V , traveling through some roads of E then nally ends at the starting point v, and she would like the sum of all the dangerous value of the sites on the cycle to be high.

Thus she asks Moona Hoshinova, the chief technical o cer of her company, to conduct the plan, but since building a roller coaster is tiring and costly, she replies that if the total length of the cycle is too large, she would not be willing to take over the task. After some negotiation, they de ne a cycle v1; v2; : : : ; vn; vn+1 = v1 on G; where all vi 2 V and all (vivi+1) 2 E, as an exciting cycle if it satis es
that
iP
n









i=1 k(vi)

> K







P
n

d(vi; vi+1)



=1










where K is a constant given by Moona, and they meet the consensus that if there is an exciting cycle on G, then Moona would agree to build the roller coaster on this cycle, but if there is not such a cycle, then she would object to the plan. In this problem( and only this problem), we suppose the graph is directed and strongly connected, also, for any u; v 2 V if uv 2 E; then vu 2 E, but it’s possible that d(u; v) 6= d(v; u) since that to travel from two direction of a road may not be as di cult as each other.

    (6) (6 points) Please provide an algorithm running in O(V E) time that nds if there exists an exciting cycle.

Hint: you can try re-weighting the graph.






















12