USACO 2019 December Contest, Platinum

Problem 3. Tree Depth

Contest has ended.

Log in to allow submissions in analysis mode

For the new year, Farmer John decided to give his cows a festive binary search tree (BST)!

To generate the BST, FJ starts with a permutation $a=\{a_1,a_2,\ldots,a_N\}$ of the integers $1\ldots N$, where $N\le 300$. He then runs the following pseudocode with arguments $1$ and $N.$

  if l > r, return empty subtree;
  x = argmin_{l <= i <= r} a_i; // index of min a_i in {a_l,...,a_r}
  return a BST with x as the root, 
    generate(l,x-1) as the left subtree,
    generate(x+1,r) as the right subtree;

For example, the permutation $\{3,2,5,1,4\}$ generates the following BST:

   / \
  2   5
 / \ 
1   3

Let $d_i(a)$ denote the depth of node $i$ in the tree corresponding to $a,$ meaning the number of nodes on the path from $a_i$ to the root. In the above example, $d_4(a)=1, d_2(a)=d_5(a)=2,$ and $d_1(a)=d_3(a)=3.$

The number of inversions of $a$ is equal to the number of pairs of integers $(i,j)$ such that $1\le i<j\le N$ and $a_i>a_j.$ The cows know that the $a$ that FJ will use to generate the BST has exactly $K$ inversions $(0\le K\le \frac{N(N-1)}{2})$. Over all $a$ satisfying this condition, compute the remainder when $\sum_ad_i(a)$ is divided by $M$ for each $1\le i\le N.$


The only line of input consists of three space-separated integers $N, K,$ and $M$, followed by a new line. $M$ will be a prime number in the range $[10^8,10^9+9].$

OUTPUT FORMAT (file treedepth.out):

Print $N$ space-separated integers denoting $\sum_ad_i(a)\pmod{M}$ for each $1\le i\le N.$


  • Test cases 3-4 satisfy $N\le 8.$
  • Test cases 5-7 satisfy $N\le 20.$
  • Test cases 8-10 satisfy $N\le 50.$


3 0 192603497


1 2 3 

Here, the only permutation is $a=\{1,2,3\}.$


3 1 144408983


3 4 4 

Here, the two permutations are $a=\{1,3,2\}$ and $a=\{2,1,3\}.$

Problem credits: Yinzhan Xu

Contest has ended. No further submissions allowed.