A — ABC Preparation
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.
B — Smartphone Addiction
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$$$.
C — Duodecim Ferra
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}$$$.
D — Stamp
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$$$
E — Sequence Matching
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:
- deleting all $$$i+j$$$ elements
- leaving the $$$i-th$$$ and $$$j-th$$$ elements as they are and taking any penalties for having non-equal elements
- deleting the previous element from $$$A$$$
- deleting the previous element from $$$B$$$
Our answer is $$$dp_{n,m}$$$.
F — Range Xor Query
We can use a data structure, such as a Fenwick tree, or segment tree, to process these queries.
C can also be done using the Stars and Bars theorem,
We have $$$x_0 + x_1 + x_2 + \dots + x_{11} = n$$$ in C where $$$x_i$$$ are the lengths of the bars. This is just the number of positive integral solutions which is $$$n - 1 \choose 11$$$
Thanks! I added your solution!
saarang orz
Auto comment: topic has been updated by ScarletS (previous revision, new revision, compare).
Auto comment: topic has been updated by ScarletS (previous revision, new revision, compare).
Can you explain the dp[i][j] solution in Problem C a little more. How do the transitions come? I can't get that.
$$$dp[i][j][0]$$$ denotes the number of ways till $$$ith$$$ index such that the number of cuts made so far are $$$j$$$, and there is no cut at the ith index.
$$$dp[i][j][1]$$$ denotes the number of ways till $$$ith$$$ index such that the number of cuts made so far are $$$j$$$, and there is a cut at the ith index.
So now $$$dp[i][j][0]=dp[i-1][j][0]+dp[i-1][j][1]$$$. There are $$$j$$$ cuts till $$$ith$$$ index. It implies there were $$$j$$$ cuts till $$$(i-1)th$$$ index because there is no cut at the $$$ith$$$ index.
$$$dp[i][j][1]=dp[i-1][j-1][0]+dp[i-1][j-1][1]$$$. Since there are $$$j$$$ cuts till $$$ith$$$ index and there is a cut at the $$$ith$$$ index, it implies there were $$$(j-1)$$$ cuts till $$$(i-1)th$$$ index.
In the end, the answer is $$$dp[L][11][0]$$$. Since we want $$$11$$$ cuts till the $$$Lth$$$ index and also the cut is not at the $$$Lth$$$ index (Cut at $$$Lth$$$ index means there is no piece after that so the cut should essentially be before $$$Lth$$$ index for $$$12$$$ pieces).
I did a $$$O(12*n)$$$ dp for C. Didn't notice the constraint was too small :/
Auto comment: topic has been updated by ScarletS (previous revision, new revision, compare).
For second solution of C actually you don't need python it also can be done with C++ like this.
It's actually not necessary to check all the divisors like that. Instead, you can write a loop like this:
The reason this works (without division issues) is because the intermediate result at the end of a loop iteration is $$$C(n, i)$$$, which we know is an integer.
In E, how does the dp definition and state transition ensure that we'll get two same length A' and B' after some operations for each subproblem ?
Sorry for the late response, but this is a classical problem. We ensure that we get A' and B' of the same length, as previous states have equal lengths too. We either have two equal/unequal elements at the end (which goes back to $$$dp_{i-1,j-1}$$$ [+1 if unequal]), delete an element from A' (going back to $$$dp_{i-1,j}$$$), or delete an element from B' (going back to $$$dp_{i,j-1}$$$). You can read more about it on page 74 of CPH.
No worries. Thanks for the reference :) I understand the logic now.