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.
#include <stdio.h>
bool primo(int a) {
for (int i = 2; i * i < a; i++)
if (a % i == 0)
return false;
return true;
}
bool potenciaDoisMenosUm(int a){
int t = 1;
while (t - 1 <= a) {
if (a == t - 1)
return true;
t *= 2;
}
return false;
}
int main()
{
int P, N;
scanf("%d", &P);
scanf("%d", &N);
int k = N;
while (k > 0) {
int c = 0;
bool encontrado = false;
// Encontrar o c que satisfaz a condicao
while(!encontrado) {
c++;
if(P==1){ encontrado = potenciaDoisMenosUm(k + c);}
if(P==2){ encontrado = primo(k + c);}
}
// Gerar os pares
for (int i = 0; i <= (k - c) / 2; i++)
printf("%d %d\n",c+i, k-i);
k = c-1;
}
return 0;
}
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).
#include <stdio.h>
#define NMAX 200307
bool condicao[NMAX];
int main()
{
int P, N;
scanf("%d", &P);
scanf("%d", &N);
if (P == 1) {
for (int i = 0; i < NMAX; i++)
condicao[i] = false;
int c = 1;
while (c - 1 < NMAX) {
condicao[c-1] = true;
c *= 2;
}
}
else if(P==2) {
for(int i = 0; i < NMAX; i++)
condicao[i] = true;
for(int i = 2; i < NMAX; i++){
if (condicao[i]) {
int c = 2 * i;
while(c < NMAX){
condicao[c] = false;
c += i;
}
}
}
}
int k = N;
while (k > 0) {
int c = 0;
bool encontrado = false;
// Encontrar o c tal que k + c satisfaz a condicao
while (!encontrado) {
c++;
encontrado = condicao[k + c];
}
// Gerar os pares
for(int i = 0; i <= (k - c) / 2; i++)
printf("%d %d\n", c + i, k - i);
k = c - 1;
}
return 0;
}
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)$.
#include <stdio.h>
#define NMAX 200307
bool condicao[NMAX];
int next[NMAX];
int main()
{
int P, N;
scanf("%d", &P);
scanf("%d", &N);
if (P == 1) {
for (int i = 0; i < NMAX; i++)
condicao[i] = false;
int c = 1;
while (c - 1 < NMAX) {
condicao[c-1] = true;
c *= 2;
}
}
else if(P==2) {
for(int i = 0; i < NMAX; i++)
condicao[i] = true;
for(int i = 2; i < NMAX; i++){
if (condicao[i]) {
int c = 2 * i;
while(c < NMAX){
condicao[c] = false;
c += i;
}
}
}
}
// Calcular o q
int m = -1;
for (int i = NMAX - 1; i >= 0; i--) {
next[i] = m - i;
if (condicao[i])
m = i;
}
int k = N;
while (k > 0) {
int c = next[k];
// Gerar os pares
for (int i=0; i <= (k - c) / 2; i++)
printf("%d %d\n", c + i, k - i);
k = c - 1;
}
return 0;
}
Esta solução daria para todos os pontos neste problema, 10+20+20 em cada parte.