JayZhan's blog

By JayZhan, history, 6 years ago, In English

Div2 894E — Ralph and Mushrooms

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

  • Vote: I like it
  • -13
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by JayZhan (previous revision, new revision, compare).

»
6 years ago, # |
  Vote: I like it +14 Vote: I do not like it

What should this be? A question, a tutorial, ...?

In any case, it wouldn't hurt if you format your text a little bit, and use capitalization and punctuation. And you don't need to start a new paragraph for every sentence.

Also two small errors: The total formula is (you wrote it with is). And in the example n is 3, not 4.