We will hold LINE Verda Programming Contest（AtCoder Beginner Contest 263）.
- Contest URL: https://atcoder.jp/contests/abc263
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20220806T2100&p1=248
- Duration: 100 minutes
- Number of Tasks: 8
- Writer: PCTprobability, nok0, m_99, blackyuki, YoshikaMiyafuji
- Tester: Nyaan, kyopro_friends
- Rated range: ~ 1999
The point values will be 100-200-300-400-500-500-600-600. We are looking forward to your participation!
For problem E, standard dp involves calculating sum of fraction,which is O(n^2). How to improve further?
use fenwick
We can calculate the expected values in cell n-1 .. 1. Then ans=e[1]
$$$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.
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 - Line Distance.
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.
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 $$$i<j$$$ otherwise. Let $$$C_i = \sum_{j>1} c_{ij}$$$ (ignoring the order of indices of $$$c$$$). Then
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) ?
Just think of prefix and suffix sums.
Hope, you liked it.
Thanks!
btw prefix[i] = min(prefix[i-1]+arr[i],i*L) and not max.
Yeah, I updated!
Can anyone please share their approach for problem F