chokudai's blog

LINE Verda Programming Contest（AtCoder Beginner Contest 263） Announcement
By chokudai, history, 2 years ago, In English

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!

  • Vote: I like it
  • +72
  • Vote: I do not like it

Comments Comments (18)
| Write comment?
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For problem E, standard dp involves calculating sum of fraction,which is O(n^2). How to improve further?

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    use fenwick

    → Reply
  • »
    »
    2 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you give deep explanation of E. I am not able to understand what you tried to say

      → Reply
      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it +10 Vote: I do not like it

        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.

        → Reply
      • »
        »
        »
        »
        2 years ago, # ^ |
        ← Rev. 4   Vote: I like it +3 Vote: I do not like it

        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.

        → Reply
        • »
          »
          »
          »
          »
          2 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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.

          → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      neat!

      → Reply
»
2 years ago, # |
  Vote: I like it +16 Vote: I do not like it

H/Ex is pretty similar to this problem: 1446F - Line Distance.

→ Reply
»
2 years ago, # |
  Vote: I like it +27 Vote: I do not like it

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.

→ Reply
  • »
    »
    2 years ago, # ^ |
    ← Rev. 2   Vote: I like it +11 Vote: I do not like it

    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

    $$$ 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.

    → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

E is a Markov Chain problem.
This editorial (in Japanese) is very good: https://atcoder.jp/contests/abc263/editorial/4552

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    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).

    → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Could someone please explain problem D, like how do we calculate the minimum sum in O(n) ?

→ Reply
  • »
    »
    2 years ago, # ^ |
    ← Rev. 2   Vote: I like it +8 Vote: I do not like it

    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.

    → Reply
»
2 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Can anyone please share their approach for problem F

→ Reply