Unofficial Editorial for AtCoder Beginner Contest #190
Difference between en13 and en14, changed 26 character(s)
[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 &mdash; 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 &mdash; 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 &mdash; 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 &mdash; 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 &mdash; 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>↵
↵

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en15 English ScarletS 2021-02-03 05:13:27 58 Tiny change: 'uence by $n - 1 - 2a_' -> 'uence by $N - 1 - 2a_'
en14 English ScarletS 2021-01-30 18:39:40 26 Fixed messy codes to slightly-less-messy ones.
en13 English ScarletS 2021-01-30 17:25:49 4 Tiny change: 'issions/19781904)\n\n</sp' -> 'issions/19822194)\n\n</sp'
en12 English ScarletS 2021-01-30 17:20:52 10 Tiny change: 'issions/19777957)\n\n</spo' -> 'issions/19821916)\n\n</spo'
en11 English ScarletS 2021-01-30 17:14:49 31
en10 English ScarletS 2021-01-30 17:06:38 3 Tiny change: 'exity: $O(N + M + 2^K * K' -> 'exity: $O(K(N + M) + 2^K * K'
en9 English ScarletS 2021-01-30 17:02:49 1 Tiny change: ' $n - 1 - a_i$ for e' -> ' $n - 1 - 2a_i$ for e'
en8 English ScarletS 2021-01-30 17:02:09 4 Tiny change: ' $O(2^K * M * K)$ [My sol' -> ' $O(2^K * (M + K))$ [My sol'
en7 English ScarletS 2021-01-30 16:59:15 64
en6 English ScarletS 2021-01-30 16:55:28 35 Tiny change: 'exity: $O()$ [My sol' -> 'exity: $O(NlogN$ for calculating inversions$)$ [My sol'
en5 English ScarletS 2021-01-30 16:53:46 911
en4 English ScarletS 2021-01-30 16:50:34 348
en3 English ScarletS 2021-01-30 16:49:03 8 Tiny change: 'exity: $O()$ [My sol' -> 'exity: $O(\sqrt(N))$ [My sol'
en2 English ScarletS 2021-01-30 16:45:35 126
en1 English ScarletS 2021-01-30 16:43:52 3234 Initial revision (published)