T251 - Total Legs

Output $2 \times c + 4 \times r + 8 \times s$.

T252 - Attendance Check

Sort the array of integers. If it is a permutation, the sorted array should be equal to $[1, 2, ..., N]$. Alternatively, you can just use the function std::is_permutation.

T253 - Street Fighter

Subtask 1

After beating opponent $i$, check whether Ryu can beat opponent $i+1$ by looping through all defeated opponents $0$ to $i$ for a similar fighting style. Complexity: $O(N^2)$.

Full Solution

Notice that maintaining the minimum and maximum fighting style of defeated opponents $0$ to $i$ is sufficient to check whether there is a similar fighting style to opponent $i+1$.
This is because all fighting styles between the minimum and maximum must be similar to a defeated opponent's fighting style. (Can you tell why?)
Hence we can solve the problem in $O(N)$.

T254 - Extrovert Seating

Without loss of generality, assume $b \le g$. Notice that if $(b + 1)(k - 1) < g$, it is impossible to construct a valid string. Otherwise, we can always construct a valid string in the following way:

$$ \underbrace{\text{GGG} \dots \text{GG}}_{q + (0 < r) \text{ times}}\text{B} \underbrace{\text{GGG} \dots \text{GG}}_{q + (1 < r) \text{ times}}\text{B} \dots \underbrace{\text{GGG} \dots \text{GG}}_{q + (b - 1 < r)\text{ times}}\text{B} \underbrace{\text{GGG} \dots \text{GG}}_{q + (b < r) \text{ times}} $$ where $q = \left\lfloor \frac{g}{b + 1} \right\rfloor, r = g - (b + 1)q$.

T255 - JSOI

Subtask 1

Output Yes if $A_{1,1} < B_{1,1}$, else output No.

Subtask 2

Since cl_lmc can only solve $N$ tasks, all of them must lie on the same line in order to win, so there are only $2(N + 1)$ sets of tasks we need to check. For each strategy, we need to check whether HarryBOB can interrupt cl_lmc by:

• Solving one of the tasks before cl_lmc, or
• Making a line before cl_lmc

Hard code and brute force all $2! \times 2(2 + 1) = 12$ strategies.

Subtask 3

Suppose the $N$ tasks to be solved are $[(A_1, B_1), (A_2, B_2), \dots, (A_N, B_N)]$ where $A_i$ and $B_i$ is the time required for cl_lmc and HarryBOB to solve, and we are going to solve them in order. Then cl_lmc can solve all of them without interrupted if and only if: $$ \sum_{j=1}^{i} A_j < B_i \text{ for all } 1 \le i \le N $$ To check whether HarryBOB can form another line before cl_lmc, we can just precompute the minimum of the sum of $B_{i,j}$ that forms a line. Brute force all $N! \times 2(N + 1)$ strategy, each should take about $O(N)$ to check whether it works.
Time complexity: $O(N! \times N^2)$

Full Solution

Observation

cl_lmc should always solve tasks in non-decreasing $B_i$ order.
Proof: Suppose cl_lmc can solve all of $[(A_1, B_1), (A_2, B_2), \dots, (A_N, B_N)]$ with $B_k > B_{k+1}$ for some $k$.
Then, we must have $$ \sum_{j=1}^{k} A_j < B_k \text{ and } \sum_{j=1}^{k+1} A_j < B_{k+1} $$ However, this also means that $$ \sum_{j=1}^{k-1} A_j + A_{k+1} < \sum_{j=1}^{k+1} A_j < B_{k+1} \text{ and } \sum_{j=1}^{k+1} A_j < B_{k+1} < B_k $$ This means that swapping $(A_k, B_k)$ and $(A_{k+1}, B_{k+1})$ is always not worse than not swapping if $B_k > B_{k+1}$. Thus, we should always keep swapping until $B_i$ is in non-decreasing order.

This gives us a way to check whether cl_lmc can solve all the tasks on a line without interrupted in $O(N \log N)$ time. Therefore, for each line, we can check whether cl_lmc can solve all tasks on it and form a line faster than HarryBOB. Subtask 4 is for people who forget to compute the minimum sum. Subtask 5 is for people who fail to notice that when $N$ is even, the two diagonals do not intersect, so the minimum sum has to consider that.
Time complexity: $O(N^2 \log N)$

T256 - Notes Unscrambling

Subtask 1

Exhaust all $2^N$ possible combinations of $A$ and naively compute $B$ and $C$ in $O(N^2)$ to check for validity.
Time complexity: $O(N^2 \times 2^N)$

Subtask 2

Let $S$ be the number of $1$s in $A$.
Notice that when

• $A_i=0$: $\ (B_i,C_i)=(0, S)$
• $A_i=1$: $\ (B_i,C_i)=(S,N)$

Hence, if $B_i=0$ we can know that $A_i=0$, otherwise $A_i=1$. Consider $S=0$ where $A_i\ne 0$, so the previous method is guaranteed to be correct.
If $S\ne 0$, we can find $S$ by taking $B_i$ where $A_i=1$, then check whether $B$ and $C$ are consistent with $A$, otherwise output -1.
Time complexity: $O(N)$

Key Observation:

$(A \space \land \space B) +(A \space \lor \space B)=A+B$. Why? Consider a single bit first.

Case 1: $A=1, B=1$

$(1 \space \land \space 1) + (1 \space \lor \space 1)=2$

Case 2: $A=1, B=0 \space / \space A=0, B=1$

$(1 \space \land \space 0) +(1 \space \lor \space 0)=1$

Case 3: $A=0, B=0$

$(0 \space \land \space 0) +(0 \space \lor \space 0)=0$
So $(A \space \land \space B) +(A \space \lor \space B)=A+B$ holds for a single bit. Since an integer is a collection of independent bits, we can generalise: $(A \space \land \space B) +(A \space \lor \space B)=A+B$, holds for all non-negative integers $A, B$.

Subtask 3

Notice that: $$B_i+C_i=N \times A_i + (A_1+A_2+A_3+...+A_N)=N\times A_i + \sum_{i=1}^{N} A_i$$ Denote $D_i=B_i+C_i$, we have: $$\sum_{i=1}^{N} D_i=N \times A_1+N \times A_2 + N \times A_3+...+N \times A_N+N \times \left(\sum_{i=1}^{N} A_i\right)=2 \times N \times \left(\sum_{i=1}^{N} A_i\right)$$
Rearranging terms, we have $\sum_{i=1}^{N} A_i= \frac{\sum_{i=1}^{N} D_i}{2N}$ and $A_i=\frac{D_i-\sum_{i=1}^{N} A_i}{N}=\frac{2N \times D_i-\sum_{i=1}^{N} D_i}{2N^2}$, thus we can compute $A_i$.
Time complexity: $O(N)$

Subtask 4

As $A$ is no longer guaranteed to be valid, we need to validate the answer by computing $B$ and $C$. Naively check the answer in $O(N^2)$.
Time complexity: $O(N^2)$

Full solution

Compute $A$ through the method in Subtask 3, we may notice that each bit of a number can be handled independently.
Therefore we can combine the solution of Subtask 2 and Subtask 3: handle each bit separately and update $B$ and $C$ accordingly, and check if the computed arrays match the input.
Time complexity: $O(N \times \log (\max A_i))$

T257 - Magical Shuffle II

Subtask 1

The cards is already sorted at the beginning, so just output 0.

Subtask 2

Hardcode all 6 different cases.

Subtask 3

Notice that the optimal solution should not exceed 10. Use DFS to simulate every possible move.

Subtask 4

By pigeonhole principle, the condition implies that $A$ and $B$ are permutations of $[1, 2,\dots, N]$.
Hence, if you arbitrarily select a stack $i_0$ and move $A_{i_0}$ to the empty stack, there must exist some $A_{i_1}=B_{i_0}$ to complete card number $A_{i_1}$, then there must exist some $B_{i_2}=A_{i_1}\dots$, until there exists some $B_{i_k}=A_{i_0}$ to complete card number $A_{i_0}$ and now after doing $k+1$ moves there is a vacant stack to repeat the process.
Note that we must exclude the trivial stacks $A_i=B_i$ that are already completed.

Graph Modelling

In fact, we can transform this problem into a graph problem by constructing edges $A_i \rightarrow B_i$.
We can observe that each set of cards where we implement the method described in Subtask 4 is actually a simple directed cycle, and hence the total number of moves in Subtask 4 is $N+\text{no. of simple cycles}$.
If the cards are not arranged like in Subtask 4, each card may either have: $2$ inward/outward edges, or $1$ inward and outward edge, and it is not difficult to notice that the number of cards with $2$ inward edges is equal to the number of cards with $2$ outward edges.

Subtask 5

The condition is equivalent to Card $1$ having two outward edges, and it should be obvious that there will be exactly one card $T$ that has two inward edges.
First we may implement the solution from Subtask 4 to complete all simple cycles first.
Then, let us move both of cards $1$ to the empty stack, then we may run a dfs from card 1 until we reach card $T$ on both directions.
Note that traversing an edge $a\rightarrow b$ in the dfs is equivalent to moving a card $b$ on the top of some stack to another card $b$ which is on the bottom of another stack which $a$ once occupied the top of said stack.
Notice that once we simulate all the card moves, we are left with all cards except $T$ being completed, and two stacks each with only one card $T$, which then may be completed with one more move.
Notice that in the connected component with card $1$, we only use $k+1$ moves where $k$ is the number of cards in the connected component.

Full Solution

We propose an algorithm to reduce a connected component with $k$ cards with two inward/outward edges to one with only $k-1$ cards with two inward/outward edges.
Take a card $a$ with two outward edges (let us denote them by $a\rightarrow \text{left}(a)$ and $a\rightarrow \text{right}(a)$) and complete it, then we traverse only in one outward direction towards $\text{right}(a)$ from $a$ until we reach a card $b$ with two inward edges, then we may move the card once below $b$ and place it above $\text{left}(a)$.
Note that this perfectly removes a pair of card with two inward/outward edges, and completes $k$ cards in $k+2$ moves. We can repeatedly apply this algorithm until we reach the base case where we use Subtask 5's solution.
Combining solutions from Subtasks 4, 5 and our newly proposed reduction algorithm, we are able to solve the problem.
Note that the number of moves is: $$ \begin{align*} &N + \text{no. of simple cycles} + \text{no. of cards with two inward/outward edges } - \\ &\text{no. of connected components that are not simple cycles} \end{align*} $$

Some extra reading

T258 - A Taste of Royalty

Observation 1

Consider two adjacent settlements $x$ and $y$, note that all tours $(U_i, V_i)$ may have a tour sequence like: $U_i \rightarrow \dots \rightarrow x \rightarrow y \rightarrow \dots \rightarrow x \rightarrow y \rightarrow \dots \rightarrow V_i$.
By repeatedly travelling to $x$ and $y$ a finite number of times, you can guarantee that the final median $\geq \min(S_x, S_y)$. Hence the lower bound of the answer is $\min(S_x, S_y)$ for all adjacent settlements $x$ and $y$.

Subtask 1

Using the above observation and the property of $S_{par_i}\leq S_i$, the lower bound of the answer is $\max(A_{par_j})$ where $j$ is a leaf.
Note that the answer will only exceed $\max(A_{par_j})$ if $(U_i, V_i) = (par_j, j)$ where $j$ is a leaf, which is excluded by the subtask condition.
Hence it is sufficient to output $\max(S_{par_j})$ or simply $\max(\min(S_{A_i}, S_{B_i}))$.

Subtask 2

It is now possible for the answer to exceed the above lower bound. However since the tour starts at settlement $0$ and ends at settlement $N-1$, the simple path from $0$ to $N-1$ would be optimal unless there exists two adjacent nodes $x$ and $y$ to repeatedly travel to, which is covered by $\max(\min(S_{A_i}, S_{B_i}))$.
Hence output the maximum between $\max(\min(S_{A_i}, S_{B_i}))$ and the median of the simple path from $0$ to $N-1$.

Subtask 3

Generalising the idea from Subtask 2, observe that for a tour $(U_i, V_i)$, taking a detour away from the simple path from $U_i$ to $V_i$ is only optimal if there exists adjacent settlements $x$ and $y$ where $\min(S_x, S_y)$ is greater than the median on the simple path from $U_i$ to $V_i$.
Consider otherwise, in which adjacent nodes would only offset the median by $+1$ and $-1$, which would not change the median.
Hence simply find the medians of all simple paths from $U_i$ to $V_i$ with DFS in $O(QN\log(N))$. _{(which can pass due to weak cases)}

Observation 2

Let us assume that our final median of a tour is $f$. Note that this $f$ is only achievable if there exists a sequence from $U_i$ to $V_i$ where at least $\lceil{k/2}\rceil$ settlements in the sequence have sweetness $\geq f$.
Let us define settlements which have $S_i\geq f$ be of value $+1$ and settlements with $S_i\lt f$ be of value $-1$.
The problem is then equivalent to finding a path from $U_i$ to $V_i$ that has non-negative sum of values.

Subtask 4

For each query, brute force the final median and check for valid paths. Note that without special handling, there may exist positive/negative cycles in the graph, so using Djikstra to search for a path of maximal sum will lead to TLE.
One way to solve this is to use the $O(NM)$ Bellman-Ford algorithm that can deal with positive/negative cycles, with a final complexity of $O(QN^2M)$.

Subtask 5

Any one of the following optimisations may be made to solve this subtask:

• Binary search on the final median to achieve $O(QNM\log(N))$
• Note that if there are adjacent settlements of value $+1$, then there must always exist a non-negative sum path, hence we can exclude such cases and directly use Djikstra to achieve $O(QNM\log(N))$

Subtask 6 - Solution 1

Just do both of the above optimisations to achieve $O(QM\log^2(N))$.

Observation 3

With our definition of settlement values of $+1$ and $-1$, for most cases: adjacent settlements in the tour sequence with maximal median would have alternating values between $+1$ and $-1$.
The only exception is if the value of both $U_i$ and $V_i$ are $+1$, in which there may be at most one pair of adjacent settlements in the tour sequence with values of $-1$.

Subtask 6 - Solution 2

Initially set all values of settlements to be $-1$. We iterate from possible medians in descending order, turning values of settlements from $-1$ to $+1$.
We maintain all paths of alternating value with DSU. Two settlements in the same DSU would have a valid path of alternating value: equivalent to the current median being possible.
To handle the special case where both $U_i$ and $V_i$ are $+1$, we have to consider neighbors of each of the union grouped of settlements. Using and merging unordered_map to maintain neighbors, we may solve the subtask in $O(QM\log(N))$ or $O(QM\log^2(N))$.

Subtask 7

Note that the condition is equivalent to excluding the special case where both $U_i$ and $V_i$ are $+1$.
We may simply solve this subtask by implementating a Reachability Tree/DSU-Tree with LCA, or directly use the tree created with DSU only with union by rank/size to exclude LCA.
Time complexity: $O((N+Q)\log(N))$

Full Solution

We resort to the tree created with DSU only with union by rank/size, a nice observation would be that useful adjacent settlements both of value $-1$_{(define this as a "negative pair")} will never become of alternating value until there exists adjacent settlements both of value $+1$.
Hence after construction of the tree of height $\log(N)$, we maintain the set of neighbors of each node with unordered_map, where each negative pair will only contribute $O(\log(N))$ neighbors to consider in total with careful implementation.
Time complexity: $O((N+M+Q)\log(N))$