# ZCK Adhoc 講義補充
## 題目連結
暖身題:https://oj.uz/problem/view/IZhO19_stones

### 次小值的妙用
MST and Rectangles: https://csacademy.com/contest/archive/task/rectangle-mst/statement/
TIOJ 1793 (冥王星觀光): https://tioj.ck.tp.edu.tw/problems/1793

### 不同的東西
Election Spies: https://csacademy.com/contest/archive/task/election-spies/
Xoractive: https://oj.uz/problem/view/IZhO19_xoractive

### 怪怪環問題
補充: Xor basis (異或線性基): https://codeforces.com/blog/entry/68953
TIOJ 1094: https://tioj.ck.tp.edu.tw/problems/1094
Xor Cycle: https://csacademy.com/contest/archive/task/xor_cycle/
CF Global 14 pG: https://codeforces.com/contest/1515/problem/G

## 觀察力訓練題解
為了訓練大家看CF題解的能力(x)，題解是英文的>< 看不懂可以問我ww
### USACO Triangles
http://www.usaco.org/index.php?page=viewproblem2&cpid=672

:::spoiler Difficulty
5/10
:::

:::spoiler Hint 1
A brute force, trivial solution exists in $O(n^4)$ by iterating over every triangle and every point.
:::
:::spoiler Hint 2
Try to do some sort of DP, where you combine the solution for multiple triangles to get the answer for one triangle.
For example, if point $p$ is inside triangle $(a, b, c)$ then the number of points inside that triangle $f(a, b, c) = f(a, b, p) + f(a, c, p) + f(b, c, p)$.
:::
:::spoiler Hint 3
Continuing from hint 2, what happens when you try moving point $p$ out of the triangle?
:::
::: spoiler Full solution
Official Sol.
http://www.usaco.org/current/data/sol_triangles_platinum_dec16.html

My solution:
From Hint 3, observe that $f(a, b, c)$ is always a combination of $\pm f(a, b, p), \pm f(a, c, p), \pm f(b, c, p)$. All points that are in the triangle have to be in exactly one of the three triangles above. However, if $p$ is outside the triangle, you'd either have to add or subtract that number from the answer. More specifically, if points $c, p$ are on the same side of line segment $(a, b)$, then $f(a, b, p)$ should be added to the answer, otherwise it should be subtracted from the answer.

With that in mind, we can brute force all triangles with point $p = 1$, then for every other triangle find the answer in $O(1)$.

:::

### Tree Square
https://csacademy.com/contest/archive/task/tree-square/
:::spoiler Difficulty
8/10
:::

:::spoiler Hint 1
Every edge implies that the two vertices have either distance 1 or 2, and identifying a valid solution means finding that distance for each edge.
:::
:::spoiler Hint 2
Assume the edge $(u, v)$ is a tree edge, for all pairs of edges $((u, w), (v, w))$, one of them must be a tree edge and the other must not be.
:::
:::spoiler Hint 3
Consider the problem with a BFS tree, that way you can classify edges better. Notice how for layer $i$ the depth of the nodes on that layer to the root in $G$ must be either $2i$ or $2i - 1$.

註:BFS Tree 是指，在BFS的過程中，如果是節點$u$找到節點$v$，那$(u, v)$這條邊就是樹上的邊，這樣的規則建出來的樹。在BFS樹上深度為$i$的節點代表他們與起點的最短距離為$i$。非樹邊有兩種，跨越兩層的($|d_u - d_v| = 1$) 或在同一層的($d_u = d_v$)
:::
:::spoiler Hint 4
There is always at least one edge between two adjacent layers that is a tree edge.
:::
:::spoiler Hint 5
A leaf node is only adjacent to one tree edge.
:::
::: spoiler Hint 6
Consider special cases (ex. a star graph). Could you solve it if $G$ was a star? What property do you get if $G$ is not a star?
:::
::: spoiler Full solution
If $G$ is a star, then $G^2$ is a clique (完全圖). Simply output any star and you have an answer.

Otherwise, $G$ is not a star and the diameter is at least $3$, which also means that every non-leaf node is adjacent (by a tree edge) to at least one other non-leaf node. Call this node $u$. Then if $u$ isn't a leaf, there exists an adjacent node $v$ such that $v$ isn't adjacent to a node that $u$ is adjacent to. (In other words, the induced subgraph formed by $u$ and the adjacent nodes of $u$ isn't a clique) Thus, we are guranteed to find a leaf node that satisfies the condition above.

Consider the BFS tree with a leaf node as the root. We will denote $dis[i]$ as the depth of node $i$ in our final tree $G$. We will enumerate the one tree edge that the root is connected to, let's call it $(root, u)$. We can see that $dis[u] = 1$ and all the other nodes in the first layer have $dis = 2$. For the second layer, all nodes with $dis = 3$ must be connected to nodes with $dis = 1$, thus all edges going from nodes with $dis = 1$ point to nodes with $dis = 3$, and the rest have $dis = 4$. This process can be done for each layer, and we can find the $dis$ value for each node. Then all we have to do is brute force check if those values correctly form a tree.

Since the root is adjacent to at most $n$ nodes, the complexity is $O(n*(n + m))$.
:::

### Surround the Enemy
https://csacademy.com/contest/archive/task/surround-the-enemy/statement/
:::spoiler Difficulty
5/10
:::
:::spoiler Hint 1
The problem essentially becomes finding the minimum weighted cycle that contains the enemy.
Observe that the best cycle must be a simple cycle, since if there are any loops removing it would definitely give an answer just as good or better.
:::
:::spoiler Hint 2
A cycle that surrounds the enemy has to pass through at least one cell that is directly above the enemy.
More specifically, if the enemy is at $(sx, sy)$, the cycle must pass through a cell $(x, y)$ such that $x < sx$ and $y = sy$.
:::
:::spoiler Hint 3
Think of the cycle as a polygon, and the problem is essentially finding a necessary and sufficient condition for a point to be in the polygon.
Try observing the number of times it passes through the top of the point.
:::
:::spoiler Full Solution
We can determine if a point is in a polygon by shooting an arbitrary ray from the point and counting the number of times that ray intersects with the polygon. If that number is odd, the point is in the polygon, and otherwise it is outside the polygon (Proof. the ray turns from "inside" to "outside" and vice versa every time it intersects with the polygon, and it eventually has to be outside). We can think of the ray as a line going directly up from the enemy, and perform dijkstra's algorithm.
Let's try iterating over every cell above the enemy. For each cell we'll perform dijkstra's algorithm once. We'll maintain two states for each node, $dis[i][j][0]$ is the minimum distance from the starting
cell to cell $(i, j)$ if the path crossed the "ray" an even number of times, and $dis[i][j][1]$ is with an odd number of times. The answer for each starting node $(x, y)$ is $dis[x][y][1]$. Notice that we should set the cost of the enemy's cell to infinity.
Now when exactly do we change states? Consider the picture below:
We should imagine the ray at the border of two columns like the yellow arrow to avoid cases where the path moves up and down on the same column.
:::
### BOI Triangulation
https://cses.fi/108/list/
:::spoiler Difficulty
2/10
:::

:::spoiler Hint 1
You'd only make cuts along the triangulation of the polygon. Otherwise you'd cut the same triangle into two parts which clearly violates the restrictions.
:::
:::spoiler Hint 2
Build a graph where each vertex is a triangle, and two vertices are connected by an edge if they share a common edge in the triangulation.
:::
:::spoiler Hint 3
The graph in hint 2 is a tree, and the problem becomes finding the maximum number of components the tree can be cut into where each color belongs in one component.
:::
:::spoiler Full solution
From hint 3, notice that we only have to consider for each edge if removing it violates the condition, and removing one edge does not affect whether or not you should remove the other edge.
All the nodes of the same color form a connected subgraph, and all edges in that subgraph cannot be removed. To mark the subgraph, sort the nodes by their DFS order, for each new node add 1 to the weight of that node, and subtract one from the weight of the lca between this node and the previous node. Finally, subtract one from the "root node", which is the LCA between all nodes.
Repeat that for all colors and the number of edges unmarked is the answer. This can be obtained by doing DFS and finding the total weight of each node's subtree, and checking if it's equal to 0.
:::

### Binary Swaps
https://csacademy.com/contest/archive/task/binary-swaps/
:::spoiler Difficulty
7/10
:::

:::spoiler Hint 1
The process eventually terminates after some number of steps, and in the end will look like "111...10...000".
The position of every "1" is non-decreasing, while the position of every "0" is non-increasing.
:::
:::spoiler Hint 2
The relative order between 1's and between 0's doesn't change.
Think of the 1's moving to the left, in each step it would either swap with a zero on the left or not move because it's "blocked" by a 1 on the left (or it reached the beginning of the array).
:::
:::spoiler Hint 3
To know how the '1' on position $x$ moves, we only need to know how the '1' directly to the left of $x$ moves.
If the '1' gets blocked $k$ times, it will end up at position $x - t + k$.
:::
:::spoiler Hint 4
Consider the 1's from left to right, and for each 1 maintain an array $S$ of length $t$, where $S_i = 1$ if the 1 gets blocked at the i'th step, and $0$ if it swaps with a 0.
ex. For array [0, 0, 1, 1, 0, 1] and $t = 3$, $S$ for the last 1 would be [0, 1, 0].
:::
:::spoiler Hint 5
Observe how the string changes from a 1 to another 1 directly to the right of it.
:::
:::spoiler Full Solution
Continuing from Hint 5, let the distance between two consecutive 1's be $d$, then $d$ is non-increasing until it reaches $1$, and after that $d$ is either $1$ or $2$.
Now let's look at how $S$ (the string for the previous 1) turns into $S'$(the string for the current 1). $S'_i$ will initially be $0$ as long as $d > 1$, let $j$ be the index where $d = 1$ for the first time (before moving), then $S'_j = 1$, and for all $k > j, S'_k = S_{k - 1}$ will hold. That's because after $d$ becomes 1, any zero that passes through the previous 1 will immediately pass through the current 1, and if the previous 1 was blocked in the last step, the current 1 will also be blocked on the current step.
We now need to maintain an array that supports the following operations:
- Set $S_i = 0$ for all $i < j$.
- Shift all elements 1 cell to the right.
- Set $S_j = 1$.
- Maintain the number of 1's in the array.
How do we find $j$? Observe that $d$ only decreases by 1 when $S_i = 1$, this means that $d - 1$ 1's in $S$ will be removed before $d = 1$, and $j$ is equal to $1 + (position \ of \ rightmost \ 1)$. So instead of saving the data as an array, we can save it as a deque where each element is the position of a 1. For each iteration, we simply have to delete $d - 1$ 1's in the front, insert a 1 in the front, then shifting by 1 could easily be done by changing the start/end position of the deque. Since you only insert at most a single 1 in each iteration, the time complexity is amortized (均攤) $O(n)$.
C++: https://csacademy.com/submission/3162957/

:::
### JOISC Sandwich
https://www.ioi-jp.org/camp/2016/2016-sp-tasks/2016-sp-d2.pdf

:::spoiler Difficulty
7/10
:::

:::spoiler Hint 1
The only place you can start with is the four corners.
:::
:::spoiler Hint 2
If it is possible, then the answer is always even. Why?
:::
:::spoiler Hint 3: 35/100 points
There are two ways to get to a cell. If it's an "N" then you'd have to either remove the top and right sides or the down and left sides. This corresponds to two directed edges to adjacent cells.
:::
:::spoiler Hint 4
If you decide to clear a cell "N" by removing the left and down cells, all cells directly to the left and directly below that cell will be removed.

Picture:

| .\ | ./ | ./ | .\ |
| --- | --- | --- | --- |
| | | | /. |
| | | | .\ |

:::

::: spoiler Full solution
日文題解: https://www.ioi-jp.org/camp/2016/2016-sp-tasks/2016-sp-d2-sandwich-review.pdf
In an optimal solution, you'd always remove entire sandwiches. That's because if you're removing this triangle, both sides (the sides forming a right angle in the right triangle) have to be removed, then if you don't remove the other triangle, it couldn't influence any other cells, and should not be removed in the first place.

From Hint 3, we can build a directed graph where each node is a cell and each edge $(u, v)$ means "cell $v$ has to be removed before cell $u$". Obviously, if the graph is acyclic, there is a solution and the answer is the number of nodes reached in the graph.
Now we have a brute force solution in $O(n^2m^2)$: Build a directed graph starting from the cell you want to find the answer to, and use topological sort to check if it is acyclic. Notice that you have to take the minimum value between the two ways of getting to the cell.

To get the full solution, the observation in Hint 4 is required. To elaborate, consider the direction of the edge that points to a cell $v$. Regardless of whether the cell is "N" or "Z", that same direction will be passed to the next cell. Also notice that when you're brute forcing the solution, you build the graph for a cell starting from either its left or right side. Thus the left graph for cell $(i, j + 1)$ must contain the left graph of the cell $(i, j)$, and we only have to find the additional cells added.

There are two more observations to make implementation simpler. Firstly, all new cells added must be connected the the starting cell, and if the previous graph is acyclic and the new graph contains cycles, the cells in the cycle must be found while performing DFS on the new cell. This means we simply have to perform DFS from the new cell, ignore the cells visited before and check if there are newly formed cycles. At most $nm$ cells will be visited per row, which adds up to a complexity of $O(n*nm)$.

Solution in C++: https://www.ioi-jp.org/camp/2016/2016-sp-tasks/2016-sp-d2-sandwich-sample.cpp
:::

### Anagram sort
https://csacademy.com/contest/archive/task/anagram-sort/statement/
:::spoiler Difficulty
6/10
:::

:::spoiler Hint 1
Consider the simpler case where the array $A$ is a permutation. The minimum number of swaps from another permuation $B$ to $A$ is the number of pairs $(i, j)$ such that $[a_i < a_j] \neq [b_i < b_j]$. ($[x]$ is the boolean function which returns 1 if the statement is true and 0 otherwise).
:::
:::spoiler Hint 2
Consider trying to do bubble sort on the judge's array. Can you find the position of the smallest element in two queries?
:::
:::spoiler Hint 3
Try to find $f(i)$, the number of indices $j < i$ such that $a_j > a_i$ for each $i$.
:::

::: spoiler Full solution
https://csacademy.com/contest/archive/task/anagram-sort/solution/
:::
### AGC 016 pD
https://atcoder.jp/contests/agc016/tasks/agc016_d
:::spoiler Difficulty
4/10
:::
:::spoiler Hint 1
If you do the operation twice on the same element, you'd end up with the original array.
:::
:::spoiler Hint 2
Let $a_0 = a_1 ^ a_2 ^ ... ^ a_n$, then the operation is equivalent to swapping $a_0$ with $a_i$.
:::
:::spoiler Hint 3
Imagine a simpler case where $a_i (\forall 0 \leq i < n)$ are distinct.
Draw a directed graph where each element $a_i$ points to $b_j$ if $a_i = b_j$. How many operations are required to turn $A$ into $B$?
:::
:::spoiler Full Solution
Continuing from Hint 3, if all $a_i$ are distinct, we can build the graph mentioned above, and the number of operations to solve each cycle would be $size - 1$ if $a_0$ is in the cycle and $size + 1$ otherwise (if $size > 1$), thus the answer is $\sum size + cycle \ num - 2$. We can ignore the positions where $a_i = b_i$ if $i > 0$.
The problem arises when there are equal elements, since it would be unclear how the graph should be built. However, we can see from the formula above that we want to minimize the number of cycles, and if two cycles each contain an element of the same value, then we can always swap edges in a way that merges them into one cycle. Thus, we simply have to start from any graph and then use DSU to merge cycles containing the same element.
C++: https://atcoder.jp/contests/agc016/submissions/23386194
:::

### JOISC Toilets
https://atcoder.jp/contests/joisc2016/tasks/joisc2016_f
:::spoiler Difficulty
6/10
:::
:::spoiler Hint 1
We can see that all boys have to go to the mixed restroom. Thus, if there are more than $N$ boys, the answer is $-1$.
:::

:::spoiler Hint 2
Consider the process of the queue as spltting the people into $N$ pairs, where pair $i$ is the two people that go to the toilet at time $i$. Try observing how the pairing works. Notice that one person in each pair will always be a girl.
:::

:::spoiler Hint 3
The pairing process can be summarized as follows: Go from the start to the end of the queue, if the current person is a girl, then pair it with the leftmost unpaired person. If all boys at the end of the process are paired, then they can finish in $N$ minutes.
:::

:::spoiler Hint 4
You'd only want to move boys infront of the girls, and if the answer is $k$, it will be optimal if there are $k$ new boys infront of every girl (if possible).
:::

:::spoiler Hint 5
Let's represent a boy as +1, and a girl as -1. Basically, we'd want to know $boys \ - \ girls$ for each prefix in the string (prefix sums). Notice that there will always be at most one girl that is unpaired.
:::

:::spoiler Full Solution
https://www.ioi-jp.org/camp/2016/2016-sp-tasks/2016-sp-d2-toilets-review.pdf

Continuing from Hint 5, let's imagine finding the prefix sum for every position of the string.
We can find the number of boys paired by calculating the number of girls paired with girls, and the most important observation is that this number is equal to $\lfloor \min(pref_i) / 2 \rfloor$.
With that, we can calculate the minimum value of $\min(pref_i)$ to so that all boys are paired, and the difference between that and the current minimum prefix is the answer.

C++: https://www.ioi-jp.org/camp/2016/2016-sp-tasks/2016-sp-d2-toilets-sample.cpp
My code: https://atcoder.jp/contests/joisc2016/submissions/23384634
:::