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

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

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

See here

saarang123's implementation (warning: Python used)

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

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

We can use a data structure, such as a Fenwick tree, or segment tree, to process these queries.

My solution (using a Fenwick tree)