Hi everyone!↵
↵
Thank you for joining [Weekly Training Farm 19](http://codeforces.me/group/gRkn7bDfsN/contest/210950).↵
I am going to refer to good-quality participants' codes in the editorial.↵
Please let me know if you feel so shy and want me to remove the linksThe solution codes will be uploaded later.↵
↵
Congratulations to:↵
↵
* The winner: [user:zscoder,2017-01-02]↵
* The runner up: [user:eddy1021,2017-01-02]↵
* 3rd place: [user:arosusti,2017-01-02]↵
↵
[Problem A. Aligned Text](http://codeforces.me/group/gRkn7bDfsN/contest/210950/problem/A)↵
------------------↵
↵
This problem is equivalent to finding the longest arithmetic progression of a given set $S$.↵
We can always enumerate the common difference $w$ and use another loop to find the maximum length.↵
↵
* A directed $O(n^3)$ implementation here [submission:23482870] by [user:iloveIMO,2017-01-02].↵
* An $O(n^2)$ method here [submission:23486085] by [user:aaaaajack,2017-01-02].↵
↵
[Problem B. Bitcount](http://codeforces.me/group/gRkn7bDfsN/contest/210950/problem/B)↵
------------------↵
↵
If we want to count something that can be represented as a sum of values taken within an interval $[a, b]$, we can always translate them as $count([a, b]) = count([0, b]) - count([0, a-1])$. Usually this will make the implementation easier (and safer).↵
↵
Moreover, in this problem, we can even deal with each binary digit separately. Hence, given an upper bound $m$ ($=b$ or $=a-1$) and a position $0\le i\le \lceil \log m\rceil$, we can focus on counting the number of $1$-bits in the $i$-th position between $1$ and $m$.↵
↵
* An $O(\log b)$ implementation here [submission:23482876] by [user:zscoder,2017-01-02].↵
↵
[Problem C. Crossing River](http://codeforces.me/group/gRkn7bDfsN/contest/210950/problem/C)↵
-----------------↵
↵
There are "forward" methods and "reversed" methods. The "forward" idea is to identify $dp[i]$ to be the smallest possible jumping gap from the left river bank to the $i$-th rock. However, the table is not easy to build in $O(n\log n)$ time. Although I believe it is achievable using `set` iterators, but no one use it during the contest =)↵
↵
The key to this problem is to use the "reversed" idea: binary search. We first guess an answer $m$ and then decide if the frog can cross the river with jumping distance no more than $m$. There are several way to do this. The first idea (coincident to the author's solution) is to use the sliding window technique: keeping all reachable rocks within the range $[i-m, i-1]$. If any of these rocks has value less or equal to $a_i$, then the $i$-th stone is reachable. We can use a deque to achieve linear time testing given $m$.↵
↵
The second idea is to first sort the rocks according to their values: we don't need sliding windows anymore! <s>We use sliding ubuntu!</s> Then, we greedily consider each rock in the order of their values, if we can jump furtherer, we jump. This solution is simpler and looks elegant to me.↵
↵
* Binary Search + Deque implementation here [submission:23483430] by [user:eddy1021,2017-01-02].↵
* Binary Search + Sweep Line (Sorted Order) implementation here [submission:23483064] by [user:zscoder,2017-01-02].↵
* There are other solutions uses BIT or sets, make acceptable $O(n\log^2 n)$ solutions.↵
↵
[Problem D. Dice Rolling](http://codeforces.me/group/gRkn7bDfsN/contest/210950/problem/D)↵
-----------------↵
↵
Tricky case-study problem. Define the opposite faces as a "set". The key to this problem is the following lemma:↵
↵
**Lemma:** Let $\{l, r\}$ be a "set". In any dice rolling sequence, between two occurrence of $l$ there must exist an $r$.↵
↵
So, let the $sum$ be the sum of two numbers in a "set", the answer must be a multiple of $sum$ plus some remaining extra (at most three) larger number in some sets. So the special cases started by studying $n=1$ or $m=1$, then $n=2$ or $m=2$, then $n\ge 3$ and $m\ge 3$. The very special case is when $(n,m)=(2,4)$ or $(4,2)$.↵
↵
* Solution here [submission:23487756] by [user:aaaaajack,2017-01-02].↵
↵
[Problem E. Escaped String](http://codeforces.me/group/gRkn7bDfsN/contest/210950/problem/E)↵
-----------------↵
↵
At first glance, it seems to be a classical $O(n^2)$ dynamic programming: $dp[i][j]$ is defined to be the shortest possible length of subsequence $s$ of $A[0..i]$ and the **first** occurrence in string $B$ as a subsequence ending at $j$-th character. Then we have the following:↵
↵
* $dp[i][j] = dp[i-1][j]$, if $A[i]\neq B[j]$.↵
* $dp[i][j] = \min\{dp[i-1][j], dp[i-1][prev_B(j-1, A[i-1])]\}$, if $A[i] = B[j]$, where $prev_B(j-1, A[i-1])$ is the previous occurrence of $A[i-1]$ appear in string $B$ before index $j-1$.↵
↵
However, this needs an $O(n^2)$ size memory, which is unaffordable. By observing that the dynamic programming state is meaningful only when $A[i]=B[j]$, we can use a memory efficient encoding for storing these DP states. Please refer to [My code](https://gist.github.com/tmt514/ab9a5d4e02796beb7fd1514b39449352) for implementation.↵
↵
The second solution is to notice that the answer is always less or equal to $1+$ the maximum occurrence of any single letter (i.e., $\le 501$). This is because one can greedily choose the character $\alpha$ such that the index that the "next $\alpha$" occurring in $A$ $\le$ the index of the "next $\alpha$" occurring in $B$, among these character we choose the largest indexed $\alpha$ in $B$. It gives us a solution of length no more than $501$. Now, we can use the LIS idea: let $dp[i][\ell]$ to be the largest index $j$ in $B$ such that there exists a subsequence of $A[0..i]$ of length $\ell$ occurs in $B[0..j]$ but not $B[0..j-1]$.↵
↵
Then the recurrence relation is:↵
$dp[i][\ell] = \max\{dp[i-1][\ell], next_B(dp[i][\ell-1], A[i])\}$.↵
↵
* Solution here [submission:23488373] by [user:aaaaajack,2017-01-02].↵
* Solution here [submission:23484579] by [user:arosusti,2017-01-02].
↵
Thank you for joining [Weekly Training Farm 19](http://codeforces.me/group/gRkn7bDfsN/contest/210950).↵
Please let me know if you feel so shy and want me to remove the links
↵
Congratulations to:↵
↵
* The winner: [user:zscoder,2017-01-02]↵
* The runner up: [user:eddy1021,2017-01-02]↵
* 3rd place: [user:arosusti,2017-01-02]↵
↵
[Problem A. Aligned Text](http://codeforces.me/group/gRkn7bDfsN/contest/210950/problem/A)↵
------------------↵
↵
This problem is equivalent to finding the longest arithmetic progression of a given set $S$.↵
We can always enumerate the common difference $w$ and use another loop to find the maximum length.↵
↵
* An $O(n^2)$ method here [submission:23486085] by [user:aaaaajack,2017-01-02].↵
↵
------------------↵
↵
If we want to count something that can be represented as a sum of values taken within an interval $[a, b]$, we can always translate them as $count([a, b]) = count([0, b]) - count([0, a-1])$. Usually this will make the implementation easier (and safer).↵
↵
Moreover, in this problem, we can even deal with each binary digit separately. Hence, given an upper bound $m$ ($=b$ or $=a-1$) and a position $0\le i\le \lceil \log m\rceil$, we can focus on counting the number of $1$-bits in the $i$-th position between $1$ and $m$.↵
↵
↵
-----------------↵
↵
There are "forward" methods and "reversed" methods. The "forward" idea is to identify $dp[i]$ to be the smallest possible jumping gap from the left river bank to the $i$-th rock. However, the table is not easy to build in $O(n\log n)$ time. Although I believe it is achievable using `set` iterators, but no one use it during the contest =)↵
↵
The key to this problem is to use the "reversed" idea: binary search. We first guess an answer $m$ and then decide if the frog can cross the river with jumping distance no more than $m$. There are several way to do this. The first idea (coincident to the author's solution) is to use the sliding window technique: keeping all reachable rocks within the range $[i-m, i-1]$. If any of these rocks has value less or equal to $a_i$, then the $i$-th stone is reachable. We can use a deque to achieve linear time testing given $m$.↵
↵
The second idea is to first sort the rocks according to their values: we don't need sliding windows anymore! <s>We use sliding ubuntu!</s> Then, we greedily consider each rock in the order of their values, if we can jump furtherer, we jump. This solution is simpler and looks elegant to me.↵
↵
* Binary Search + Sweep Line (Sorted Order) implementation here [submission:23483064] by [user:zscoder,2017-01-02].↵
↵
[Problem D. Dice Rolling](http://codeforces.me/group/gRkn7bDfsN/contest/210950/problem/D)↵
-----------------↵
↵
Tricky case-study problem. Define the opposite faces as a "set". The key to this problem is the following lemma:↵
↵
**Lemma:** Let $\{l, r\}$ be a "set". In any dice rolling sequence, between two occurrence of $l$ there must exist an $r$.↵
↵
So, let the $sum$ be the sum of two numbers in a "set", the answer must be a multiple of $sum$ plus some remaining extra (at most three) larger number in some sets. So the special cases started by studying $n=1$ or $m=1$, then $n=2$ or $m=2$, then $n\ge 3$ and $m\ge 3$. The very special case is when $(n,m)=(2,4)$ or $(4,2)$.↵
↵
[Problem E. Escaped String](http://codeforces.me/group/gRkn7bDfsN/contest/210950/problem/E)↵
-----------------↵
↵
At first glance, it seems to be a classical $O(n^2)$ dynamic programming: $dp[i][j]$ is defined to be the shortest possible length of subsequence $s$ of $A[0..i]$ and the **first** occurrence in string $B$ as a subsequence ending at $j$-th character. Then we have the following:↵
↵
* $dp[i][j] = dp[i-1][j]$, if $A[i]\neq B[j]$.↵
* $dp[i][j] = \min\{dp[i-1][j], dp[i-1][prev_B(j-1, A[i-1])]\}$, if $A[i] = B[j]$, where $prev_B(j-1, A[i-1])$ is the previous occurrence of $A[i-1]$ appear in string $B$ before index $j-1$.↵
↵
However, this needs an $O(n^2)$ size memory, which is unaffordable. By observing that the dynamic programming state is meaningful only when $A[i]=B[j]$, we can use a memory efficient encoding for storing these DP states. Please refer to [My code](https://gist.github.com/tmt514/ab9a5d4e02796beb7fd1514b39449352) for implementation.↵
↵
The second solution is to notice that the answer is always less or equal to $1+$ the maximum occurrence of any single letter (i.e., $\le 501$). This is because one can greedily choose the character $\alpha$ such that the index that the "next $\alpha$" occurring in $A$ $\le$ the index of the "next $\alpha$" occurring in $B$, among these character we choose the largest indexed $\alpha$ in $B$. It gives us a solution of length no more than $501$. Now, we can use the LIS idea: let $dp[i][\ell]$ to be the largest index $j$ in $B$ such that there exists a subsequence of $A[0..i]$ of length $\ell$ occurs in $B[0..j]$ but not $B[0..j-1]$.↵
↵
Then the recurrence relation is:↵
$dp[i][\ell] = \max\{dp[i-1][\ell], next_B(dp[i][\ell-1], A[i])\}$.↵
↵
* Solution here [submission:23484579] by [user:arosusti,2017-01-02].
