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.