Jump to content

[usaco] Arithmetic Progressions


Localhost
 Share

Recommended Posts

Btw, deixo aqui a minha nova approach:

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

// used array is for checking if exists in O(1)
unsigned int bsq[65000],used[125000];
int upper,size,end,diff;

void input() {
   FILE *fin=freopen("ariprog.in","r",stdin);
   scanf("%i %i", &size,&upper);
   fclose(fin);
}

int comp(const void *a, const void *b) { return (*(int *)a) - (*(int *)b); }

// Generate all the bisquares
void gen() {
   int k=0,j=0,i=0,tmp=0;
   for(k=0; k <= upper; k++) {
       for(j=k; j <= upper; j++,i++) {
           bsq[i]=(k*k)+(j*j);
           used[bsq[i]]=1;
       }
   }
   end=i;
   qsort(bsq,end,sizeof(int),comp);
   for(k=1; k < end; k++) {
       if(bsq[k]==bsq[k-1]) {
           tmp=bsq[k-1];
           bsq[k-1]=bsq[end-1];
           bsq[end-1]=tmp;
           end--;
       }
   }
   qsort(bsq,end,sizeof(int),comp);
   diff=bsq[end-1]-bsq[0];
}

void solve() {
   int k=0,j=0,i=0,q=0,times=0;
   FILE *fout=freopen("ariprog.out","w",stdout);
   for(k=1; k < diff; k++) {
       for(j=0; j < end; j++) {
           for(i=bsq[j],q=0;;i+=k) {
               if(used[i]==1) q++;
               if(used[i]==0 || q > size) break;
           }
           if(q>=size) { printf("%i %i\n",bsq[j],k); times++; }
       }
   }
   if(times==0) printf("NONE\n");
}

int main(void) {
   input();
   gen();
   solve();
   return 0;
}

here since 2009

Link to comment
Share on other sites

Btw, eu tenho a certeza de como posso reduzir o tempo e conseguir passar.

A ideia é um calculo que em que eu não preciso de checar algumas lenghts para as progressões, ou seja, por exemplo, se as sequência tiverem de ter tamanho 3, então eu não preciso de pesquisar progressões com tamanho 1 e 2, porque assim já não vai dar para tamanho 3.

Eu sei que é um calculo qualquer para limitar isso mas não estou a ver como faço esse calculo, talvez já esteja cansado 👍

edit: Problema resolvido, último caso em 2,1seg, not bad.

Btw, o calculo era este: (bsq[end-1]-bsq[0]) / (size-1), em que bsq é o vector que contém os bisquares, end é o final do mesmo vector, size é a lenght das progressões que eles querem.

here since 2009

Link to comment
Share on other sites

1-Faz a aplicação em C++ em vez de C e utiliza o sort() em vez do qsort(). É mais rapido e mais recente.

2-Muda isto:

    for(k=1; k < end; k++) {
        if(bsq[k]==bsq[k-1]) {
            tmp=bsq[k-1];
            bsq[k-1]=bsq[end-1];
            bsq[end-1]=tmp;
            end--;
        }
    }

para isto:

    int fim= end-1;
    for(k=0; k < fim; k++) {
        if(bsq[k+1]==bsq[k]) {
            tmp=bsq[k];
            bsq[k]=bsq[fim];
            bsq[fim]=tmp;
            fim--;
        }
    }
end=fim+1; 

Poupa-te quatro contas de menos por loop.

Quanto tempo e que demora a correr assim?

<Signature goes here>

Link to comment
Share on other sites

xtrm0, o localhost já concluiu este desafio, e as modificações que propuseste são pequenos pormenores ... podem poupar-te alguns milissegundos, mas não vão fazer diferença no resultado final.

Costumava pensar assim -- concentrava-me mais nos pequenos pormenores -- no entanto, tens de te concentrar mais no próprio algoritmo do que nisso (claro que há ocasiões em que esses pormenores são muito significativos, mas neste caso não, e é raro).

No final, se tiveres um TLE, e demorar até 2s, aí talvez seja melhor concentrares-te nos pormenores.

Link to comment
Share on other sites

Voltei a pegar neste problema 👍

Comecei a codar e rapidamente cheguei a uma solução, que só por acaso, não passa no tempo lol. Fui ver como tinha resolvido da última vez e reparei que esta maneira de resolver que utilizei agora é diferente.

Deixo já aqui o código:

#include <cstdio>

using namespace std;

bool bisq[125500];
int n, m, counter, sum, ans;

void pre_compute ()
{
for (int k = 0; k <= m; k++)
{
	for (int i = 0; i <= m; i++)
		bisq[k * k + i * i] = true;
}
}

int main ()
{
FILE *fin = freopen ("ariprog.in", "r", stdin), *fout = freopen ("ariprog.out", "w", stdout);

scanf ("%d %d", &n, &m);
pre_compute ();

for (int k = 1; k <= m * m; k++)
{
	for (int j = 0; j <= m * m; j++)
	{
		sum = j;
		if (bisq[j] == false) continue;
		counter = 1;

		while (counter < n)
		{
			if (bisq[sum + k] == false) break;
			sum += k;
			counter++;
		}

		if (counter == n)
		{
			printf ("%d %d\n", j, k);
			ans++;
		}
	}
}
if (ans <= 0) printf ("NONE\n");

fclose (fin);
fclose (fout);

return 0;
}

Eu sei que existe maneira de reduzir a complexidade disto mudando aquele 2º ciclo (for). Só não sei é como! Alguém me podia ajudar?

here since 2009

Link to comment
Share on other sites

Eu estava a resolver agora este prog mas não estou realmente a perceber o que é pedido, eu vi a explicação do mogers e então gerei os bisquares e ordeneios, e também mapeei os bisquares que foram encontrados, assim:

int bisquares[62500], usados[125000];
int ultimo = 0;

int compara(const void *a, const void *b)
{
return (*(int*)a-*(int*)b);
}

void gera_bisquares(int m)
{
//m = limite
for(unsigned int i=0; i<=m; i++)
{
 for(unsigned int j=i; j<=m; j++)
 {
  if(usados[i*i+j*j] != 1 )
  {
   usados[i*i+j*j] = 1;
   bisquares[ultimo++] = i*i+j*j;
  }
 }
}
}

int main()
{
FILE *in, *out;
in = fopen("ariprog.in", "r");
out = fopen("ariprog.out", "w");
assert(in != NULL && out != NULL);

int N, M;

//lê input
fscanf(in, "%d\n%d", &N, &M);

//gera os bisquares possíveis
gera_bisquares(M);

//sort dos bisquares gerados
qsort(bisquares, ultimo, sizeof(int), compara);

return 0;
}

Mas agora não estou a perceber, eu tenho o vector ordenado, facilmente vou buscar conjuntos de tamanho n até terminar o vector, mas o que pede é as progressões aritméticas, e eu não estou a entender a própria fórmula para as calcular, a, a+b, a+2b, ..., a+nb , o a e b não sei se são inteiros normais ou se são os inteiros bisquares que gerei.. Não estou a entender ;s

Corrige um sábio e ele mais sábio ficará. Corrige um ignorante e um inimigo ganharás.

Link to comment
Share on other sites

Os números da progressão aritmética é que têm de ser bisquares. A solução do exemplo é { 1 , 5 , 9 , 13 , 17 } todos estes números são bisquares. Usando a tua notação o "a" = 1 e o "b" = 4, o "b" não precisa de ser bisquare, os números (a + i*b) é que sim.

"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

Link to comment
Share on other sites

Os números da progressão aritmética é que têm de ser bisquares. A solução do exemplo é { 1 , 5 , 9 , 13 , 17 } todos estes números são bisquares. Usando a tua notação o "a" = 1 e o "b" = 4, o "b" não precisa de ser bisquare, os números (a + i*b) é que sim.

já entendi, thanks 😄

Corrige um sábio e ele mais sábio ficará. Corrige um ignorante e um inimigo ganharás.

Link to comment
Share on other sites

Boas de novo, eu enviei o meu programa mas ele não passa no tempo, no 7º caso, apesar de me dar a resposta..

/*
ID: bruninh1
LANG: C++
TASK: ariprog
*/
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

int bisquares[62500], usados[125000];
int ultimo = 0;

int compara(const void *a, const void *b)
{
return (*(int*)a-*(int*)b);
}

void gera_bisquares(int m)
{
//m = limite
for(unsigned int i=0; i<=m; i++)
{
 for(unsigned int j=i; j<=m; j++)
 {
  if(usados[i*i+j*j] != 1 )
  {
usados[i*i+j*j] = 1;
bisquares[ultimo++] = i*i+j*j;
  }
 }
}
}

int main()
{
FILE *in, *out;
in = fopen("ariprog.in", "r");
out = fopen("ariprog.out", "w");
assert(in != NULL && out != NULL);
int N, M, limite, conta;

//lê input
fscanf(in, "%d\n%d", &N, &M);

//gera os bisquares possíveis
gera_bisquares(M);

//sort dos bisquares gerados
qsort(bisquares, ultimo, sizeof(int), compara);

//calculos
limite = bisquares[ultimo-1] - bisquares[0];
int q = 0, vezes = 0;
for(int i=1; i<limite; i++)
{
 for(int j=0; j<ultimo; j++)
 {
  int q = 0;
  for(int k=bisquares[j];;k+=i)
  {
if(usados[k] == 1)
 q++;
if(usados[k] == 0 || q >= N || k+i>125000) break;
  }
  if(q>=N)
  {
fprintf(out, "%d %d\n", bisquares[j], i);
vezes++;
  }
 }
}
if(vezes == 0)
 fprintf(out, "NONE\n");
return 0;
}

Eu testei o programa e estava a ler uma posição que não existia no vector, porque a "busca" não parava e estava a ler números muito grandes, então limitei ao adicionar : || k+i>125000 , e deixei de ter erro, mas mesmo assim não passa.. E a diferença é muito grande, porque todos os casos passaram em menos de 1s ..

> Run 7: Execution error: Your program (`ariprog') used more than
 the allotted runtime of 5 seconds (it ended or was stopped at
 5.357 seconds) when presented with test case 7. It used 4076 KB of
 memory.
 ------ Data for Run 7 [length=7 bytes] ------
 21
 200
 ----------------------------

Alguma dica? 🙂

Edited by polska

Corrige um sábio e ele mais sábio ficará. Corrige um ignorante e um inimigo ganharás.

Link to comment
Share on other sites

Para que é que serve o ciclo for(int i=1; i<limite; i++) ?

Na prática é useless...

"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

Link to comment
Share on other sites

Para que é que serve o ciclo for(int i=1; i<limite; i++) ?

Na prática é useless...

é o ciclo do valor 'b' na expressão que pus aqui da outra vez, e incrementa no ciclo k... , mas isso tu viste 😉

Corrige um sábio e ele mais sábio ficará. Corrige um ignorante e um inimigo ganharás.

Link to comment
Share on other sites

O b é derivado da diferença entre bisquares, pois a sequência só pode ter bisquares.

"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
 Share

×
×
  • Create New...

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.