yohandi

A recent graduate with a strong interest in algorithms and data structures.

CSC3100 Data Structures Fall 2023 Assignment Solutions Writeup

December 28, 2023 by Yohandi

In the very recent term, I got an opportunity to become the teaching assistant for the CSC3100 Data Structures course. The below are compilation of solutions writeup made by me for all the assignments. These solutions are from my own insights and perspectives on the problems and are unofficial. PDF version can be found at the bottom of this page.

Assignment 1

Queue Disorder

Written and developed by: Xuanhao Pan

Editorial by: Yohandi

Description

In a queue, people are supposed to stand in ascending order of their heights. However, due to some confusion, the order of the queue gets disrupted. Your task is to determine the number of disorder pairs in the queue.

A disorder pair is defined as a pair of people

KaTeX can only parse string typed expression

(p_{i}, p_{j})

such that

i < j

and

p_{i}

is taller than

p_{j}

in the queue, which means their order is reversed.

For example, consider a queue with 5 people:

KaTeX can only parse string typed expression

[180, 160, 175, 170, 170]

. In this case, there are 6 disorder pairs:

(180, 160), (180, 175), (180, 170), (180, 170), (175, 170)

and

(175, 170)

. Please note that

(170, 170)

is not considered as a disorder pair. Write a program to calculate the number of disorder pairs in a given queue with

N

people.

Constraints

$1 \leq N \leq 1 0^{6}$
$1 \leq p_{i} \leq 1 0^{9}, \forall i \in {1, \dots, N}$

Solution

This problem is a straightforward inversion count problem. We can use merge sort to maintain the number of inversions between pairs. Suppose a range

KaTeX can only parse string typed expression

[L, R)

accounts for the number of inversions of all pairs in the range. This then recurses into sub-ranges

[L, mid)

and

[mid, R)

. Any indices

i

and

j

such that

i \in [L, mid)

and

j \in [mid, R)

can be processed concurrently with the merge procedure for the two half arrays using the sorted property.

Alternatively, we can use a Binary Indexed Tree to count the number of elements within a specific index range. To count only those elements smaller than a certain number, updates can be made following the sequence of the sorted elements. Each element, however, should be mapped into a pair of itself and its index (descendingly) to handle elements with the same value.

Both solutions work in

KaTeX can only parse string typed expression

O (n lo g n)

#include <bits/stdc++.h>
using namespace std;

class BIT {
private:
...

Star Sequence

Written and developed by: Tianci Hou

Editorial by: Yohandi

Description

Renko Usami observes space through a telescope when she notices a fantastic phenomenon – the number of stars in the fields follows a mathematical pattern.

Specifically, let’s denote the number of stars in the

KaTeX can only parse string typed expression

N

-th field by

f_{N}

, then

f_{N}

satisfies the following expression, and

a, b

are given positive integers.

f_{N} = a f_{N - 1} + b f_{N - 2} (N \geq 2)

Now Renko Usami is curious about how many stars in the

KaTeX can only parse string typed expression

n

-th field, but the

n

-th field is too far away to be observed through her cheap astronomical telescope. Since there are so many stars, she only cares about the value of the number of stars modulo

m

. In other words, she want to know

f_{n} mod m

Fortunately, Renko Usami is able to observe the two closest star fields to her, and the numbers of stars in fields are

KaTeX can only parse string typed expression

f_{0}

and

f_{1}

. Unfortunately, she is going to be late again for her appointment with Merry. Can you write a program for her to calculate

f_{n} mod m

Constraints

$1 \leq n \leq 1 0^{18}$
$1 \leq a, b, f_{0}, f_{1} \leq 100$
$1 \leq m \leq 2 \cdot 1 0^{9}$

Solution

To calculate

KaTeX can only parse string typed expression

f_{n} mod m

, we use matrix exponentiation to efficiently compute the required term in the sequence. We can construct a vector consisting of

f_{N}

and

f_{N - 1}

using the following matrix power multiplied by the initial vector, which consists of

f_{1}

and

f_{0}

. The formulation is derived as follows:

(f_{N} f_{N - 1}) = (a 1 b 0) (f_{N - 1} f_{N - 2}) = (a 1 b 0)^{N - 1} (f_{1} f_{0})

The matrix power can be computed using the divide and conquer technique, which works in

KaTeX can only parse string typed expression

O (lo g n)

#include <bits/stdc++.h>
using namespace std;

long long MOD;

...

Assignment 2

Battle Game

Written and developed by: Bingwei Zhang

Editorial by: Yohandi

Description

Imagine a group of

KaTeX can only parse string typed expression

n

players that are located in different floors. The

i

-th player (for each

i

such that

1 \leq i \leq n

, where

i

is an integer) is characterized by the following:

$p_{i}$ , a unique starting floor level
$h_{i}$ , a starting HP (Health Points) value
$d_{i}$ , a direction of movement, either U indicating that the $i$ -th player is going upward or D indicating that the $i$ -th player is going downward

All players move simultaneously at the same speed in their respective directions. When two players meet, they engage in a battle. The player with the lower health is eliminated instantaneously, while the other continue to move in the same direction at the same speed but with a reduced HP by

KaTeX can only parse string typed expression

1

. In a case where two players have identical HP, they are both eliminated simultaneously after the battle.

Your task is to determine the final HP of the surviving players

Constraints

$1 \leq n \leq 1 0^{6}$
$1 \leq p_{i} \leq 1 0^{8}, \forall i \in {1, \dots, n}$
$1 \leq h_{i} \leq 100, \forall i \in {1, \dots, n}$
$d_{i} \in {$ U, D $}, \forall i \in {1, \dots, n}$

Solution

Note that downward-moving players survive only if they win every battle with all players below them that are moving upward. Moreover, there won't be any fight between players that are moving in the same direction.

To solve this, we first sort the players by their starting floor. We then simulate from the lowest floor. If a player is moving up, we add them to a stack. Otherwise, this player battles against every player in the current state of the stack, starting from the one on top.

#include <algorithm>
#include <cassert>
#include <iostream>
#include <stack>
#include <vector>
...

Personal comment: the overall solution works in

KaTeX can only parse string typed expression

O (n lo g n)

; however, the constant itself was made strict as stack, the main solution, works in

O (n)

. The sorting algorithm dominates the runtime of the overall algorithm. The constraint of

p_{i}, \forall i \in {1, \dots, n}

should have been lower than or equal to

1 0^{6}

instead of

1 0^{8}

so that we can use the counting sort algorithm, which can be well-applied in

O (n)

Buried Treasure

Written and developed by: Yohandi

Editorial by: Yohandi

Description

Jack Sparrow, the legendary pirate of the Seven Seas, sets sail to an inhabited island in search of a buried treasure. Guided by his map, he believes the treasure lies within a weird-looking trench. The trench stretches across a width of

KaTeX can only parse string typed expression

n

. For any given point from

i - 1

i

on the trench’s

x

-coordinate, the depth is represented by

d_{i}

(for each

i

such that

1 \leq i \leq n

, where

i

is an integer).

Jack is wondering about the size of the largest treasure that could possibly fit inside the trench. Wanting to maximize his haul, he turns to you, a trusted member of his crew, to make the calculations. By largest, Jack means the maximum area – the product of width and height – of the rectangular treasure chest that can be buried within the trench’s confines. For example, the following figure shows the largest possible treasure that can fit in a trench with

KaTeX can only parse string typed expression

n = 8

and

d = [6, 2, 5, 4, 5, 1, 4, 4]

Figure 1

Could you give these calculations a look for our legendary pirate?

Constraints

$1 \leq T \leq 10$
$1 \leq n \leq 1 0^{6}$
$1 \leq d_{i} \leq 1 0^{6}, \forall i \in {1, \dots, n}$
The sum of $n$ over all queries, denoted as $N$ , does not exceed $1 0^{6}$ in each test case.

Solution

This problem is a classic "Maximum Rectangle Area in Histogram" problem with a rephrased and modified statement. However, the proof of optimal chest rotation angles is only between

KaTeX can only parse string typed expression

0^{\circ}, 9 0^{\circ}, 18 0^{\circ}, 27 0^{\circ}

is still needed to correctly solve this problem.

The approach is to have a stack that maintains the indices of depths in ascending order so that we can identify the potential of extension (starting points) for rectangles. Each of those rectangles is computed as

KaTeX can only parse string typed expression

A_{i} = d_{i} \times (r_{i} - l_{i} + 1)

, where

r_{i}

is the rightmost index to which the rectangle containing the

i

-th index can extend (same goes for

l_{i}

but on the other direction). The main task is to find

max_{i} A_{i}

#include <bits/stdc++.h>
using namespace std;

long long largest_chest(int n, vector<int> &v) {
  long long ret = 0;
...

Assignment 3

Node Distance

Written and developed by: Yige Jiang

Editorial by: Yohandi

Description

You are given a tree with

KaTeX can only parse string typed expression

n

nodes, where each edge in the tree has a corresponding weight denoting the length of each edge. The nodes in the tree are colored either black or white. Your task is to calculate the sum of distances between every pair of black nodes in the tree. Let

B = {b_{1}, b_{2}, \dots}

a set of black nodes, then the answer is formulated as:

i = 1 \sum ∣ B ∣ - 1 j = i + 1 \sum ∣ B ∣ dist (b_{i}, b_{j})

where

KaTeX can only parse string typed expression

∣ B ∣

denotes the number of the black nodes in the tree, and

dist (b_{i}, b_{j})

is the length of the simple path from the

i

-th to

j

-th black node.

Write a program to calculate the formulation above.

Constraints

$1 \leq n \leq 1 0^{5}$
$c_{i} \in {0, 1}, \forall i \in {1, \dots, n}$
$1 \leq q_{p - 1} < p, \forall p \in {1, \dots, n - 1}$
$1 \leq w_{p} \leq 1000, \forall p \in {1, \dots, n - 1}$

Solution

Suppose we focus on the contribution of each edge to the total distance. An edge connecting nodes

KaTeX can only parse string typed expression

u

and

v

, when removed, splits the tree into two subtrees, say they are

T_{1}

and

T_{2}

. The key insight here is that this edge contributes to the total distance exactly the product of the number of black nodes in

T_{1}

and the number of black nodes in

T_{2}

The implementation is done by performing a DFS from any fixed root. During DFS, we count the number of black nodes in each subtree. For a subtree rooted at

KaTeX can only parse string typed expression

u

, the count of black nodes in

T_{1}

is the number of black nodes within this subtree. The count for

T_{2}

is determined by subtracting the count of black nodes in

T_{1}

from the total number of black nodes in the tree.

#include <bits/stdc++.h>
using namespace std;

int main() {
  ios_base::sync_with_stdio(0);
...

Price Sequence

Written and developed by: Ruiying Liu

Editorial by: Yohandi

Description

Mario bought

KaTeX can only parse string typed expression

n

math books and he recorded their prices. The prices are all integers, and the price sequence is

a = {a_{0}, a_{1}, ..., a_{i}, ..., a_{n - 1}}

of length

n

. Please help him to manage this price sequence. There are three types of operations:

BUY x: buy a new book with price $x$ , thus $x$ is added at the end of $a$ .
CLOSEST_ADJ_PRICE: output the minimum absolute difference between adjacent prices.
CLOSEST_PRICE: output the absolute difference between the two closest prices in the entire sequence.

A total of

KaTeX can only parse string typed expression

m

operations are performed. Each operation is one of the three mentioned types. You need to write a program to perform given operations. For operations CLOSEST_ADJ_PRICE and CLOSEST_PRICE you need to output the corresponding answers.

Constraints

$2 \leq n, m \leq 100000$
$0 \leq a_{i} \leq 1 0^{12}, \forall i \in {0, \dots, n - 1}$
$0 \leq x \leq 1 0^{12}$

Solution

Both the CLOSEST_ADJ_PRICE and CLOSEST_PRICE operations are independent to each other; hence, for each update, i.e., the BUY x operation, we can perform a separate update on two different data structures.

For the CLOSEST_ADJ_PRICE operation, we maintain two variables: the price of the last book bought and the minimum absolute difference between adjacent prices. When a BUY x operation occurs, update the last book's price to x and, if necessary, update the minimum absolute difference using the absolute difference between x and the previously last book's price.
For the CLOSEST_PRICE operation, we use a balanced binary search tree to avoid the linear time complexity in the insertion worst case. Upon inserting a new price x, we compare it with its immediate predecessor and successor in the tree to update the minimum absolute difference between any two prices in the sequence.

#include <bits/stdc++.h>
using namespace std;

int main() {
  ios_base::sync_with_stdio(0);
...

Assignment 4

Divine Ingenuity

Written and developed by: Shu Wang

Editorial by: Yohandi

Description

If you have ever played Genshin Impact, you probably know about the “Divine Ingenuity: Collector’s Chapter” event. In this event, players can create custom domains by arranging components, including props and traps, between the given starting point and exit point.

Paimon does not want to design a difficult domain; she pursues the ultimate “automatic map”. In the given domain with a size of

KaTeX can only parse string typed expression

m \times n

, she only placed Airflow and Spikes. Specifically, Spikes will eliminate the player (represented by x), while the Airflow will blow the player to the next position according to the wind direction (up, left, down, right represented by w, a, s, d, respectively).

The starting point and exit point are denoted by i and j, respectively. Ideally, in Paimon’s domain, the player selects a direction and advances one position initially; afterward, the Airflow propels the player to the endpoint without falling into the Spikes. The player will achieve automatic clearance in such a domain.

However, Paimon, in her slight oversight, failed to create a domain that allows players to achieve automatic clearance. Please assist Paimon by making the minimum adjustments to her design to achieve automatic clearance.

Given that the positions of the starting point and exit point are fixed, you can only adjust components at other locations. You have the option to remove existing component at any position; then, place a new direction of Airflow, or position a Spikes.

Constraints

$3 \leq m, n \leq 2000$

Solution

This problem can be modeled as a graph problem, where:

For nodes corresponding to Airflow, an edge is created to the node in the direction of the Airflow with weight 0, as no adjustment is needed. For nodes in directions other than the Airflow, edges are created to the adjacent nodes in their respective directions with weight 1, indicating that one adjustment (changing the direction of the Airflow) is required.
For Spikes nodes are connected to all adjacent nodes with weight 1, as a Spike can be replaced with an Airflow in any direction with one adjustment.

We run Dijkstra's algorithm to find the shortest path from a node with the character i to a node with the character j.

#include "dijkstra.hpp"
#include <bits/stdc++.h>
using namespace std;

int main() {
...

Edge Changing

Written and developed by: Ziyi Zhao

Editorial by: Yohandi

Description

Give you a graph with

KaTeX can only parse string typed expression

n

vertices and

m

edges. No two edges connect the same two vertices. For vertex ID from

1

n

, we do the following operation: If any two neighbors of a vertex have a

k \times

relationship in terms of their IDs, we add a new edge between them. In other words, for any vertex

i = 1

n

, if

u = k v

v = k u

, we add an edge

(u, v)

, where

u, v \in Neighbor (i)

. Besides, if there is already an edge between

u

and

v

, no operation is taken.

After the operation, we want you to output the BFS order starting from vertex

KaTeX can only parse string typed expression

s

. Please traverse all neighbors in ascending order of their IDs when expanding a vertex.

Constraints

$1 \leq n, m, \leq 1 0^{5}$
$2 \leq k \leq 1 0^{5}$

Solution

This problem is a straightforward BFS implementation problem with few modifications on the main graph. However, the inserted nodes need to be handled carefully as the problem requires the traversal in ascending order. One of the ways to handle this is to use a balanced binary search tree.

#include <bits/stdc++.h>
using namespace std;

int main() {
  ios_base::sync_with_stdio(0);
...

PDF version

← Natural Parallelism: Scalable Techniques in Distributed and Parallel Sorting Algorithms Natural Parallelism: Advancing Machine Learning with OpenACC →