T221 - Angle Sum of Polygon

The angle sum of a $N$-sided polygon (or $N$-gon) is $(N-2) \cdot 180^\circ$. Remember to use long long.

T222 - Laundry

Hint 1

What is the minimum number of days that Justin can wear a shirt in a week, given that he has $S$ shirts currently?

Hint 2

How many shirts he can wear in a week, providing that he also put shirts into the laundry?

Solution

T223 - Fascinating Compositions

Subtask 1 (30%)

Suppose that to achieve the minimum number of operations, we will need to have $K$ essays of length $L$. Out of all the essays with at most $L$ characters, we can greedily find the $K$ essays which have the closest number of characters to $L$ and then perform operations on them.

Also note that $L$ is necessarily an element of $A$ (i.e. $L \in A$). If not, we can decrease $L$ to achieve a smaller number of operations.

Sort the array $A$. For each subarray of length $K$, count the number of operations needed to make all of them the same as its maximal element. Find the minimum number of operations across all such subarrays.

Time complexity: $O(N \log N + NK)$

Subtask 2 (70%)

Use prefix sum to calculate the sum of any subarray in $O(1)$. For any subarray $B_1, B_2, \cdots, B_K$ of length $K$, the number of operations needed to fulfill the requirement is $$B_K \cdot K - (B_1 + B_2 + \cdots + B_K)$$

Sliding window may also be used instead of prefix sum.

Time complexity: $O(N \log N)$

T224 - Rock's Canvas

Consider the Cartesian coordinate plane and two points $P_1(x_1, y_1)$ and $P_2(x_2, y_2)$.

We can express a straight line on the coordinate plane as $y = mx + c$ where $m$ is the slope and $c$ is the y-intercept. The only property that distinguishes two lines of the same slope is the y-intercept.

Note that $B_i = 1$ corresponds to slope $1$, and $B_i = 2$ corresponds to slope $-1$.
A line with slope $1$ is of the form $y = x + c$, which we can rewrite as $c = y - x$. $P_1$ and $P_2$ are on the same line with slope $1$ if $y_1 - x_1 = y_2 - x_2$.
Similarly, a line with slope $-1$ is of the form $y = -x + c$, which we can rewrite as $c = x + y$. $P_1$ and $P_2$ are on the same line with slope $-1$ if $x_1 + y_1 = x_2 + y_2$.

Subtask 1-4 (60%)

When Rock checks the majority of some diagonal, check for each star drawn if it lies on the specified line.

Time complexity: $O(Q^2)$ or $O(Q^2 \log Q)$ depending on implementation

Subtask 5 (40%)

We can construct a map, so that for each slope and y-intercept pair $(m, c)$, we have another map $C$ storing the count of each color like a counting array, the total number of elements $L$, and color $X$ which is the majority element.

Every time Rock draws a star of a color $T$ in a cell, we will update two $(m, c)$ pairs, one where $m = 1$ and one where $m = -1$. We increase the count of $T$ by 1 in $C$, increase $L$ by 1, and check if $T$ is the new majority element using $2 \cdot C[T] > L$. If so, we update $X$ to be $T$.

When Rock checks the majority of some diagonal, we check that for the correponding $(m, c)$ pair if $2 \cdot C[X] > L$ still holds. If so, $X$ is the majority, otherwise there is no majority.

Time complexity: $O(Q \log Q)$

Note

The plane is 1-based, meaning $C_i$ given in the input is not exactly the y-intercept.

T225 - Love Cycle

We can model the problem as a graph with $N$ nodes. For each $1 \le i \le N$, we draw a directed edge from $i$ to $P_i$.

We will give each node $i$ a label $L_i$. If two nodes $i, j$ are in the same cycle, then $L_i = L_j$, otherwise $L_i \neq L_j$. We can achieve this using BFS / DFS / DSU. Then we have a unique number for each cycle in the graph, because each node in the cycle has the same $L_i$. We will now use $L_i$ to refer to cycles instead. We can then compute the size of each cycle.

Note that $0 \le K \le 2$. We can choose to do one of the following some amount of times:

1. Choose an index $i$. For a cost of $1$, swap $P_i$ and $P_{i+1}$.
2. Choose an index $i$. For a cost of $2$, swap $P_i$ and $P_{i+2}$.

We are trying to maximize the size of any cycle. If $L_i \neq L_j$, the act of swapping $P_i$ and $P_j$ merges the cycles $L_i$ and $L_j$. Therefore, if we choose to perform option 2 to merge cycles $i$ and $i + 2$, we can instead perform option 1 twice to merge cycles $i, i+1, i+2$ for the same cost. Therefore it is necessarily optimal to swap $P_i$ for adjacent $i$ only.

We will construct another graph $G$ with $L_i$ as nodes representing cycles. For each $1 \le i \le N - 1$, if $L_i \neq L_{i + 1}$, we construct an undirected edge between nodes $L_i$ and $L_{i+1}$, meaning we can merge cycles $L_i$ and $L_{i+1}$ with cost 1. Take steps to prevent duplicate edges. For each node $L_i$ in $G$, find at most $K$ neighbors with the largest size. Add the size of cycles $L_i$ and its $K$ neighbors together. The answer is the maximum of such sums across each node.

Time complexity: $O(N)$ or $O(N \log N)$ depending on implementation

Note

In the initial version of this problem $K=4$. However it was rejected as the solution was incorrect and time was running short.