MO417 - Questão para a prova oral

Número: 086

Enunciado:
Você e seus amigos participam de um bolão online do jogo da final do campeonato que acontecerá nesse fim de semana. Você gostaria de definir sua aposta considerando a quantidade de jogadores titulares escalados, porém, a escalação só sai minutos antes do encerramento das apostas. Conhecendo o número das camisetas dos jogadores titulares e sabendo que a numeração das camisetas não muda, você decide então codificar um programa para calcular a quantidade de jogadores titulares escalados e realizar a aposta.
Especificamente, sobre o problema de calcular a quantidade de jogadores titulares escalados, sabendo, contudo, que um jogador pode ser escalado em uma posição diferente da sua original, julgue as afirmações a seguir e aponte a CORRETA.

1. Esse problema é semelhante ao problema de encontrar uma subcadeia em um texto;
2. Esse problema pode ser resolvido com complexidade O(n * log(n)) ordenando os números das camisetas dos jogadores escalados e realizando um busca binária da numeração de cada jogador titular nesse conjunto.
3. Esse problema é igual ao problema da Maior Subsequencia Comum e portanto não pode ser resolvido em O(n * log(n)).
4. Um algoritmo guloso que considera só a maior subsequencia comum até o momento resolve o problema;
5. NDA

Autor(a): Raoni Florentino da Silva Teixeira