Candy I e CandyIII

Neste post, analisaremos dois problemas do SPOJ:
http://www.spoj.pl/problems/CANDY/
http://www.spoj.pl/problems/CANDY3/

Problema CANDY I

O problema consiste em descobrir o menor número de movimentos necessários para que cada pacote de doces fique com a mesma quantidade de doces. Se a tarefa não for possível, imprima -1.

Observe que a tarefa só é possível se a soma da quantidade de doces de todos os pacotes for divisível pela quantidade de pacotes. 

Para descobrir a menor números de movimentos necessários, basta soma as diferenças entre o número de doces de cada pacote menos a média de números de doces por pacote para os  pacotes com números de doces superior a média. (Difícil né?)

Pseudocódigo
Entrada n o número de pacotes
        vetor p[i] representando número de balas do pacote 1<=i<=n.

soma = 0
Para i = 1 até n faça
   soma += p[i]

Se soma%n==0:
   media = soma/n
   cont = 0
   Para i=1 até n faça
        se p[i] > media
           cont += p[i] - media

Problema CANDYIII

O problema CANDY III é bastante parecido com CANDYI. A tarefa consiste apenas em descobrir se é possível dividir o total de doces de maneira que todas as crianças recebam a mesma quantidade de doces.

Observe que em um problema com restrições razoáveis bastaria somar a quantidade de doces de todas as crianças e testar se o valor encontrado é divisível pela quantidade de criança. Particularmente, este problema não tem nenhuma restrição com relação a quantidade de doces de cada criança e nem em relação a quantidade de crianças.

Para resolver este problema, consideramos que a quantidade de doces de cada criança seria do tipo long long int. Considerando este fato, não temos a garantia que o somatório da quantidade de doces também cabe em long long int. Então, utilizaremos o seguinte resultado de aritmética modular:

(a+b)%n = (a%n + b%n)%n

Observe que este resultado pode ser utilizado para calcular somas difíceis rapidamente.
Por exemplo,
(12124214214214+214214521421412412+42124214215215214+12421412421421)%10
(12124214214214%10+214214521421412412%10+42124214215215214%10+
12421412421421%10)%10
(4+2+4+1)%10
11%10
1

Divisor Summation

No problema Divisor Summation , você deve calcular a somatório de todos os os divisores próprios (um divisor estritamente menor que n) de um número n (1 <= n <= 500000). Por exemplo, o somatório dos divisores próprios de 20 é 1 + 2 + 4 + 5 + 10 = 22.

A seguir, o algoritmo trivial para esse problema:

int soma(int n){
 int i;
 int sum=0;
 
 for(i=1;i<n;i++){
  if(n%i==0){
   sum +=i;
  }
 }
 return sum;
} 

Infelizmente ou felizmente, o algoritmo acima excede o tempo limite estabelecido para o problema. Precisamos torná-lo mais rápido. Primeiramente, vamos mostrar que o seguinte resultado é válido:

Teorema 1: Seja d o menor divisor de um número composto n então d ≤  .

Suponha por absurdo que d >  . Logo,

d²  > n

d > n/d

Se d é um divisor de n então existe um k tal que n=k*d, ou seja, k=n/d. Logo, n/d também é divisor de n. Absurdo, encontramos um divisor menor que d.

Com esse resultado, podemos dividir o conjunto dos números divisores de um número em três conjuntos   , e   nos divisores menores que   , maiores que  e divisores  iguais   , respectivamente. Para cada divisor no conjunto podemos encontrar um divisor no conjunto . O conjunto   é igual  se o  número não é um quadrado perfeito ou é unitário se o número é um quadrado perfeito.  Baseado nessa divisão, nós podemos desenvolver o seguinte algoritmo:

int soma(int n){
    int i;
    int sum = 1;
    if(n==1 ) return 0;
    for(i=2;i*i<n;i++){
       if(n%i==0) { 
        sum+=i; sum+=n/i;
       }
    }
    if(i*i==n) sum += i;
    return sum;
}

Para evitar o excesso de multiplicação dentro for podemos retirar a multiplicação calculando o valor do limite antes do início do for da seguinte maneira.

int soma(int n){
    int i;
    int sum = 1;
    double limite = sqrt(n);
    if(n==1) return 0;    
    for(i=2;i<limite;i++){
       if(n%i==0) { 
        sum+=i; sum+=n/i;
       }  
    }
    if(i*i==n)sum += i;
    return sum;
}

Podemos desenvolver uma solução ainda mais eficiente. A idéia básica do algoritmo que vamos desenvolver é a seguinte: vamos pré-calcular a soma dos divisores para todos os números da entrada em uma tabela. Inicialmente, a tabela começa com todas as somas iguais a zerados. Para cada número i, acrescentamos i para todos múltiplos de i a partir do número 2i.

#include <stdio.h>
#include <string.h>
#define MAX 500001
int sum[MAX];
void preprocess(){
 int i,j;
 memset(sum,0,sizeof(sum)); //zerar o vetor sum
 for(i=1;i<MAX;i++){
   for(j=i+i;j<MAX;j=j+i){
   sum[j] +=i;
  }
 } 
}

int soma(int n){
 return sum[n];
}

  

Problema Count on Cantor

O problema Count on Cantor é baseado na famosa demonstração que o conjunto dos números racionais é enumerável feita pelo matemático Georg Cantor. A prova é baseada no processo de enumeração utilizando as diagonais.Inicialmente, escreveremos todos os números racionais na forma matricial da seguinte maneira:

1/1	1/2	1/3	1/4	1/5	1/6	1/7	...
2/1	2/2	2/3	2/4	2/5	2/6	2/7	...
3/1	3/2	3/3	3/4	3/5	3/6	3/7	...
4/1	4/2	4/3	4/4	4/5	4/6	4/7	...
5/1	5/2	5/3	5/4	5/5	5/6	5/7	...
.	.	.	.	.	.	.
.	.	.	.	.	.	.
.	.	.	.	.	.	.

 
Para mostrar que um conjunto C é contável ou o conjunto é finito ou existe uma bijeção f: . Note que algumas escolhas não são suficientes, por exemplo, se definirmos a seguinte a função:

f:

f(i) = 1/i

As frações com numerador 2, por exemplo, não pertenceriam a imagem de f. Podemos definir uma bijeção f: , enumerando os elementos de Q utilizando a diagonal.

       

O mesmo processo de enumeração por diagonais pode ser aplicado para mostrar que o produto cartesiano N x N é enumerável.  Ainda mais, este processo pode ser generalizado para mostrar que o produto cartesiano de dois conjuntos enumeráveis A e B é enumerável.

O problema pede para você descobrir qual é o termo dada à sua posição  na enumeração.

Podemos observar que na k-ésima diagonal temos k frações m/n cuja  soma do numerador e denominador é uma constante m+n=k+1. O número de frações até a k-ésima diagonal é:

S(k) = 1+2+...+k = k(k+1)/2

A fórmula S(k) pode ser desenvolvida utilizando vários métodos. Vamos desenvolver este somatório de duas maneiras.

Método 1

   S =  1+2     +...+k (Somatório na ordem normal)

+S = k+(k-1)+...+1 (Somatório na ordem inversa)

2S = (k+1)k            (Somando as k parcelas na mesma posição, obtemos (k+1))

S = (k+1)k/2

Método 2

  

 

 

 

A fórmula também pode ser desenvolvida utilizando a expressão (i-1)i - i(i+1).

Para descobrir qual é a diagonal que um termo t está localizada, podemos fazer o seguinte algoritmo:

 d=1;  
 s=1;  
 while( s < t ){  
  d++;  
   s = s + d;  
  }  
  s=s-d;  

A posição do termo na diagonal depende se a diagonal é par ou ímpar. Se a diagonal é par então o numerador começa com o numerador 1 e o denominador d. Se a diagonal é ímpar então o numerador começa com o numerador d e o denominador 1.

 if((d%2)==0){  
   num=1+t-s-1;  
   den=d+s-t+1;  
 }else{  
   num=d+s-t+1;  
   den=1+t-s-1;  
  }