When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

Vivek1998299's blog

By Vivek1998299, history, 5 years ago, In English

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.

  • Vote: I like it
  • +70
  • Vote: I do not like it

| Write comment?
»
5 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Clashes with today's CF round.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +25 Vote: I do not like it

    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.

»
5 years ago, # |
  Vote: I like it +23 Vote: I do not like it

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

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +56 Vote: I do not like it

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

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

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

How to solve hard(editorial link preferably)

  • »
    »
    5 years ago, # ^ |
    Rev. 3   Vote: I like it +46 Vote: I do not like it

    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}}$$$

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

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

»
5 years ago, # |
  Vote: I like it +10 Vote: I do not like it

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).

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