QwQ

You bought my participation with that anime picture XD

As a tester, I recommend reading all problems. GLHF!

Good luck in your achievement!!!

How did you get negative rating???

And the first place will lead to a very positive delta.

damn you're right

Good question. Maybe this round is a BIT difficult.

puts on glasses Theoretically you should not be telling this information to the participants since several individuals may theoretically be able to find out about the topics of the problems of this round by getting the statistics of topics where you're good at or not based on your performances on CF, please don't blame me if this situation will happen

Lyrically is a cute boy. I met him in Nanjing. He only studied OI for less than a year, but he can easily become a candidate master. This is incredible. From this, we can conclude that he is pretending to be weak (fAKe).

What does that mean? Lot of people say there is too much math in chinese rounds.

So Div.1 D's solution is very similar to NOIP2022 T4?

Yes

Yot can't participate in div 1 because your rating is lower that 1900, but you can freely participate in div 2 and it will affect you'r rating

orz

啊？

HAIL KEK!

awa

(And many DS.)

But these are all stereotypes. I think there will be many interesting problems, too.

Hope to enjoy the contest!

Seems a lot of OIers like vocaloid (including me).

But I don't really like the style of the illustrations...

awa

I hope its not in Chinese.

Just to suffer...

The moon shines, thank the moon.

The moon shines, thank the moon. YueLiangHaoShan, BaiXieYueLiang.

wa on pretest 2

Maybe it's Chinese Round.

D1 < C. Solve yeah you will become CM. just solve A, B, D1, C.

Really hard to get +137

-_-

orz

orz

orz

But it might be fit for Chinese oiers

Same buddy, I'm too weak in probability :(

It's not really about expectation. I mean it is but you don't have to know anything.

For k = 1 answer is obviously 1, for k = 3 the answer is also 1 (there is one point central point which is the intersection of paths A-B, A-C and B-C; this is the island you are looking for, if you move one step from it you can get closer to one island but further from 2 others).

So you need to solve only for k = 2. Calculate the sum of path lengths with standard tree dp and divide by number of paths (n-1)*n/2.

What did you find weird in this?

It is a common phenomenon to use memes in test cases, in fact

Edit:nevermind, i was answering for div2 b

I solved D1, for odd n answer is 1, how to solve D2,i know what to do but can't optimize it.

Consider the set of good vertices for fixed locations of the $$$k$$$ nodes. This set of good islands is always connected and, if there are $$$m$$$ good islands, between them there are $$$m-1$$$ edges. Try to calculate the expected number of edges between the good nodes instead of the expected number of the nodes. Or more specifically, try to calculate how many times each edge will be between two good nodes. The answer will be this plus 1.

Let's find the number of bad combinations with vertex $$$v$$$. Notice, that there should exists only 1 subtree with number of vertices from combination greater than $$$\frac{k}{2}$$$. So let's fix that subtree. Suppose size of this subtree is $$$s$$$. Then the number of bad combinations is $$$\sum_{i=1}^{k} \binom{s}{k+i} \binom{n-s}{k-i}$$$. We fix the number of vertices from combination in that subtree: $$$k+i$$$. Then choose them with $$$\binom{s}{k+i}$$$ ways. And multiply it with $$$\binom{n-s}{k-i}$$$ — number of ways to place other $$$k-i$$$ vertices not in that subtree. We need to calculate this sum for $$$O(n)$$$ sizes. You can rewrite this sum as $$$\sum_{i=k+1}^{s} \binom{i-1}{k} \binom{n-i}{k-1}$$$. Why? Consider the binary array with size $$$n$$$ and $$$k$$$ ones. Then this sum is the number of way to have $$$> \frac{k}{2}$$$ ones in the first $$$s$$$ positions. Let's fix the position of $$$k+1$$$ ones — call it $$$i$$$. Then we need to have $$$k$$$ ones on the left and $$$k-1$$$ on the right. Number of ways to choose left ones is $$$\binom{i-1}{k}$$$, on the right is $$$\binom{n-i}{k-1}$$$. The binomial coefficients do not depend on $$$s$$$, so you can calculate it fast with prefix sums.

How? That's way easier than regular D's. It's just counting total number of paths in a tree, and it's a very standard problem.

Actually how would one create a BIT to do those in O(N log N) time?

It is

I did not realize that lol. I took each node and determined how many different paths have that specific node as a valid one and summed all that up.

For C, I try this: Every non-leaf node which does not have more than 1 child can be compressed into it's descendant. I think if we do this we might be able to pass with dp[node][val], which gives minimum moves to make all leaves in subtree of node equal to val. Because height of tree after compressing is logarithmic. Idk if it will work I fail to implement in time