How can I fix my C++ code for counting unique binary trees with a specific height and number of nodes?

Question

I've been working on the USACO training problem Cow Pedigrees (see https://jvonk.github.io/usaco/2018/10/16/nocows.html for an explanation of the problem and a sample solution)

Basically, you have to count the number (mod 9901) of possibilities of unique binary trees with a number of nodes N and a height of K.

Here is the C++ code that I've tried so far. It outputs the correct answers for some smaller inputs like N = 5; K = 3 and N = 9; K = 4. However, once it got to the test case of N = 35 and K = 7, it outputs 7642 instead of the correct answer of 5024.

I cannot for the life of me figure out why that is, because my code all makes sense to me, and when I walk through the steps with smaller numbers it seems to be doing everything correctly and the same as if I did it manually. I think the issue is something to do with it double counting possibilities that should not be double counted (in the if else statement) but I can't figure out why that would be true.

I would really appreciate if someone could explain where my approach is going wrong and how I could correct it!! Thanks in advance.

#include <bits/stdc++.h>

using namespace std;

int main() {
  // values
  int N, K;
  int possibilities[201][101]{};

  // input
  ifstream fin("nocows.in");
  fin >> N >> K;

  // solution
  possibilities[1][1] = 1;
  for (int k = 2; k <= K; k++){ // for every possible height
    // 1 node is used for the "mother", the amount of the  rest of the nodes will be between 2*(k - 1) and -2 * (1-2^(k-1))
    for (int n = 2 * (k - 1); n <= 2 * (pow(2, k - 1) - 1) && n <= N; n += 2 ){
      // one side will have n1 nodes - anywhere odd number from 1 to n; and a height of k - 1
      for (int n1 = 1; n1 < n; n1 += 2){
        // the other side will have any height k - 1 or less and the remaining nodes
        for (int k1 = 1; k1 < k; k1++){
          // if they are different numbers, they will be doubled because they are not interchangable so can work for both right and left
          if (n1 != n - n1 || k1 != k - 1) 
            possibilities[n + 1][k] += (2 * possibilities[n1][k - 1] * possibilities[n - n1][k1]) % 9901;
          else
            possibilities[n + 1][k] += (possibilities[n1][k - 1] * possibilities[n - n1][k1]) % 9901;
          possibilities[n + 1][k] %= 9901;
        }
      }
    }
  }

  // output
  ofstream fout("nocows.out");
  fout << possibilities[N][K] % 9901 << '\n';

  return 0;
}

edit: to clarify, this is a problem I was trying to solve to help me practice for competitive programming.

• Thus, because programs need to be written quickly, including the whole standard library and using the namespace is common practice to prevent the need to look up which specific parts of the standard library to use and makes typing the code faster, because you don't need to write out std::.
• This being practice for CP is also why a C-style array is used and not std::vector or std::array, because there are memory and time limitations and C-style arrays are generally faster to access and consume less memory.
• Also, because the number of possibilities could maybe become large enough to cause integer overflow, I am finding the remainder with respect to 9901 before adding it to array so that my numbers never get too large.

Answer 1

Let's look in more detail how to split the original problem according to two smaller problems.

In this tree, each node either always has two children or zero children. Thus, either the root (which is referred as the "mother") has two children or zero children. The root having zero children is trivial. It corresponds to N = 1 and K = 1.

When the root has two children, each of these children can be roots of their own trees. Take a closer at these sub-trees. These trees are completely independent of each other. Each of them behave in the same way as the original tree. As long as one of them has a depth of k-1, they together form a valid arrangement of the original tree.

Thus, the solution could be approached in this way:

• For better clarity, let n denote the total number of nodes (In the code given in the question, n corresponds to 1 less than the total number of nodes). It has to be odd to be a valid number of nodes. Say, n1 and n2 are the number of nodes in the two sub-trees. n1 and n2 should also be odd numbers that are less than n-1 and n1 + n2 = n-1.
• There are four variables that determine all the possibilities: n1, n2, k1 and k2. k1 and k2 are the depths of the two sub-trees.
• In the for loops, we need to ensure the condition that at least one of k1 and k2 is equal to k-1. Only then you get a configuration corresponding to the original tree.
• We need to be careful about the case of (k1 == k-1) && (k2 == k-1) and not double count it.

One way to modify the code given in the question is:

#include <algorithm>
#include <cmath>
#include <fstream>
#include <iostream>

int main() {
  // values
  int N, K;
  int possibilities[201][101]{};

  // input
  std::ifstream fin("nocows.in");
  fin >> N >> K;

  // solution
  possibilities[1][1] = 1;
  for (int k = 2; k <= K; k++){ // for every possible height
    // 1 node is used for the root, the total nodes will be 
    // between 2*(k - 1) + 1 and min(2 * (2^(k-1) - 1) + 1, N)
    for (int n = 2 * (k - 1) + 1;
         n <= std::min(static_cast<int>(2 * (pow(2, k - 1) - 1)) + 1, N);
         n += 2 ){
      // The root has two children. Each of the two children could be treated as 
      // roots of their own trees. Thus, the total number of possibilities for 
      // the original is equal to the sum of the product of pairs of these cases.
      // one side will have n1 nodes where n1 < n - 1 
      // the other side will have n2 = n - 1 -n1
      // The two trees are independent, with the constraint being at least one 
      // should have a depth of k-1.
      for (int n1 = 1; n1 < n-1; n1 += 2){
        int n2 = n - 1 - n1;
        for (int k1 = 1; k1 < k; k1++){
          if (k1 != k-1) {
            // constrain only one of the depths to k-1 and count both the given
            // configuration and the switched configuration.
            possibilities[n][k] +=
              2 * possibilities[n1][k1] * possibilities[n2][k-1];
          }
          else {
            // deal with the case of both depths being k-1
            possibilities[n][k] += possibilities[n1][k-1] * possibilities[n2][k-1];
          }
        }
      }
    }
  }

  /*
  for (int n = 0; n <= N; ++n) {
    for (int k = 0; k <= K; ++k) {
      std::cout<<" "<<possibilities[n][k];
    }
    std::cout<<"\n";
  }
  */

  // output
  std::ofstream fout("nocows.out");
  fout << possibilities[N][K] % 9901 << '\n';

  return 0;
}

Thus, the only difference with respect to the code posted in the question is changing the if condition from (n1 != n - 1 - n1 || k1 != k - 1) to if (k1 != k - 1). The earlier condition leads to double counting the cases where k1 == k -1 but n1 != n - 1 - n1. As long as k1 == k-1 the case should be counted only once. That is because n1 ranges over all odd values less than n-1 and n2 = n - 1 - n1. As n1 passes over all its values, we will be dealing with all possible pairs of n1 and n2.