Segue abaixo a matriz com CADBDA na vertical e ACABBAD na horizontal:
| A | C | A | B | B | A | D | ||
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | |
| C | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
| A | 0 | 1 | 1 | 2 | 2 | 2 | 2 | 2 |
| D | 0 | 1 | 1 | 2 | 2 | 2 | 2 | 3 |
| B | 0 | 1 | 1 | 2 | 3 | 3 | 3 | 3 |
| D | 0 | 1 | 1 | 2 | 3 | 3 | 3 | 4 |
| A | 0 | 1 | 1 | 2 | 3 | 3 | 4 | 4 |
Poderia ter sido feita também a matriz transposta, com ACABBAD na vertical e CADBDA na horizontal.
As subsequências comuns mais longas são CABA e CABD. Qualquer uma delas seria uma resposta válida.
O critério de avaliação premiou com 0,5 a subsequência comum mais longa e com 2,0 a construção da matriz.
Pelo tamanho do heap (58), já dá pra saber que ele terá árvores de graus 1, 3, 4 e 5, contendo respectivamente 2, 8, 16 e 32 elementos, cuja soma dá 58.
Há inúmeras maneiras de distribuir as chaves pelas árvores. Um possível heap seria o seguinte:
A coisa mais esperta a fazer seria colocar a menor chave (1) na árvore de grau 1. Assim sua retirada apenas transformaria esta árvore numa árvore binomial de grau zero e não mexeria nas demais.
Quem desenhou as árovres com chaves corretas, disse os graus e mostrou as mudanças após extração do mínimo ganhou nota 2,5. Tirei pontos que quem violou a estrutura de heap (por exemplo, colocando uma chave maior como pai de uma menor - tirei 0,5 pontos) e de quem colocou mais de uma árvore de um certo grau (tirei 2,0 pontos). Teve gente que deixou esta questão em branco ou quase; estes levaram zero.
Os tempos de chegada e partida são dados abaixo:
Não havia outra resposta, pois especificamos a ordem alfabética. Houve quem comecasse de zero, o que foi considerado correto também. Quem violou a ordem alfabética perdeu 1,0 ponto. Quem repetiu números (por exemplo, chegada de i igual à partida de f) perdeu 0,5 para cada repetição. Quem errou tempos de saída perdeu 1,0 ou 1,5 pontos, dependendo da gravidade.
Usando Kruskal (aquele algoritmo que pega as arestas em ordem crescente de peso), uma possível solução seria:
ai, bi, dg, dh, aj, ae, hk, eh, bc, af
Há outras ordens corretas porque quando empata o peso pode-se tomar qualquer aresta que não gere ciclo. Por exemplo, aj e dh podem ser incluidas em qualquer ordem. Há também a opção de escolher ef em lugar de af no final, dando também uma resposta correta.
Poderia ter sido usado Prim também. Aí as respostas são muito mais variadas, pois pode-se iniciar o algoritmo em qualquer vértice.
Teve gente que pegou arestas erradas, por vários motivos. Aí o critério baseou-se no peso da árvore resultante. Quem passou x unidades do peso mínimo perdeu x pontos, exceto que não deixei baixar de 0,5 quando percebi que a pessoa sabia pelo menos o básico sobre o problema. Teve gente que acertou a árvore, mas errou a ordem em que as arestas foram inseridas - neste caso tirei 1,0 ponto.