[A — Very Very Primitive Game](https://atcoder.jp/contests/abc190/tasks/abc190_a)↵
---------------------------------------------------------------------------------------↵
↵
<spoiler summary="Solution">↵
Simply simulate the game and print out the winner.↵
↵
Time complexity: $O(A+B)$ [My solution](https://atcoder.jp/contests/abc190/submissions/19821916)↵
↵
</spoiler>↵
↵
[B — Magic 3](https://atcoder.jp/contests/abc190/tasks/abc190_b)↵
---------------------------------------------------------------------------------------↵
↵
<spoiler summary="Solution">↵
For each spell $i$, check if $X_i < S$ and $Y_i > D$. If such spell $i$ is found, the answer is `"Yes"`, otherwise, if after all spells have been processed and no such spell has been found, the answer is `"No"`.↵
↵
Time complexity: $O(N)$ [My solution](https://atcoder.jp/contests/abc190/submissions/19822194)↵
↵
</spoiler>↵
↵
[C — Bowls and Dishes](https://atcoder.jp/contests/abc190/tasks/abc190_c)↵
---------------------------------------------------------------------------------------↵
↵
<spoiler summary="Solution">↵
We can approach this problem using bitmasks. For each $i$ from $0$ to $2^K-1$, if bit $j$ is "on" (i.e. $i$ AND $2^j = 2^j$), we give the $j$-th dish to ball to $C_j$, otherwise we give it to $D_j$. We calculate the maximum number of satisfied conditions across all $i$, and that is our answer.↵
↵
Time complexity: $O(2^K * (M + K))$ [My solution](https://atcoder.jp/contests/abc190/submissions/1978891824997)↵
↵
</spoiler>↵
↵
[D — Staircase Sequences](https://atcoder.jp/contests/abc190/tasks/abc190_d)↵
---------------------------------------------------------------------------------------↵
↵
<spoiler summary="Solution">↵
The sum $S$ of an arithmetic sequence with first term $a$, $n$ terms, and common difference $1$ can be found with the formula $S = \frac{n}{2}[2a + n - 1]$. Rearranging this and multiplying across by $2$, we get $2S = n(n+2a-1)$, therefore $n$ must be a factor of $2S$, which is $2N$ in this problem. Rearranging further, we get $a = \frac{\frac{2N}{i}-i+1}{2}$. Now, we can iterate over all the factors $i$ of $2N$, and we need to check if $\frac{2N}{i}-i+1$ is divisible by $2$.↵
↵
Time complexity: $O(\sqrt{N})$ [My solution](https://atcoder.jp/contests/abc190/submissions/1980023325009)↵
↵
</spoiler>↵
↵
[E — Magical Ornament](https://atcoder.jp/contests/abc190/tasks/abc190_e)↵
---------------------------------------------------------------------------------------↵
↵
<spoiler summary="Solution">↵
We can represent the gems which can be placed adjacent to each other using a graph. Now, for each $C_i$, do a breadth-first search of the graph and calculate distances to all other gems. We can now model the solution as one with dynamic programming with bitmasks. Let $dp_{i,j}$ be our answer if we use all the gems included in the mask of $i$, ending with gem number $j$.↵
↵
Time complexity: $O(K(N + M) + 2^K * K^2)$ [My solution](https://atcoder.jp/contests/abc190/submissions/1980708025033)↵
↵
</spoiler>↵
↵
[F — Shift and Inversions](https://atcoder.jp/contests/abc190/tasks/abc190_f)↵
---------------------------------------------------------------------------------------↵
↵
<spoiler summary="Solution">↵
We can calculate the number of inversions in the original array in a number of ways, such as with a Fenwick tree or with merge sort. Now, notice that each of the resulting sequences essentially remove the first element of the previous sequence and insert it at the end of it. This changes the number of inversions in the new sequence by $n - 1 - 2a_i$ for each $i$ from $0$ to $N-2$.↵
↵
Time complexity: $O(NlogN$ for calculating inversions $)$ [My solution](https://atcoder.jp/contests/abc190/submissions/1980923425040)↵
↵
</spoiler>↵
↵
---------------------------------------------------------------------------------------↵
↵
<spoiler summary="Solution">↵
Simply simulate the game and print out the winner.↵
↵
Time complexity: $O(A+B)$ [My solution](https://atcoder.jp/contests/abc190/submissions/19821916)↵
↵
</spoiler>↵
↵
[B — Magic 3](https://atcoder.jp/contests/abc190/tasks/abc190_b)↵
---------------------------------------------------------------------------------------↵
↵
<spoiler summary="Solution">↵
For each spell $i$, check if $X_i < S$ and $Y_i > D$. If such spell $i$ is found, the answer is `"Yes"`, otherwise, if after all spells have been processed and no such spell has been found, the answer is `"No"`.↵
↵
Time complexity: $O(N)$ [My solution](https://atcoder.jp/contests/abc190/submissions/19822194)↵
↵
</spoiler>↵
↵
[C — Bowls and Dishes](https://atcoder.jp/contests/abc190/tasks/abc190_c)↵
---------------------------------------------------------------------------------------↵
↵
<spoiler summary="Solution">↵
We can approach this problem using bitmasks. For each $i$ from $0$ to $2^K-1$, if bit $j$ is "on" (i.e. $i$ AND $2^j = 2^j$), we give the $j$-th dish to ball to $C_j$, otherwise we give it to $D_j$. We calculate the maximum number of satisfied conditions across all $i$, and that is our answer.↵
↵
Time complexity: $O(2^K * (M + K))$ [My solution](https://atcoder.jp/contests/abc190/submissions/19
↵
</spoiler>↵
↵
[D — Staircase Sequences](https://atcoder.jp/contests/abc190/tasks/abc190_d)↵
---------------------------------------------------------------------------------------↵
↵
<spoiler summary="Solution">↵
The sum $S$ of an arithmetic sequence with first term $a$, $n$ terms, and common difference $1$ can be found with the formula $S = \frac{n}{2}[2a + n - 1]$. Rearranging this and multiplying across by $2$, we get $2S = n(n+2a-1)$, therefore $n$ must be a factor of $2S$, which is $2N$ in this problem. Rearranging further, we get $a = \frac{\frac{2N}{i}-i+1}{2}$. Now, we can iterate over all the factors $i$ of $2N$, and we need to check if $\frac{2N}{i}-i+1$ is divisible by $2$.↵
↵
Time complexity: $O(\sqrt{N})$ [My solution](https://atcoder.jp/contests/abc190/submissions/198
↵
</spoiler>↵
↵
[E — Magical Ornament](https://atcoder.jp/contests/abc190/tasks/abc190_e)↵
---------------------------------------------------------------------------------------↵
↵
<spoiler summary="Solution">↵
We can represent the gems which can be placed adjacent to each other using a graph. Now, for each $C_i$, do a breadth-first search of the graph and calculate distances to all other gems. We can now model the solution as one with dynamic programming with bitmasks. Let $dp_{i,j}$ be our answer if we use all the gems included in the mask of $i$, ending with gem number $j$.↵
↵
Time complexity: $O(K(N + M) + 2^K * K^2)$ [My solution](https://atcoder.jp/contests/abc190/submissions/198
↵
</spoiler>↵
↵
[F — Shift and Inversions](https://atcoder.jp/contests/abc190/tasks/abc190_f)↵
---------------------------------------------------------------------------------------↵
↵
<spoiler summary="Solution">↵
We can calculate the number of inversions in the original array in a number of ways, such as with a Fenwick tree or with merge sort. Now, notice that each of the resulting sequences essentially remove the first element of the previous sequence and insert it at the end of it. This changes the number of inversions in the new sequence by $n - 1 - 2a_i$ for each $i$ from $0$ to $N-2$.↵
↵
Time complexity: $O(NlogN$ for calculating inversions $)$ [My solution](https://atcoder.jp/contests/abc190/submissions/198
↵
</spoiler>↵
↵
