[Problem AA — ABC Preparation](https://atcoder.jp/contests/abc185/tasks/abc185_a)↵
==============================================================↵
↵
<spoiler summary="Solution">↵
Since we need exactly one of each of $A_1$, $A_2$, $A_3$ and $A_4$, we are limited by the minimum number we have of one of these. Therefore, we need to print the minimum element of these four.↵
↵
[My solution](https://atcoder.jp/contests/abc185/submissions/18767215)↵
↵
</spoiler>↵
↵
[Problem BB — Smartphone Addiction](https://atcoder.jp/contests/abc185/tasks/abc185_b)↵
==============================================================↵
↵
<spoiler summary="Solution">↵
If Takahashi's phone is to run out of battery during his walks between two of the locations, it will be at an even lesser battery at the end of that walk. So, we simply need to check that upon entering one of the $M$ cafes, or returning to his house, that his phone's battery is greater than 0, and increase his battery by $y_i-x_i$ for each of the cafes, while making sure the phone's battery is capped at $N$.↵
↵
[My solution](https://atcoder.jp/contests/abc185/submissions/18767149)↵
↵
</spoiler>↵
↵
[Problem CC — Duodecim Ferra](https://atcoder.jp/contests/abc185/tasks/abc185_c)↵
==============================================================↵
↵
<spoiler summary="Solution 1">↵
We can maintain a $dp_{i,j}$ where $i$ represents the number of cuts made so far, and $j$ represents the length of the iron bar accounted for so far. The transitions are $dp_{i,j} = \sum_{k=0}^{j-1} dp_{i-1,k}$, and our answer is $dp_{12,n}$.↵
↵
[My solution](https://atcoder.jp/contests/abc185/submissions/18766806)↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Solution 2">↵
↵
[See here](https://codeforces.me/blog/entry/85555?#comment-732531)↵
↵
[saarang123's implementation (warning: Python used)](https://atcoder.jp/contests/abc185/submissions/18740195)↵
</spoiler>↵
↵
[Problem DD — Stamp](https://atcoder.jp/contests/abc185/tasks/abc185_d)↵
==============================================================↵
↵
<spoiler summary="Solution">↵
First, sort $A$, so that we have all the blue squares in increasing order. Now, note that the number of white squares between two blue squares is $A_{i+1}-A{i} - 1$. Since we don't need to paint any squares between two blue squares if they are consecutive, as there are none, our value of $k$ will be the minimum across all of the number of white squares between all blue squares that are non-zero, including the number of consecutive non-zero white squares before the first blue square and after the last blue square. Now that we have our value of $k$, we simply need to colour each of these consecutive blocks of white squares. If there are $x_i$ consecutive white squares, we can colour them all red in $\lceil \frac{x_i}{k} \rceil = \lfloor \frac{x_i+k-1}{k} \rfloor$↵
↵
[My solution](https://atcoder.jp/contests/abc185/submissions/18766766)↵
↵
</spoiler>↵
↵
[Problem EE — Sequence Matching](https://atcoder.jp/contests/abc185/tasks/abc185_e)↵
==============================================================↵
↵
<spoiler summary="Solution">↵
Let $dp_{i,j}$ be the minimum number of operations to convert the first $i$ elements of $A$ into the first $j$ elements of $B$. Clearly, we can convert the first $i$ elements of $A$ into the first $j$ elements of $B$ by simply deleting all $i+j$ elements. Now, we can recalculate our $dp$, in order of increasing {i+j}, as follows:↵
↵
- If $A_i=B_j$: $dp_{i,j} = min(i+j, dp_{i-1,j-1}, dp_{i-1,j}+1, dp_{i,j-1}+1)$↵
↵
- Otherwise: $dp_{i,j} = min(i+j, dp_{i-1,j-1}+1, dp_{i-1,j}+1, dp_{i,j-1}+1)$↵
↵
This is because we can reduce the problem down, respectively, by:↵
↵
1. deleting all $i+j$ elements↵
2. leaving the $i-th$ and $j-th$ elements as they are and taking any penalties for having non-equal elements↵
3. deleting the previous element from $A$↵
4. deleting the previous element from $B$↵
↵
Our answer is $dp_{n,m}$.↵
↵
[My solution](https://atcoder.jp/contests/abc185/submissions/18766349)↵
↵
</spoiler>↵
↵
[Problem FF — Range Xor Query](https://atcoder.jp/contests/abc185/tasks/abc185_f)↵
==============================================================↵
↵
<spoiler summary="Solution">↵
We can use a data structure, such as a Fenwick tree, or segment tree, to process these queries. ↵
↵
[My solution](https://atcoder.jp/contests/abc185/submissions/18769701)↵
↵
</spoiler>↵
↵
==============================================================↵
↵
<spoiler summary="Solution">↵
Since we need exactly one of each of $A_1$, $A_2$, $A_3$ and $A_4$, we are limited by the minimum number we have of one of these. Therefore, we need to print the minimum element of these four.↵
↵
[My solution](https://atcoder.jp/contests/abc185/submissions/18767215)↵
↵
</spoiler>↵
↵
[
==============================================================↵
↵
<spoiler summary="Solution">↵
If Takahashi's phone is to run out of battery during his walks between two of the locations, it will be at an even lesser battery at the end of that walk. So, we simply need to check that upon entering one of the $M$ cafes, or returning to his house, that his phone's battery is greater than 0, and increase his battery by $y_i-x_i$ for each of the cafes, while making sure the phone's battery is capped at $N$.↵
↵
[My solution](https://atcoder.jp/contests/abc185/submissions/18767149)↵
↵
</spoiler>↵
↵
[
==============================================================↵
↵
<spoiler summary="Solution 1">↵
We can maintain a $dp_{i,j}$ where $i$ represents the number of cuts made so far, and $j$ represents the length of the iron bar accounted for so far. The transitions are $dp_{i,j} = \sum_{k=0}^{j-1} dp_{i-1,k}$, and our answer is $dp_{12,n}$.↵
↵
[My solution](https://atcoder.jp/contests/abc185/submissions/18766806)↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Solution 2">↵
↵
[See here](https://codeforces.me/blog/entry/85555?#comment-732531)↵
↵
[saarang123's implementation (warning: Python used)](https://atcoder.jp/contests/abc185/submissions/18740195)↵
</spoiler>↵
↵
[
==============================================================↵
↵
<spoiler summary="Solution">↵
First, sort $A$, so that we have all the blue squares in increasing order. Now, note that the number of white squares between two blue squares is $A_{i+1}-A{i} - 1$. Since we don't need to paint any squares between two blue squares if they are consecutive, as there are none, our value of $k$ will be the minimum across all of the number of white squares between all blue squares that are non-zero, including the number of consecutive non-zero white squares before the first blue square and after the last blue square. Now that we have our value of $k$, we simply need to colour each of these consecutive blocks of white squares. If there are $x_i$ consecutive white squares, we can colour them all red in $\lceil \frac{x_i}{k} \rceil = \lfloor \frac{x_i+k-1}{k} \rfloor$↵
↵
[My solution](https://atcoder.jp/contests/abc185/submissions/18766766)↵
↵
</spoiler>↵
↵
[
==============================================================↵
↵
<spoiler summary="Solution">↵
Let $dp_{i,j}$ be the minimum number of operations to convert the first $i$ elements of $A$ into the first $j$ elements of $B$. Clearly, we can convert the first $i$ elements of $A$ into the first $j$ elements of $B$ by simply deleting all $i+j$ elements. Now, we can recalculate our $dp$, in order of increasing {i+j}, as follows:↵
↵
- If $A_i=B_j$: $dp_{i,j} = min(i+j, dp_{i-1,j-1}, dp_{i-1,j}+1, dp_{i,j-1}+1)$↵
↵
- Otherwise: $dp_{i,j} = min(i+j, dp_{i-1,j-1}+1, dp_{i-1,j}+1, dp_{i,j-1}+1)$↵
↵
This is because we can reduce the problem down, respectively, by:↵
↵
1. deleting all $i+j$ elements↵
2. leaving the $i-th$ and $j-th$ elements as they are and taking any penalties for having non-equal elements↵
3. deleting the previous element from $A$↵
4. deleting the previous element from $B$↵
↵
Our answer is $dp_{n,m}$.↵
↵
[My solution](https://atcoder.jp/contests/abc185/submissions/18766349)↵
↵
</spoiler>↵
↵
[
==============================================================↵
↵
<spoiler summary="Solution">↵
We can use a data structure, such as a Fenwick tree, or segment tree, to process these queries. ↵
↵
[My solution](https://atcoder.jp/contests/abc185/submissions/18769701)↵
↵
</spoiler>↵
↵
