Блог пользователя chokudai

Автор chokudai, история, 20 месяцев назад, По-английски

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!

  • Проголосовать: нравится
  • +72
  • Проголосовать: не нравится

»
20 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    20 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    use fenwick

  • »
    »
    20 месяцев назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    • »
      »
      »
      20 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        20 месяцев назад, # ^ |
          Проголосовать: нравится +10 Проголосовать: не нравится

        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.

      • »
        »
        »
        »
        20 месяцев назад, # ^ |
        Rev. 4   Проголосовать: нравится +3 Проголосовать: не нравится

        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.

        • »
          »
          »
          »
          »
          20 месяцев назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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.

    • »
      »
      »
      20 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      neat!

»
20 месяцев назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

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

»
20 месяцев назад, # |
  Проголосовать: нравится +27 Проголосовать: не нравится

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.

  • »
    »
    20 месяцев назад, # ^ |
    Rev. 2   Проголосовать: нравится +11 Проголосовать: не нравится

    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.

»
20 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    20 месяцев назад, # ^ |
      Проголосовать: нравится +9 Проголосовать: не нравится

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

»
20 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    20 месяцев назад, # ^ |
    Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

    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.

»
20 месяцев назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Can anyone please share their approach for problem F