C24T1 - Linear Cites

Subtask 1

There are teleporters on every position.

Observation

The teleporter at position $P_i$ is only useful for $a \leq P_i \leq b$ or $a \geq P_i \geq b$.
Calculate the number of these pairs for each position with $O(L)$.

Subtask 2

Use BFS to find all pairs of distance $(a, b)$ and check whether it is the minimum time.
Time complexity: $O(N^2)$

Subtask 3

Observation

Apart from the useful pairs on the previous observation, for a teleporter at position $P_i$ and adjacent teleporters $P_{i-1}$ and $P_{i+1}$.
There are useful pairs $P_i-a+P_i-b\leq a-P_{i-1}+b-P_{i+1}$ where $P_{i-1}\leq a, b\leq P_i$.
The same is similar for $P_i$ and $P_{i+1}$.
Binary search to find adjacent pairs of the new teleporter and precompute previous teleporters.
Count the number of these pairs and handle the edge cases carefully.
Time complexity: $O(NlogN)$

Subtask 4

Add all the new teleporters into a std::map or std::set to find adjacent teleporters and remove after each query or handle cases accordingly.
Time complexity: $O(NlogN)$

C24T2 - Paper Perimeter

Subtask 1

Observation

The paper cutting algorithm takes logarithmic time. Let's assume it takes $O(k)$ time.

Check all possible $(H, W)$ and run paper cutting, time complexity: $O(k\times HW)$.

Subtask 2

Precompute subtask 1 for all $(H, W)$ and save optimal answers for every $T_i$.
Time complexity: $O(HW+Q)$

Subtask 3

Check for invalid solutions and check all pairs according the the perimeter.
Time complexity: $O(P_i)$

Subtask 4

Observation

$T_i$ for pair $(H, W)$ is simply $gcd(H, W)$ as it is the euclidean GCD algorithm.
GCD has time complexity of $O(log(min(H, W)))$.

Hence both $H$ and $W$ have to be multiples of $T_i$.
Only check pairs that meet this condition.
Time complexity: $O(Qlog(min(H, W))\times \frac{P_i}{T_i})$

Subtask 5

Case handle the invalid cases and brute force the valid pairs $(H, W)$ greedily with minimum $W-L$.
A maximum of 3 pairs will be exhausted to find a valid solution with greedy solution.
Time complexity: $O(Qlog(min(H, W)))$

C24T3 - Prototype Testing

Simplified task statement

Find the maximum displacement among all pairs $(l, r)$ in the string $S$ for each update.

Subtask 1

Brute force all pairs for each query: $O(N^2Q)$

Subtask 2

Displacement can be calculated via partial sum: $ps[r]-ps[l]$ or $ps[l]-ps[r]$.
Both can be used as we are only looking for the maximum displacement and negative values do not affect the answer.
For each query, brute force all $r$ and greedily pick $l$ that maximizes displacement.
Time complexity: $O(QN)$

Subtask 3

Use two segment trees for both signs of $L$ and $R$, update by maintaining prefix and suffix max and the answer in each node.
Time complexity: $O(QlogN)$

Subtask 4

Use the same idea as subtask 2 and handle for 2D grid by checking maximum for all 4 assignments of $(L,R,U,D)$.
Time complexity: $O(QN)$

Subtask 5

Combine ideas of both subtasks 3 and 4 and maintain 4 segment trees.
Time complexity: $O(QlogN)$

C24T4 - Rigged Tournament

Subtask 1

Check if the assignment is valid in $O(2^N)$.

Subtask 2

Brute force all possible initial pairings and check for validity in $O((2^N)!\times 2^N)$.

Subtask 3

Observation

Consider a contestant who has won $i$ rounds in terms of a graph with edges $(B_{i,0}, B_{i,1})$.
Denote $G_i$ be the tree formed.
Note that $G_i$ is simply the root connected to the roots of $G_j$ where $0\leq j\le i-1$.
Greedily check the minimum required wins of each contestant in the tree and run tree DP.
Make sure to handle invalid cases properly.
Time complexity: $O(2^N\times N)$

Subtask 4

Check for gaps in incomplete trees to fit other trees.
Time complexity: $O(2^N\times N)$