Asia West, India, NIT Trichy, gupta_nitin, rishabnahar2025, ritik_m

1) Pick any spanning tree and root at node $$$1$$$.

2) Pick the node having the max depth, go up $$$\sqrt{n}$$$ for that node following parents, push this one in the answer, and remove that subtree.

3) Do step 2 until the tree is not empty.

I understand $$$O(n^{2}*2^{n})$$$ solution but how to do in $$$O(n*2^{n})$$$ ?

NVM, got it.

Enjoyed the contest!

Sorry for that, we made it independently and didn't expect link cut tree solution; yeah our solution is little simple based on Query Sqrt decomposition.

Reminder: Contest starts in less than 1 hour.

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

Lets assume p is probability of alice winning then

1) alice choose white ball :- ( W/(W+B) )*( 1-p )

2) alice choose black ball:- all pattern of type BWB, BWWWB, BWWWWWB....this will become infinite Geometric progression.

Add these two, you will get the answer.

Code

i guessed the pattern lol!

k = n-k-1

Ans = (n-1)! *( 1/(n-1) + 2/(n-2) + 3/(n-3) +...+ k/(n-k) )

Apologies for unclear statement, as max value of d[i] is 7, if we know answer of l length prefix then we can expand it to get the answer of l+1 length prefix, but for it we need the order the previous 7 element ( l,l-1,l-2...l-6), in which we eat them. now we can put l+1 th element inbetween 8 position among these 7 element. so dp state is the [index , order of previous of 7 element], now order of previous 7 element can be among 7! ways in which we can order them. So number of states can be upto n*7!. code

in Sweet change, for ith position you only need order(in which we eat them) of no more that 7 last element,so can be solved using dp with number of state being n*(7!).

We don't need to find x,y,z in problem D because any three node will given us answer , so take first and second and third node and now in a loop 1->2->3->1 there will be atleast two continuous edges which are equal, this will make implementation easy , you can see my submission 106600375

Every time you can remove k-1 elements so count of numbers you want to remove must be divisible by k-1 and now when count of numbers is >k-1 , you can bring them down to k-1 by applying operation between them now if any b[i] is having (k-1)/2 elements in left and (k-1)/2 in right you can do last removal ok k-1 elements so ultimately you just need to check that atleast one b[i] should have >=(k-1)/2 elements in left and in right also. English is not so good :(

Got it,thanks!

Can You Please Explain, why it repeats.