Problema C - Arrumando o quarto

O Problema

Dado um conjunto de $N$ números, determinar o tamanho do maior subconjunto de números tal que para todo o par $N_i$ e $N_j$ pertencentes ao conjunto se tem que $N_i$ é múltiplo de $N_j$ ou $N_j$ é múltiplo de $N_i$.

Restrições

São garantidos os seguintes limites em todos os casos de teste que irão ser colocados ao programa:

1 ≤ $N$ ≤ 100 000	Número de elementos no conjunto
1 ≤ $N_i$ ≤ 10 000 000	Valores do conjunto

Os casos de teste deste problema estão organizados em 4 grupos com restrições adicionais diferentes:

Grupo	Número de Pontos	Restrições adicionais
1	20	1 ≤ $N$ ≤ 25, 1 ≤ $N_i$ ≤ 1 000
2	40	1 ≤ $N$ ≤ 1 000, 1 ≤ $N_i$ ≤ 100 000
3	20	1 ≤ $N$ ≤ 100 000, 1 ≤ $N_i$ ≤ 100 000
4	20	-

Solução Base

Neste problema precisamos de encontrar o maior subconjunto que satisfaça a propriedade que para todos os pares de elementos $a$, $b$, ou $a$ é múltiplo de $b$ ou $b$ múltiplo de $a$.

A solução mais simples para este problema será gerar todos os subconjuntos possíveis, verificar quais os que respeitam a restrição do problema e escolher o maior dentro desses.

Para gerar todos os subconjuntos possíveis, basta usar uma função recursiva que vai construindo os subconjuntos, garantindo sempre que cada valor a adicionar é válido, ou seja, é múltiplo ou divisor dos valores já adicionados.

Como há $2^N$ subconjuntos diferentes e testar se todos os pares são múltiplos requer tempo $N^2$, esta solução tem complexidade temporal proporcional a $N^2 \cdot 2^N$.

Esta seria uma solução $O(N^2 \cdot 2^N)$ que daria aproximadamente 20 pontos.

Solução Melhorada

Para melhorar a solução anterior, começamos por fazer uma observação. Se $S$ é um subconjunto que respeita as restrições do problema, então o menor elemento de $S$ é divisor de todos os elementos de $S$ e o maior elemento de $S$ é múltiplo de todos os elementos de $S$. Sabendo isto, vamos descrever uma solução mais inteligente que a anterior.

Vamos chamar ao conjunto de números do problema de $C$, denotando por $C_i$ o i-ésimo elemento de $C$. Adicionalmente, vamos chamar a $S_i$ ao tamanho do maior subconjunto de $C$ que tem como menor elemento o valor $C_i$. Se já tivermos calculado $S_i$, para todos os $i$ maiores que $k$, então para calcularmos $S_k$ podemos fazer o seguinte: se $C_j$ é múltiplo de $C_k$ (com $j > k$), então podemos pegar no conjunto correspondente a $S_j$, adicionar-lhe $C_k$ e obter um conjunto válido. Logo podemos procurar todos os índices $j$ onde $C_j$ é múltiplo de $C_k$, escolher o com maior $S_j$ e calcular $S_k = S_j + 1$, o que corresponde a pegar no conjunto correspondente a $S_j$ e adicionar-lhe $C_k$.

Se guardarmos os valores de $S_i$ num array para evitar recomputá-los, temos uma solução baseada na conhecida técnica de programação dinâmica que tem complexidade temporal $O(N^2)$. Na verdade, esta solução é muito parecida com a solução do conhecido problema de Longest Increasing Subsequence.

Esta seria uma solução $O(N^2)$ que daria aproximadamente 60 pontos.

Solução Intermédia

A solução anterior é muito melhor que a inicial, passar de $O(N^2 \cdot 2^N)$ para $O(N^2)$ é uma melhoria enorme, mas podemos fazer melhor.

Vamos agora pensar sobre $S_i$ "ao contrário", ou seja, vamos definir $S'_i$ como o tamanho do maior subconjunto de $C$ que tem como maior elemento o valor $C_i$. A propriedade que atribuímos a $S_i$ mantém-se para $S'_i$, mas neste caso será: se $C_j$ é divisor de $C_k$ (com $j > k$), então podemos pegar no conjunto correspondente a $S_j$, adicionar-lhe $C_k$ e obter um conjunto válido. Usando $S'_i$, podemos obter uma solução muito parecida com a anterior, com complexidade $O(N^2)$, mas nós queremos melhor!

Para calcular $S'_k$, só nos interessa os $S'_j$ de elementos que sejam divisores de $C_k$, logo podemos modificar a nossa solução ligeiramente. Se em vez de indexarmos $S'_i$ nos elementos de $C$, indexarmos nos valores, podemos fazer algo diferente. O que isto significa é: em vez se considerarmos $S'_i$ como o maior subconjunto com maior valor $C_i$, considerarmos $S'_i$ como o maior subconjunto com maior valor $i$ (nota como agora usamos o valor em vez do índice em $C$) podemos só escolher os índices que nos interessam. Se usarmos esta modificação, para calcular $S'_k$ basta gerarmos todos os divisores $j$ de $k$ e escolher aquele com maior valor de $S'_j$ como na solução anterior. A vantagem de fazer isto é que um número $k$ tem no máximo $2\sqrt{k}$ divisores (se $i$ é divisor de $k$, então $k / i$ também é) logo conseguimos calcular o valor de $S'_k$ com complexidade temporal $\sqrt{k}$. Se calcularmos a resposta para todos os valores de $k$ desde $1$ até $\max{N_i}$, calculamos todas as respostas possíveis.

Nota: é preciso ter algum cuidado com valores repetidos nesta solução. Se $C$ conter vários valores de $i$, é preciso ter isto em consideração no cálculo de $S'_i$. Deixamos os pormenores como exercício, mas uma dica é guardar a frequência de cada número numa array $F$ e depois de determinar o melhor $S'_j$ para calcular $S'_k$ fazer $S'_k = S'_j + F_k$.

Esta seria uma solução $O(N\sqrt{\max(N_i)})$ que daria aproximadamente 80 pontos.

Solução Ótima

Estamos mesmo próximos da solução ótima!

Vamos voltar a olhar para a solução melhorada e pensar de forma semelhante ao que fizemos na solução anterior. Quando estamos a calcular o valor de $S_k$ na solução anterior, será que precisamos mesmo de passar por todos os elementos de $C$ com índice $j > k$? Na verdade, os únicos valores válidos são os múltiplos de $C_k$, logo vamos fazer algo parecido com o que fizemos na solução intermédia. Se indexarmos $S_i$ indexarmos nos valores de $C$ (como fizemos na solução anterior), o que temos de determinar agora são todos os múltiplos $j$ de $k$ e escolher o com maior $S_j$.

Esta solução é muito parecida com a anterior, mas usando múltiplos em vez de divisores, mas então, porque é que é melhor? À primeira vista esta solução parece ser $O(N^2)$, o que não seria nada bom, mas podemos fazer uma análise mais cuidada:

• Para calcular $S_1$, temos de passar por todos os múltiplos de 1, que são no máximo $\max(N_i)$ números.
• Para calcular $S_2$, temos de passar por todos os múltiplos de 2, que são no máximo $\max(N_i) / 2$ números.
• Para calcular $S_3$, temos de passar por todos os múltiplos de 3, que são no máximo $\max(N_i) / 3$ números.
• ...
• Para calcular $S_k$, temos de passar por todos os múltiplos de k, que são no máximo $\max(N_i) / k$ números.

Ou seja, a complexidade da nossa solução é: $\max(N_i) \cdot (1 + 1 / 2 + 1 / 3 + ... + 1 / \max(N_i))$. O truque está em perceber que este valor de $(1 + 1 / 2 + 1 / 3 + ... + 1 / \max(N_i))$ é proporcional ao logaritmo de $\max(N_i)$. A explicação de tal não é trivial, requer alguns conhecimentos matemáticos mais avançados, mas podem ler mais sobre o assunto neste artigo da Wikipédia sobre números harmónicos, que é o nome pelo qual esta série é conhecida. Sendo assim, a nossa solução final tem uma complexidade temporal total de $O(N\log(\max(N_i)))$.

Esta seria uma solução $O(N\log(\max(N_i)))$ que daria os 100 pontos.