Rating changes for last rounds are temporarily rolled back. They will be returned soon. ×

YocyCraft's blog

By YocyCraft, history, 7 weeks ago, In English

Problem link:1785D - Деревянная ложка

First, WLOG we can assume we arrange the tournament in such way: In every matches, the left player wins. We can achieve this by doing the following operation to the binary tree of the tournament: for each non-leaf node of the binary tree, if the winner of this node is its right child, we "flip" this node by swapping its left subtree and right subtree. Since fliping doesn't change the winner of each match, this will not change the "wooden spoon", and after this operation, the "wooden spoon" is the right-most node. Since there are $$$2^{n}-1$$$ nodes in the binary tree, we can merge $$$2^{2^n-1}$$$ situations into one by this operation.

For example, we can do operation to this tree:










Where $$$1$$$ (the left-most node) is the champion, and $$$7$$$ (the right-most node) is the "wooden spoon".

Then we assume the right-most node is k, and there's $$$dp[n][k]$$$ different arrangements (after operation). If $$$k$$$ is the $$$j$$$-th smallest element in the right half of the tree, then we have $$$\sum_{i=1}^{2^{n-1}}dp[n-1][i]$$$ ways to arrange the left half, and $$$dp[n-1][j]$$$ ways to arrange the right half (since $$$k$$$ is also the right-most node in the right-subtree). But in how many ways we can distribute $$$2^{n}$$$ elements into $$$2$$$ halves? Well, since $$$1$$$ is the left-most element, there are $$$k-2$$$ elements we could put in the right part (which are in the range $$$[2, k-1]$$$), and there are actually $$$j-1$$$ elements of them in the right part, so we have $$$\binom{k-2}{j-1}$$$ ways to choose them. Similarly, we have $$$\binom{2^{n}-k}{2^{n-1}-j}$$$ ways to choose elements from $$$[k+1, 2^k]$$$. Therefore, we can get such formula:

$$$dp[n][k]=\displaystyle \sum_{j=1}^{2^{n-1}}(\displaystyle \sum_{i=1}^{2^{n-1}}dp[n-1][i]) \cdot dp[n-1][j] \cdot \binom{k-2}{j-1} \cdot \binom{2^{n}-k}{2^{n-1}-j}$$$

Then we can calculate them by FFT. The answer is $$$2^{2^{n}-1} \cdot dp[n][k]$$$.

Code example
  • Vote: I like it
  • +42
  • Vote: I do not like it

7 weeks ago, # |
Rev. 5   Vote: I like it +22 Vote: I do not like it

Note that the problem can be solved without FFT.

Let's calculate the probability the leaf on the left is the wooden spoon (then, multiply by $$$2^n$$$).

Let the "$$$i$$$-th" block be the right subtree of the $$$(n-i+1)$$$-th node in the leftmost path (so, blocks contain nodes in positions $$$[1, 1], [2, 2], [3, 4], [5, 8], \dots$$$ from the left). The condition is "each block contains a prefix minimum" (here, a prefix also includes the blocks $$$[1, i-1]$$$).

Let dp[i][j] be the number of ways to put all the elements $$$[1, j-1]$$$ in blocks $$$> i$$$ (you will put $$$j$$$ in block $$$i$$$ later, and it will be the minimum of block $$$i$$$, and also a prefix minimum). The condition is now "for decreasing $$$i$$$, $$$j$$$ is strictly increasing". So, you must calculate dp[i][j] using transitions from dp[i + 1][k] with $$$k < j$$$.

Note that in the transitions formula there is no factor that depends both on $$$j$$$ and $$$k$$$. So, you can optimize the dp by calculating prefix sums of dp[i + 1][k] $$$\cdot \text{ } (\text{product of factors that depend on } k \text{ in the transition})$$$.

AC code: 192338327

  • »
    6 weeks ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    I don't think all elements [1,j-1] can be put in blocks > i since element 1 only belongs to the block 1? Terribly sorry for the trouble, but do I misunderstand something?

    • »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Good point. Don't arrange the tournament like in the solution above (i.e., don't let the left player win), and calculate the probability that the wooden spoon is the node on the left.