2023 KSA Automata Summer Contest

## Solution

Since $k$ is given up to eight decimal places, $10^9 \times k$ must be an integer. Therefore, $k$ can be represented as $k = \cfrac{10^9 \times k}{10^9}$.

## Solution

The problem is to count the distinct angles formed between the line segment connecting the points $(0, 0)$ and $(X_i, Y_i)$ with the $x$-axis.

There are various methods to represent the angle, such as slope, trigonometric functions, etc. However, when using floating points, you need to take care of an error. For example, when storing the slope, if you are using the C language, you should use `double` instead of `float`. Also, ensure that the representation of the angle accurately captures all the points $(X_i, Y_i)$ on every quadrant and the axes.

Using data structures like sets, the solution can be found in $\mathcal O (N \log N)$ time complexity.



## Subtask 1

Since $M = 1$, you can sort the $N$ characters and concatenate the first $K$ characters to get the answer.

## Subtask 2

All the strings are identical, so regardless of which $K$ strings you choose, the answer will be the same. Concatenate the chosen $K$ strings and sort them.

## Subtask 3

The problem can be solved with a greedy approach. First, sort the characters in each string. For example, `ACBA` becomes `AABC`. Then, sort the strings $S_1, S_2, \cdots, S_N$ in lexicographical order and concatenate the first $K$ strings. Finally, sort the characters in the resulting string, and this will give you the desired string $T$ as required by the problem.

## Solution 1

Define $S_i$ as the sum of scores from the 1st to the $i$th target, and define $R_i$ as the answer to the problem when considering only the targets from the 1st to the $i$th.

- $R_1 = \max(0, S_1)$. If $S_1 < 0$, it is better to forfeit. Otherwise, hitting the 1st target is better.
- $R_i = \max(R_{i-1}, S_i - R_{i-1})$. If you hit the $i$th target, you obtain its score but must give $R_{i-1}$ points to the opponent. If you hit the targets above $i$th target or forfeit, you give those points to the opponent but can secure $R_{i-1}$ points for yourself.

With this method, the solution can be found in $\mathcal O(N)$ time.

## Solution 2

You can also optimize the $\mathcal O(N^2)$ dynamic programming approach using data structures like segment trees to find the solution in $\mathcal O(N \log N)$ time.


## Solution

We can maximize the sum of levels with all intervals having a length of at most $4$.

### Proof

First, among the ways to partition the given array to maximize the sum of levels, choose any method. For intervals generated with a length of $5$ or more, they can be split into intervals with a length of at most $4$.
- If the length of the interval is $5$, it can be split into one of the following: $(1, 4)$, $(2, 3)$, or $(3, 2)$.
- If the length of the interval is $6$, it can be split into one of the following: $(2, 4)$, $(1, 2, 3)$, or $(3, 2, 1)$.
- If the length of the interval is $7$ or more, by taking intervals of length $1$ or $2$ from the left until the length becomes $5$ or $6$, we can split as mentioned above.

$P + Q \ge P \oplus Q$ always holds, so the partition made with the above method also becomes the answer to the problem. $\square$



Once you have found this fact, you can solve the problem with the following DP definition:

- $dp[i][j]$ = the maximum sum of levels when dividing up to the $i$th index, with the last interval having a length of $j$.

The time complexity is $\mathcal O(16N)$.

## Solution

First, we need to know the fact that when you swap any two positions in a permutation, the parity of inversions changes.

Define $A_k, A_{k-1}, \cdots, A_1$ as $L$ and $A_{k+1}, A_{k+2}, \cdots, A_N$ as $R$. Without loss of generality, let's assume that $1$ is in $L$. The total number of inversions will be defined as the sum of the inversions in $L$ and $R$.

### Case where $A_k=1$

$L$ and $R$ are independent. This means a number from $L$ cannot move to $R$ and vice versa. Thus, regardless of the game rules, if the total inversions are odd, Minchan wins, and if they are even, Junee wins.

### When $A_k \neq 1$ and the total number of inversions is odd

Minchan can swap the position containing $1$ with position $k$ to make $L$ and $R$ independent, and hence he can win.

### When $A_k \neq 1$ and the total number of inversions is even

Both Minchan and Junee should ensure that the parity of the total inversions does not change. If the parity changes, the opponent can move $1$ to the $K$th index on their next turn and win. To maintain parity, one needs to swap position $K$ with some positions in $R$. If we let this position $x$, then the parity of $A_K$ and $A_x$ should differ. This is because for all positions $i$ such that $A_x < A_i < A_K$, each of them changes the total number of inversions by $+1$ or $-1$.

Thus, with each swap, the parity of $A_K$ changes, and eventually, one will swap with the smallest number in $R$. If the original parity of $A_K$ and the smallest number in $R$ differ, Minchan wins; if they are the same, Jun wins. However, there's an exception: if the smallest number in $R$ is larger than $A_K$, Jun always wins.

To compute the inversions, if you use data structures like Fenwick tree or segment tree, you can solve the problem with time complexity of $\mathcal O(N\log N)$.

## Subtask 2

You can try all $\binom{N}{K}$ possible ways of taking books.

## Subtask 3

Since $T_i = 0$, you only need to consider $W_i$ and $V_i$. Firstly, sort the books in ascending order based on $V_i$.

Assuming that you take the $x$-th book and choose the remaining $K-1$ from the books numbered $1, 2, \cdots, x - 1$, the maximum value of $V_i$ is fixed at $V_x$. Loop in the order $x = 1, 2, \cdots, N$ and keep adding books to a priority queue while ensuring the size of the priority queue always remains $K - 1$. This will allow you to determine the minimum sum of the $W_i$s. In this case, the priority queue should ensure that the book with the biggest $W_i$ is at the top.

The time complexity is $\mathcal O(N \log N)$.

## Subtask 4

After sorting the books in descending order based on $T_i$, you can apply the solution from **Subtask 3**. Assuming that you take the $x$th book and choose the remaining $K-1$ from the books numbered $1, 2, \cdots, x - 1$, the minimum value of $T_i$ gets fixed at $T_x$.

The time complexity is $\mathcal O(N^2 \log N)$.

## Subtask 5

Just like in **Subtask 3**, after sorting the books in ascending order based on $V_i$, increase $x$ by $1$ and calculate the minimum tiredness.

Excluding the one book fixed at the position $x$, out of the remaining $K-1$ books, $K-2$ books are chosen in ascending order of their $W_i$. Let's call the minimum $T$ value among these selected $K-1$ books as $T_{min}$. Now, for selecting another book $y$, we can split it into two cases:

- If $T_y < T_{min}$, the answer increases by $W_y + T_y - T_{min}$.
- If $T_y \geq T_{min}$, the answer increases only by $W_y$.

Therefore, as $x$ increases, update the minimum values of $W_y + T_y$ and $W_y$. You can manage $T_{min}$ using data structures like disjoint sets or segment trees, which allows the time complexity of $\mathcal O(N \log N)$.

## Solution

Consider the theme park as a tree with a vertex $1$ as its root. Moreover, hosting an event on the path connecting zone $i$ and its parent will be defined as selecting zone $i$. When observing from the deepest vertex sequentially, the following algorithm can be devised:

- If zone $i$ operates with an entrance fee, then select zone $i$.
- If zone $i$ operates for free, decide whether to select zone $i$ or not.

If we decide to select zone $i$, it is possible to cancel a few of the previously selected zones. If there is an ancestor-descendant relationship pair among the canceled zones, the number of times one collects tickets on the path to a particular zone decreases. Thus, such pairs shouldn't exist. Hence, it's necessary to know the set with the largest cost sum among the sets without any parent-child relationship pairs.

Let's define the set with the largest cost sum that can be formed using currently selected zones that meet the above condition as $S_{i,0}$. Additionally, $S_{i,1}$ is defined as the set with the largest cost sum that can be formed from the currently selected zones not included in $S_{i,0}$. Similarly, $S_{i,j}$ is defined as the set with the largest cost sum that can be made from the currently selected zones that aren't included in $S_{i,0} \cup S_{i,1} \cup \cdots \cup S_{i,j-1}$. For two vertices $u$ and $v$ that aren't in an ancestor-descendant relationship if we combine $S_u$ and $S_v$ to create a new $S_w$, then we know that $S_{w,i} = S_{u,i} \cup S_{v,i}$.

By moving up from the deeper zones and naïvely merging $S$ as described above, **Subtask 3** can be solved in $\mathcal O(N^2)$. If $S$ is managed using a set or a priority queue and employs the technique of merging from a smaller set to a larger set during the merging process, **Subtask 4** can be solved in $\mathcal O(N \log^2N)$.



## Subtask 1

We'll define the KSA as a tree and the building where Eric is hiding as the solution vertex. As every vertex has $1$ as its parent, the answer is exceptionally $1$ only when $N=2$ and in all other cases, it is always $N-2$.

## Subtask 2

From here, we need to use Dynamic Programming.

Assume first that we input $x$ into the remote and receive an answer $d$. Initially, set the root of the tree to $x$. As a result, the depth of all candidate vertices for the answer becomes $d$. Therefore, each time you ask a question, you can know the Lowest Common Ancestor (LCA) between the queried vertex and the solution vertex.

Let $dp[i]$ be the minimum number of questions to find the solution vertex, given that the solution vertex belongs to the subtree of vertex $i$.

- When $depth[i] = d$, $dp[i] = 0$.
- When $depth[i] < d$, it's optimal to try the children of vertex $i$ in descending order of their DP values.

Therefore, if $X$ is sorted array of the DP values of the children of vertex $i$ in descending order, then $dp[i] = \min_{1\leq i \leq |X|}(X[i] + i - 1)$. Let $ans[i][j]$ be $dp[i]$ when solving the above DP with $x=i$ and $d=j$. The answer is $\min_{1 \leq i \leq N}\left(\max_{0 \leq j < N}ans[i][j]\right) + 1$, and the time complexity is $\mathcal O(N^3 \log N)$.

## Subtask 3

Here, further optimization is required. When calculating the $ans[i][j]$ values, subtrees used in the DP process overlap. Each subtree corresponds to a directed edge, so the total number of subtrees is $2N - 2$. After assigning numbers from $1$ to $2N - 2$ to each subtree, let's define the DP as follows:

- $dp[i][j]$ = the minimum number of questions to find the solution vertex, given that the solution vertex belongs to subtree $i$ and the distance between the solution vertex and the root of subtree $i$ is $j$.

If the height of subtree $i$ is $H[i]$, then the range of $j$ in $dp[i][j]$ is from $0$ to $H[i]$. Let's compute from $dp[i][0]$ to $dp[i][H[i]]$ collectively. Here, the values you need to get are the DP values of the children of the root of subtree $i$.

At this point, since the sum of the heights of the children is less than or equal to $N$, we know that the received values won't exceed $N$. Therefore, the time complexity of calculating $dp[i][0], dp[i][1], \cdots, dp[i][H[i]]$ is $\mathcal O(N \log N)$. Doing this for all $i$ allows you to solve the problem in $\mathcal O(N^2 \log N)$.

## Solution

Let's consider the marathon course as a graph. The student numbered $j$ must cross the edges $j-1$ times. Let's define the shortest edge weight connected to vertex $i$ as $S_i$. For every $i$, consider the following path:

- Start from vertex $1$ and arrive at vertex $i$ $\rightarrow$ From vertex $i$, repeat the shortest edge multiple times $\rightarrow$ start from vertex $i$ and arrive at vertex $N$.

For convenience, we'll refer to the path from vertex $1$ to vertex $i$ as path $A$, the path repeating the shortest edge from vertex $i$ as path $B$, and the path from vertex $i$ to vertex $N$ as path $C$. Every time the number of edges in path $A$ or path $C$ increases by one, the number of edges in path $B$ will decrease by one.

So, to determine the answer for a student numbered $j$, set all edge weights to (original weight) - $S_i$ and compute the shortest distance for paths $A$ and $C$ using methods like Dijkstra. Then, add $S_i \times (j-1)$ to find the solution. Keep in mind the following three considerations:

1. If the original weight of an edge is less than $S_i$, the weight becomes negative, and it shouldn't be passed. Passing a smaller weight edge is always more beneficial than reciprocating from vertex $i$.
2. The number of edges in path $B$ is always even, so if the parities of (the number of edges in path $A$ + the number of edges in path $C$) and $j-1$ are different, the solution for student $j$ cannot be found. Therefore, calculate the shortest distances for the cases where the number of edges in paths $A$ and $C$ are even or odd. If $j-1$ is odd, the answer is $\min(A_{odd} + C_{even}, A_{even} + C_{odd}) + S_i \times (j-1)$; if even, it's $\min(A_{even} + C_{even}, A_{odd} + C_{odd}) + S_i \times (j-1)$.
3. If the sum of edges in paths $A$ and $C$ exceeds $j$, the number of repeats in path $B$ becomes negative, giving an incorrect value.



Define $j-1$ as variable $x$ and the answer as $y$. For each $i$, two lines are formed based on the value of $x$:

- If $x$ is odd: $y = S_ix + \min(A_{even} + C_{even}, A_{odd} + C_{odd})$
- If $x$ is even: $y = S_ix + \min(A_{odd} + C_{even}, A_{even} + C_{odd})$

Therefore, create 2 line containers based on the parity of $x$ and insert the line created from each $i$. This allows you to apply Convex Hull Trick (CHT) for $x$. Finally, answers for $j < 2N$ are computed separately during preprocessing, and answers for $2N \leq j \leq K$ can be found using CHT.

By finding answers for all $j$ using CHT, you can solve **Subtask 2**. For **Subtask 4**, find the intersection points of the lines and use the cumulative sum formula. The total time complexity is $\mathcal O(NM \log N)$. Additionally, there exists a $\mathcal O(NM)$ solution without using Dijkstra.
