Analysis

Each clan structure can be represented as a b-tree, and the problem reduces to finding the largest matching subtree, for their definition of 'matching'. Because the size of the clans is not very large, we can try a brute-force solution: match every subtree of clan M to every subtree of clan N (number of subtrees = number of nodes, because we must choose the full subtree).

Brute Force

This suggests pseudo-code something like the following:

// read m_list and n_list from input
m_tree = make_btree(m_list)
n_tree = make_btree(n_list)
best = 0
for m_node in m_tree:
   for n_node in n_tree:
       if is_match(m_node, n_node):
           s = m_node.size() // size refers to size of full subtree
           if s > best:
              best = s
print best

There are 2 issues with this approach:

• Match detection is computationally intensive, and the function hides a lot of complexity. Match detection is recursive, so the complexity of match detection is O(size of tree).
• Even with match detection O(1), 10,000 × 10,000 = 100,000,000. That's a big number, and depending on the constant factor, may not finish in half a second (total time / number of test cases = 0.5 seconds). We need some optimizations.

Memoization

Because match detection is recursive, an immediate idea should be to memoize results as they go up the tree. Use a 2-dimensional array of bools (call it matches) to keep track of whether subtree i (clan member i in tree M) is a match with subtree j (clan member j in tree N). Denote this result as matches[i][j] = true.

As long as we fill in matches from the bottom up, the matching code for any node will only iterate over its children in the matches array.

In addition to this, we can compute the number of total subordinates for each node in the same way, storing this result in the node struct itself.

Hashing

Another optimization is the fact that we don't need to check every pair of nodes against each other, just those which appear to match. One way to do this is to use some crude matching criteria initially, and then do a full match if these criteria are satisfied.

My idea is to hash every node in the N-tree using a hash function which generates a unique value out of a combination of:

• Fighting style
• Total number of underlings
• Number of immediate children

Here is my hash function code:

typedef long long ll;
const int MAX_M = 10000;
return ((ll) children.size() * 26 * 2 * MAX_M) + ((ll) num_subordinates * 26) + (fightingStyle - 65);

Where 65 is the ASCII code for 'A'.

In this way, we simply hash each node in the M-tree, find the list of matches in the N-tree (which are pre-hashed), and iterate over these potential matches to do the recursive match computation. Combined with memoization, this should be much faster than MN.