### chokudai's blog

By chokudai, history, 12 days ago, We will hold LINE Verda Programming Contest（AtCoder Beginner Contest 263）.

The point values will be 100-200-300-400-500-500-600-600. We are looking forward to your participation! Comments (19)
 » For problem E, standard dp involves calculating sum of fraction,which is O(n^2). How to improve further?
•  » » use fenwick
•  » » 11 days ago, # ^ | ← Rev. 2 →   We can calculate the expected values in cell n-1 .. 1. Then ans=e$e[n]=0$$e[i]=1+\frac{e[i]}{a[i]+1}+avg(e[i+1 .. i+a[i]])$$e[i]=(a[i]+1)\cdot\frac{1+avg(e[i+1 .. i+a[i]])}{a[i]}$The avg(...) is the the postfix sum of that segment, divided by the size of the segment.
•  » » » Can you give deep explanation of E. I am not able to understand what you tried to say
•  » » » » e[i] is the expected number of rolling the die if we are currently in cell i and want to end in cell n, like the problem suggests.
•  » » » » 11 days ago, # ^ | ← Rev. 4 →   Let, $dp_i$ = number of rolls needed to reach position $n$ starting from position $i$. Hence $dp_n = 0.$ $dp_i = \frac{(1 + dp_{i}) + (1 + dp_{i+1}) + \dots + (1 + dp_{i + a_i})} {(a_i + 1)}.$.If you solve the equation, you get $dp_i = \frac{a_i + 1 + (dp_{i+1}+\dots + dp_{i + a_i})} {a_i}.$.So you can traverse from $i = n - 1$ to $i = 0$ and calculate $dp_i$. To calculate the value of $dp_{i+1}+\dots + dp_{n + a_i}$ you can use fenwick tree or segment tree.
•  » » » » » Good explanation. I find it the most understandable solution explanation so far. Although, the last part can just be done with regular prefix sums which can be calculated on the fly.
•  » » » neat!
 » H/Ex is pretty similar to this problem: 1446F - Расстояние до прямой.
 » Somehow I solved problem G in a very strange manner. I can't find any other submissions similar to mine. During the contest I didn't prove my solution, so I don't know why it works. Can someone explain me why it works? Of course, if it works (submission).My solution is very short (shorter than any other I saw). I didn't divide numbers into even of odd or something like this. I just did five steps:$1.$ Make bipartite graph with $2n + 2$ nodes. One node for source $S$, one for sink $T$ and all $a_i$ have one node in the left and one node in the right part. $2.$ Make edges between $a_i$ in left part and $a_j$ in right part for all $i$ and $j$ if $a_i + a_j$ is prime number with $+\infty$ capacity.$3.$ Make edges from $S$ to $a_i$ in left part with the capacity $b_i$. $4.$ Make edges from all $a_i$ in right part to $T$ with the capacity $b_i$.$5.$ Find maximum flow and divide this number by $2$. This is the answer.
•  » » 10 days ago, # ^ | ← Rev. 2 →   Wow, that's a great simple answer! I came up with a proof.Let $f_e$ be the amount of flow on edge $e$. Let $L_i$ and $R_i$ be vertex $a_i$ in the left and right part, respectively. For simplicity suppose $a_1=1$. If there is no such $a_i$ in the input, insert $(a_1, b_1) = (1, 0)$.Take an optimal solution that erases $(a_i, a_j)$ $c_{ij}$ times. Here $i=j$ iff $i=1$. Assume $i1} c_{ij}$ (ignoring the order of indices of $c$). Then $f_{SL_1} = f_{R_1T} = 2c_{11} + C_1 \leq b_1, \\ f_{SL_i} = f_{R_iT} = C_i \; (i > 1), \\ f_{L_i R_j} = \begin{cases} 2c_{11} & (i = j = 1) \\ c_{ij} & (i \neq j) \end{cases}$is a valid flow of total amount $F = \displaystyle 2\sum_{i \leq j} c_{ij}$.Now we show that this flow is nearly maximum, i.e. maximum flow is at most greater by one than the current total amount of flow.To see this we seek for a path from $S$ to $T$ on the residue graph. Suppose that such a path $S L_{e_1} R_{e_2} \cdots L_{e_{2M-1}} R_{e_{2M}} T$ exists. There are at most one $m$ such that $e_{2m} = e_{2m+1} = 1$. - If such $m$ exists, consider the parity of $F$. — If $F$ is even, then it increases $F$ by one. Now $b_1$ is odd and $b_i$ $(i > 1)$ is even. - If $F$ is odd, then it contradicts to the optimality: instead of erasing $(a_{e_2}, a_{e_3}), (a_{e_4}, a_{e_5}), \ldots, (a_{e_{2m-2}}, a_{e_{2m-1}}), (a_{e_{2m+2}}, a_{e_{2m+3}}), \ldots, (a_{e_{2M-2}}, a_{e_{2M-1}}$, we can erase one more pair by chosing $(a_{e_1}, a_{e_2}), (a_{e_3}, a_{e_4}), \ldots, (a_{e_{2m-1}}, a_{e_{2m}}), (a_{e_{2m+2}}, a_{e_{2m+3}}), \ldots, (a_{e_{2M-1}}, a_{e_{2M}})$. - If such $m$ does not exist, then $a_m \not\equiv a_{m+1} \pmod 2$, so $a_1 \neq a_m$. But it contradicts to the optimality: instead of erasing $(a_{e_2}, a_{e_3}), (a_{e_4}, a_{e_5}), \ldots, (a_{e_{2M-2}}, a_{e_{2M-1}}$, we may erase one more pair by chosing $(a_{e_1}, a_{e_2}), (a_{e_3}, a_{e_4}), \ldots, (a_{e_{2M-1}}, a_{e_{2M}})$ Therefore $\lfloor F/2 \rfloor$ is always the optimal answer.
 » E is a Markov Chain problem.This editorial (in Japanese) is very good: https://atcoder.jp/contests/abc263/editorial/4552
•  » » You just made me realize that user editorials in Japanese do not appear when the language is set to English. Nice to know. Maybe they should appear and just write in parentheses that they are written in Japanese. More people would find them useful even using a translator (assuming a lot of people didn't notice this like me).
 » Could someone please explain problem D, like how do we calculate the minimum sum in O(n) ?
•  » » 9 days ago, # ^ | ← Rev. 2 →   Just think of prefix and suffix sums. First calculate, the prefix sum as ${prefix_i = min(prefix_{i - 1} + arr_i, i * L)}$ Second calculate, the suffix sum as ${suffix_i = min(suffix_{i + 1} + arr_i, (n - i + 1) * R)}$ Ans is minimum over all ${prefix_i + suffix_{i + 1}, where}$ ${0 \le i \le n.}$ Hope, you liked it.
•  » » » Thanks! btw prefix[i] = min(prefix[i-1]+arr[i],i*L) and not max.
•  » » » » Yeah, I updated!
 » can anyone explain E?
 » Can anyone please share their approach for problem F