Soluções da Qualificação das ONI'2020
Problema B - Solidão inteira
Tipo de problema: Ad-Hoc
Autor do problema: Henrique Navas (Universidade de Lisboa - IST)
Dificuldade do problema: Médio-Fácil
O Problema
O problema é composto por duas partes semelhantes mas diferentes.
Em ambos as partes é nos dado um inteiro par $N$ e pedido para encontrar um emperelhamento de todos os números menores ou iguais a $N$ tal que a soma dos dois números inteiros satisfaça uma condição em particular.
- No primeiro caso, que a soma seja da forma $2^k-1$ para $k$ inteiro.
- No segundo case, que a soma seja um número primo (ou seja que só seja divisível por si próprio e $1$).
Restrições
É garantida o seguintes limite em todos os casos de teste que irão ser colocados ao programa:
1 ≤ $N$ ≤ $10^5$ | Inteiro máximo |
Solução Base (Subtarefa 1)
A solução conceptualmente mais simples seria a de gerar todos os possíveis emparelhamentos, até encontrar um em que todas as somas respeitam a condição, e retornar essa resposta. Apesar de simples, a implementação de tal solução de pesquisa (usando BFS ou DFS) é algo trabalhosa.
Uma alternativa seria resolver os 5 casos para cada parte no papel e fazer um programa que retorna cada solução baseada no valor de $N$. A descoberta e a implementação seriam mais fáceis e este trabalho abriria pistas para as próximas soluções.
Solução Melhorada (Subtarefa 2)
Para melhorar sobre a solução base, é importante a seguinte observação: se um par $(q,p)$ satisfaz a condição de interesse, então $(q+1,p-1)$ também satisfaz a mesma condição. Deste modo, assim que encontramos um par que satisfaz a condição de interessa, podemos gerar uma série de outros pares que também é válido.
Aplicando ao nosso problema, sugere a seguinte estratégia:
- Começando no inteiro $N$, temos de encontrar um outro inteiro $k$ tal que $N+k$ satisfaça nossa condição.
- Assim podemos gerar todos os pares $(N-i, k+i)$ para $0\le i \le \lfloor (N-k)/2 \rfloor$ (com cuidado para não repetir pares).
- Contando estes pares, já utilizamos todos os inteiros de $k$ a $N$, e encontramonos na mesma situação inicial com $N$ substituído por $k-1$.
(Uma nota importante, como $N$ é par e a condicão exige que a soma seja ímpar, é garantido que $k$ é ímpar também, e portanto que $k-1$ permanece par.)
A dificuldade agora está em, dado um par $N$, como encontrar um outro inteiro $q$, tal que $N + q$ satisfaça a condição de interesse. A forma mais simples é testar para vários $q$ se a condição é satisfeita.
Como para cada $N$, temos de testar todos os números até encontrar o par apropriado, no pior dos casos, esta solução pode ter de realizar $O(N^2)$ operações só com os dois ciclos exteriores.
É importante notar que o próprio teste afeta a complexidade do algoritmo. Nesta implementação, para testar se um número $q$ é da forma $2^k-1$ ou é primo, estamos a fazer $O(\log k)$ e $O(\sqrt{k})$ operações respectivamente, aumentando a complexidade temporal do algoritmo (no pior caso) para $O(N^2 \log N)$ e $O(N^{2+0.5})$.
Contudo é possível garantir que o próprio teste tem complexidade constante e não aumenta a complexidade da nossa abordagem. Para isso é preciso precomputar os valors $q$ que satisfazem a condição. No caso da parte 1, é fácil gerar todos os números que sejam da forma $2^k-1$ e guardar num array. No caso da parte 2, podemos gerar a lista de todos os primos até um certo número usando o Sievo de Arestotenes (Link da página da Wikipédia).
A complexidade da solução é então dada pela soma da complexidade da precomputação e a complexidade dos dois loops. Neste caso, a complexidade temporal é dominada pela segunda parte e é então $O(N^2)$ que é suficiente para 10+20 pontos em ambas as partes.
Solução Optimizada (Subtarefa 3)
Para a solução final, temos de eliminar o loop interno em que testamos diferentes $q$ pela condição. Para tal temos de ser capazes de calcular, em tempo constante o seguinte: dado um número $k$, qual é o número $q$ tal que $k+q$ satisfaz a condição. Felizmente essa informação já está contida na precomputação que fizemos no subgrupo anterior e com uma simples extensão podemos calcular esta resposta também.
Para tal, basta notar o seguinte, se há dois inteiros $m_1 \le m_2$ que satisfazem a condição, então para todos $m_1 \le k < m_2$ o valor de $q$ será $m_2 - k$. Podemos precomputar estes valores da seguinte forma:
- Começando com $k+1$ igual ao valor mais alto do array onde a condição é satisfeita ($m$) vamos construir o array dos $q$. Neste caso $q=m_N-k=1$.
- Ao reduzir o valor de $k$, há duas possibilidades,
- se $k+1$ satisfaz a condição, o valor mais próximo onde a condição é verificada é actualizada $m = k+1$ e $q = m - k = 1$.
- se $k+1$ não satisfaz a condição, o valor mais próximo onde a condição é satisfeita permanece o mesmo, e q $q = m - k$.
Deste modo só temos de percorrer o array uma vez e o algoritmo tem complexidade temporal $O(N)$. Isto permite não ter o loop interno, baixando a complexidade temporal de $O(N^2)$ para $O(N)$.
Esta solução daria para todos os pontos neste problema, 10+20+20 em cada parte.