Problema das ONI - A da final de 2009

[Joao brandao]

Boa noite, estava aqui a resolver o problema A da final de 2009(www.dcc.fc.up.pt/oni/problemas/2009/final/probA.html ) e por muito mais que pense, as ideias que tenho acabam sempre por passar o excesso de tempo possivel :-S ja fiz uma maneira que pensava que ia ter pelo menos 20 pontos e excedeu o tempo limite dando me apenas 4 pontos :-S

Se quiserem posso deixar a minha resoluçao para dos 4 pontos.

O pessoal mais evoluído nisto pode me dar uma dica de como fazer este problema sem exceder o tempo limite ?

[skiller10]

Na minha opinião este problema é DP mas tem que ser muito bem optimizado para os 100 pontos. Não vejo nenhuma maneira melhor para resolver este problema, existirá alguma solução greedy ou relacionada com teoria de números?

[Joao brandao]

Eu vi +/- a teoria do Diofanto de Alexandria, como podes imaginar eu sozinho n consigo ver/aprender a teoria toda em 1 ou 2 dias, visto ser algo muito elaborado isto.

Mas o que eu consigui retirar para resolver este problema foi uma "tecnica matematica" para isto mas mesmo assim nao esta 100% certa :-S

por exemplo:

// levo o num que é o numero que quero e depois envio a soma que vai representar a minima soma possivel para formar o numero
double process2(double num,int soma){
int   a=(int)floor(sqrt(num))*(int)floor(sqrt(num));
double   b=num-a;
int   c=(int)floor(sqrt(b))*(int)floor(sqrt(b));     
int   d=(int)floor(sqrt(b-c))*(int)floor(sqrt(b-c));
int   g=(int)floor(sqrt((b-c)-d))*(int)floor(sqrt((b-c)-d));
if((a+c==num)&&((d==0)&&(g==0)))
  soma=2;
if((a+d+c==num)&&(g!=0))
  soma=3;
if((a+d+c+g==num)&&((d!=0)&&(g!=0)))
  soma=4;
    return soma;

chamei essa função que se encontra ai para me calcular apenas a soma minima para nos levar ao numero que quero mas como ja disse, não esta 100% certo e na minha opinião, este problema não é assim que se faz 😕

[mogers]

A minha solução não usa DP (mas penso que existe uma abordagem com DP). Não me parece que seja preciso nada de especial em termos teóricos para resolver o exercício (teorias de diofanto ou lá o k andaste a ver..)

1) Tás a fazer somas de quadrados, quantos quadrados existem até 2 000 000? 1414 nem são muitos

2) 2 000 000 não é um número muito grande, podes usar um array de flags a saber se vec[ n ] é resultado da soma de 2 quadrados

3) Se K = 3, usando dois quadrados, só precisas de saber se (N - num1*num1 - num2*num2) é um quadrado

...

[skiller10]

Podes explicar melhor a tua ideia mogers.

Pelo que entendi o primeiro caso é quando sqrt(N) é um inteiro, aí a resposta é: 1 1

Os outro casos não entendi muito bem, não preciso sempre de pelo menos dois arrays? Um para guardar o nº minimo de quadrados para obter N e outro com o nº de maneiras para o fazer usando esse numero de quadrados.

[mogers]

Os outro casos não entendi muito bem, não preciso sempre de pelo menos dois arrays? Um para guardar o nº minimo de quadrados para obter N e outro com o nº de maneiras para o fazer usando esse numero de quadrados.

Depende da forma como contas as hipóteses. Mas não precisas desses arrays para guardar as soluções, basta um contador com o numero de soluções.

Eu testo se o N é um quadrado (resposta 1), depois testo se é a soma de 2 quadrados. Senão der testo se dá com 3 e por fim conto com 4 (porque com 4 dá sempre).

Não queria descrever muito a solução porque senão estrago o desafio. Mas como é que verificas se um número é resultado da soma de 2 quadrados? E como contas?

E no caso em que são precisos 3 quadrados?

[skiller10]

Mas como é que verificas se um número é resultado da soma de 2 quadrados?

Se n = a^2 + b^2, sendo a e b inteiros positivos. Para o caso dos 2 quadrados sei também que se x = (n-1)/4 resultado num x inteiro, pode ser escrito como a soma de 2 quadrados.

[mogers]

Não era isso. Isso que escreveste é trivial 🙂

Como fazes com código mesmo.. especialmente o caso com 3 quadrados

PS: Claro que ao perguntar isto, não quero que respondas algo como

for i = 1 ; i * i < 2000000

    for j = i ; j * j < 2000000

          for k = j ; k * k < 2000000

                  if n = i*i+j*j+k*k

[skiller10]

Apenas me estou a lembrar de uma maneira de o fazer, que é tentar a soma de todos os quadrados e ver se é igual a N.

[mogers]

Pensa um pouco em como melhorar isso.

[skiller10]

Tenho uma pequena ideia, mas amanhã penso melhor que cheguei a bocadinho do treino e estou todo partido 🙂

EDIT: Estive a pensar e a melhor maneira que vejo de o fazer é com DP (knapsack). Podes dar-me alguma dica mais ou a complexidade com que é possível calcular para ver se tenho mais alguma ideia. Também me lembrei de outra maneira que é utilizar pesquisa binária mas não estou a ver como aplicar esta ideia da pesquisa binária muito bem para a soma de 3 e 4 quadrados.

[Joao brandao]

Eu tinha feito essa solução antes de ter colocado post aqui no forum, e essa apenas me deu 4 pontos pk passava do tempo limite :-S

P.s.: A solução não esta de forma alguma feita para os 100 pontos e ainda da erros em alguns casos infelizmente , mas ja da para perceberem +/- a logica do problema

#include <cstdlib>
#include <iostream>
#include <cmath>
using namespace std;
int maior=0;
double process2(double num,int soma){
int   a=(int)floor(sqrt(num))*(int)floor(sqrt(num));
maior=(int)floor(sqrt(num));
double   b=num-a;
int   c=(int)floor(sqrt(b))*(int)floor(sqrt(b));   
if(a+c!=num) {
int   d=(int)floor(sqrt(b-c))*(int)floor(sqrt(b-c));
int   g=(int)floor(sqrt((b-c)-d))*(int)floor(sqrt((b-c)-d));}
if((a+c==num)&&((d==0)&&(g==0)))
  soma=2;
if((a+d+c==num)&&(g!=0))
  soma=3;
if((a+d+c+g==num)&&((d!=0)&&(g!=0)))
  soma=4;
    return soma;
}
int process3(int y,int existe,int num){
int o,p,z;
int retira=0;
existe=0;
if(y==2){retira=2;o=maior;p=1;z=1;}
if(y==3){retira=1;o=maior;p=maior;z=1;}
if(y==4){retira=0;o=maior;p=maior;z=maior+1;}
for(int i=1;i<=maior;i++){
        for(int j=1;j<=o;j++){
                for(int k=1;k<=p;++k){
                        for(int x=1;x<=z;x++){
                                if((((i*i)+(j*j)+(k*k)+(x*x))-retira)==num)
                                    existe++;
                        }
                }
        }
} 
return existe;
}
int main()
{
 int num,n,existe;
   double x,y;
   int soma=0,final;
   cin>>n;
   for(int prox=0;prox<n;prox++){
   cin>>num;
   if(num==(floor(sqrt(num))*floor(sqrt(num))))
     cout<<num<<": 1 1\n";
   else
   {
      y=process2(num,soma);
      final=process3(y,existe,num);
      cout<<(int)num<<": "<<(int)y<<" "<<(int)final-1<<endl;
      }
   }    system("pause");
   return 0;

}

[mogers]

se tens 4 pontos é certamente por wrong answers. Esse código inicial com a,c,d e g é meio estranho e é provavel que esteja errado. Faz uma solução de pesquisa normal.

PS: cuidado com erros númericos. Algo como sqrt(9) pode eventualmente dar como resultado 2.9999999999 e o floor disso é 2.

[Joao brandao]

se tens 4 pontos é certamente por wrong answers. Esse código inicial com a,c,d e g é meio estranho e é provavel que esteja errado. Faz uma solução de pesquisa normal.

PS: cuidado com erros númericos. Algo como sqrt(9) pode eventualmente dar como resultado 2.9999999999 e o floor disso é 2.

eu tive a ver e existe um caso que eles colocam la que dava qualquer coisa como 2,73 por exemplo e eles passaram para 2 para poder continuar o programa.(e neste caso o meu programa dava certo, dai ter a praticamente a certeza que é sempre para arredondar para baixo)

[mogers]

O que eu estou a dizer é que coisas como

if(num==(floor(sqrt(num))*floor(sqrt(num))))
      cout<<num<<": 1 1\n";

podem falhar porque fica if (9 == 2*2) em vez de if 9 == 3*3 devido aos erros numéricos.

Podes evitar esse tipo de coisas. Só tens numeros ate 2000000, podes usar um array de flags onde a posição i está a 1 se for um quadrado.

[Joao brandao]

vou amanha tentar voltar fazer este exercicio a ver uma soluçao melhor para isto, nem vale a pena tentar ver os erros desta soluçao pk nao iria sair do sitio. Começo uma soluçao mais simples e depois optimizo a soluçao.

Este problema é um excelente problema para quem quiser treinar um pouco 😉

[skiller10]

Mogers, viste o edit do meu post?

[mogers]

Mogers, viste o edit do meu post?

Não vi. Acho que é preferível um novo post a um edit tanto tempo depois do 1º post.

Penso que a solução que usa DP é semelhante ao knapsack, mas não pensei nela, não te posso ajudar mt nesse aspecto.

A complexidade penso que não ajuda muito neste caso, é O(N). Ou se preferires O( N + sqrt(N)*sqrt(N) ) = O(N)

É dificil tentar dar dicas quando dizes tão pouco. Só falaste em knapsack, pesquisa binária e pediste a complexidade. Sem saber como é que estás a pensar fazer as coisas, não dá muito para ajudar.

[skiller10]

A minha ideia DP que pensei é ter uma matriz do género DP[4][2000000], em DP[0] meto 1 ou 0 consoante i seja ou não um quadrado perfeito. Depois a partir daí construo os restantes "níveis": DP[1] etc. Uma melhoria a isto podia ser ter apenas um array DP[2000000] com o número de maneiras de chegar ao número e um outro array que guarda o minimo de quadrados necessários. Dava então uma complexidade de O(4*sqrt(2000000)) se não estou em erro.

A ideia da pesquisa binária para a soma de dois quadrados era pegar em cada quadrado e depois fazer uma pesquisa binária para o segundo quadrado, visto que já se sabe o valor N, já se sabe o valor do primeiro quadrado (X), é so fazer uma pesquisa pelo valor Y que será igual a N - X.

[mogers]

A ideia base da DP penso que é por aí, mas a parte complicada não é saber quantos quadrados são precisos, é evitar contar repetidos no número de soluções.

É impossível a complexidade ser apenas um factor de sqrt(N), vais ter de percorrer os N números...

Volto a referir, visto que N vai apenas até 2000000, podes usar um array de flags 0/1, poupando o factor O(log N) da pesquisa binária.