Div2↵
[894E — Ralph and Mushrooms](http://codeforces.com/problemset/problem/894/E) ↵
↵
as we know we can find cycle and contract to a point to make the graph become DAG↵
↵
but tutorial dont explain about finding mushrooms in the cycle by math knowledge↵
↵
I have read some one's code and the math is as the follow ↵
↵
IF I HAVE MISTAKE WELLCOME TO TELL ME! THX↵
↵
walk through the cycle me can get the max mushrooms as we could↵
↵
because we can still pass it though we get 0 mushroom so we can get all the mushrooms↵
↵
mushrooms decrease by 1,2,3...n↵
↵
for the initial mushrooms w↵
↵
i-th time you get w-i(i+1)/2↵
↵
for every w suppose you can get mushrooms n time↵
↵
↵
w,w-1,w-1-2,w-1-2-3...w-(1+2..n)↵
↵
which is w*(n+1)-[i(i+1)/2 i for 0 to n]↵
↵
-> w(n+1)-i(i+1)(i+2)/6↵
↵
see here https://en.wikipedia.org/wiki/Tetrahedral_number↵
↵
and the way to find n↵
↵
we have w already↵
↵
to make it simple↵
↵
consider w is one of the i(i+1)/2↵
↵
8*w↵
↵
=4*i(i+1)↵
↵
=4i^2+4i↵
↵
8*w+1=(2i+1)^2↵
↵
sqrt(8*w+1)-1=2i↵
↵
[sqrt(8*w+1)-1]/2=2i/2=i↵
↵
which is what we want,i is the max times to get mushroom↵
↵
for any w get floor for the ans↵
↵
c++↵
↵
n is the max times to get mushroom↵
↵
int n= floor((sqrt(1+8*w)-1)/2);↵
↵
sum_mushroom=(n+1)*w — n*(n+1)*(n+2)/6;↵
↵
i.e.↵
↵
w=9↵
↵
9,8,6,3,-1↵
↵
9,9,9,9,9 (+ plus↵
↵
0,1,3,6,10 (- minus↵
↵
n is 4↵
↵
9*(4+1)-(0+1+(1+2)+(1+2+3)+(1+2+3+4))↵
↵
=9+8+6+3=26
[894E — Ralph and Mushrooms](http://codeforces.com/problemset/problem/894/E) ↵
↵
as we know we can find cycle and contract to a point to make the graph become DAG↵
↵
but tutorial dont explain about finding mushrooms in the cycle by math knowledge↵
↵
I have read some one's code and the math is as the follow ↵
↵
IF I HAVE MISTAKE WELLCOME TO TELL ME! THX↵
↵
walk through the cycle me can get the max mushrooms as we could↵
↵
because we can still pass it though we get 0 mushroom so we can get all the mushrooms↵
↵
mushrooms decrease by 1,2,3...n↵
↵
for the initial mushrooms w↵
↵
i-th time you get w-i(i+1)/2↵
↵
for every w suppose you can get mushrooms n time↵
↵
↵
w,w-1,w-1-2,w-1-2-3...w-(1+2..n)↵
↵
which is w*(n+1)-[i(i+1)/2 i for 0 to n]↵
↵
-> w(n+1)-i(i+1)(i+2)/6↵
↵
see here https://en.wikipedia.org/wiki/Tetrahedral_number↵
↵
and the way to find n↵
↵
we have w already↵
↵
to make it simple↵
↵
consider w is one of the i(i+1)/2↵
↵
8*w↵
↵
=4*i(i+1)↵
↵
=4i^2+4i↵
↵
8*w+1=(2i+1)^2↵
↵
sqrt(8*w+1)-1=2i↵
↵
[sqrt(8*w+1)-1]/2=2i/2=i↵
↵
which is what we want,i is the max times to get mushroom↵
↵
for any w get floor for the ans↵
↵
c++↵
↵
n is the max times to get mushroom↵
↵
int n= floor((sqrt(1+8*w)-1)/2);↵
↵
sum_mushroom=(n+1)*w — n*(n+1)*(n+2)/6;↵
↵
i.e.↵
↵
w=9↵
↵
9,8,6,3,-1↵
↵
9,9,9,9,9 (+ plus↵
↵
0,1,3,6,10 (- minus↵
↵
n is 4↵
↵
9*(4+1)-(0+1+(1+2)+(1+2+3)+(1+2+3+4))↵
↵
=9+8+6+3=26
