Hey All!

Topcoder SRM 763 is scheduled to start at 11:00 UTC-4, July 17, 2019. Registration is now open for the SRM in the Web Arena or Applet and will close 5 minutes before the match begins.

Problems were invented and prepared by me and Slow_But_Determined. Thanks to misof for his help with the statements and testing.

Good luck to everyone!

**UPD**: The editorials will be posted soon. Meanwhile, you can go through the Author's notes here.

Clashes with today's CF round.

Sorry about that. This was some kind of unintentional scheduling snafu, MikeMirzayanov somehow missed the existence of this TC round when scheduling the CF round, probably because some data wasn't up to date somewhere. We try to look avoid such clashes but sometimes mistakes happen.

By the way, the SRM 731 Editorial was written by me, and published recently. Let's look at it if you want to :)

Does TC still pay for editorialist (and how much)? Who should I contact for?

Please get in touch with hmehta, he can give you the details.

Hey ko_osaga, Feel free to ping me (harshit@topcoder.com) whenever you are available to cover the editorials. We pay $100 for penning the editorials for a complete round. :)

How to solve hard(editorial link preferably)

Let $$$D_k$$$ be the sum of product of $$$C_i$$$ taken $$$k$$$ at a time. $$$D$$$ can be found in $$$O(n \log^2 n)$$$ by finding $$$\prod (x + C_i)$$$.

Now, by symmetry, for any subset $$$S$$$ of $$$[n]$$$ of size k, $$$E[ \prod_{i \in S} x_i] = E [ \prod_{i=1}^{k} x_i] $$$. So, expanding the product, we have:

$$$ E [ \prod_{i=1}^{n} (C_i + x_i)] = \sum_{k=0}^{n} D_{n-k} E [ \prod_{i=1}^{k} x_i] $$$

So, we have to find sum of $$$\prod_{i=1}^{k} x_i$$$ over all n-tuples $$$x$$$ summing to m. One way to solve this is using generating functions ( by finding coefficient of $$$x^m$$$ in $$$(\sum i x ^ i) ^ k (\sum x ^ i) ^ {n - k} = (\frac{x}{(1-x)^2})^k (1-x)^{k-n})$$$). Another way is this:

Consider a line segment of length $$$m$$$ to be divided into $$$n$$$ integral parts. For each of the first $$$k$$$ segments you have to cut it in two parts at an integer point not coinciding with its left end. The number of ways to do this is our answer (as we have $$$x_i$$$ choices to cut a segment of length $$$x_i$$$). Equivalently, you have $$$n + k$$$ segments, with $$$k$$$ of them which must be non zero. This gives $$$\binom{n + m - 1}{m - k}$$$.

So, you have to find $$$\displaystyle \dfrac{\sum D_{n-k} \binom{n + m - 1}{m - k}}{ \binom{n+m-1}{n-1}}$$$

Wow!! Thanx for sharing your solution :)

Auto comment: topic has been updated by Vivek1998299 (previous revision, new revision, compare).What is the stack size for Java solutions at TopCoder nowadays? The Div1 Medium can be solved with a (recursively implemented) depth-first search but this is not obvious because the stack was too small as late as at TCO 2019 1B (problem EllysTeleport).

https://community.topcoder.com/stat?c=problem_solution&rm=332894&rd=17614&pm=15563&cr=22704094 isn't this just brute force solution for ETsums problem .

Yeah, it is...That's why it fails the system test :)