15

LINE Verda Programming Contest（AtCoder Beginner Contest 263） Announcement

 2 years ago
source link: http://codeforces.com/blog/entry/105625
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

LINE Verda Programming Contest（AtCoder Beginner Contest 263） Announcement

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!

33 hours ago, # |

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

33 hours ago, # |

H/Ex is pretty similar to this problem: 1446F - Расстояние до прямой.

32 hours ago, # |

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.1. Make bipartite graph with 2n+22n+2 nodes. One node for source SS, one for sink TT and all aiai have one node in the left and one node in the right part.

2.2. Make edges between aiai in left part and ajaj in right part for all ii and jj if ai+ajai+aj is prime number with +∞+∞ capacity.

3.3. Make edges from SS to aiai in left part with the capacity bibi.

4.4. Make edges from all aiai in right part to TT with the capacity bibi.

5.5. Find maximum flow and divide this number by 22. This is the answer.

  • 13 hours ago, # ^ |

    ← Rev. 2 →  

    0

    Wow, that's a great simple answer! I came up with a proof.

    Let fefe be the amount of flow on edge ee. Let LiLi and RiRi be vertex aiai in the left and right part, respectively. For simplicity suppose a1=1a1=1. If there is no such aiai in the input, insert (a1,b1)=(1,0)(a1,b1)=(1,0).

    Take an optimal solution that erases (ai,aj)(ai,aj)cijcij times. Here i=ji=j iff i=1i=1. Assume i<ji<j otherwise. Let Ci=∑j>1cijCi=∑j>1cij (ignoring the order of indices of cc). Then

    fSL1=fR1T=2c11+C1≤b1,fSLi=fRiT=Ci(i>1),fLiRj={2c11cij(i=j=1)(i≠j)fSL1=fR1T=2c11+C1≤b1,fSLi=fRiT=Ci(i>1),fLiRj={2c11(i=j=1)cij(i≠j)

    is a valid flow of total amount F=2∑i≤jcijF=2∑i≤jcij.

    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 SS to TT on the residue graph. Suppose that such a path SLe1Re2⋯Le2M−1Re2MTSLe1Re2⋯Le2M−1Re2MT exists. There are at most one mm such that e2m=e2m+1=1e2m=e2m+1=1. - If such mm exists, consider the parity of FF. — If FF is even, then it increases FF by one. Now b1b1 is odd and bibi(i>1)(i>1) is even. - If FF is odd, then it contradicts to the optimality: instead of erasing (ae2,ae3),(ae4,ae5),…,(ae2m−2,ae2m−1),(ae2m+2,ae2m+3),…,(ae2M−2,ae2M−1(ae2,ae3),(ae4,ae5),…,(ae2m−2,ae2m−1),(ae2m+2,ae2m+3),…,(ae2M−2,ae2M−1, we can erase one more pair by chosing (ae1,ae2),(ae3,ae4),…,(ae2m−1,ae2m),(ae2m+2,ae2m+3),…,(ae2M−1,ae2M)(ae1,ae2),(ae3,ae4),…,(ae2m−1,ae2m),(ae2m+2,ae2m+3),…,(ae2M−1,ae2M). - If such mm does not exist, then am≢am+1(mod2)am≢am+1(mod2), so a1≠ama1≠am. But it contradicts to the optimality: instead of erasing (ae2,ae3),(ae4,ae5),…,(ae2M−2,ae2M−1(ae2,ae3),(ae4,ae5),…,(ae2M−2,ae2M−1, we may erase one more pair by chosing (ae1,ae2),(ae3,ae4),…,(ae2M−1,ae2M)(ae1,ae2),(ae3,ae4),…,(ae2M−1,ae2M) Therefore ⌊F/2⌋⌊F/2⌋ is always the optimal answer.

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK