Arithmetic Progressions

This is a explanation of this problem from USACO's training website. I have converted it to markdown. Please do not just copy code; you will not learn anything; at least type it out and understand so you can do it yourself in the future!

An arithmetic progression is a sequence of the form a, a+b, a+2b, …, a+nb where n=0, 1, 2, 3, … . For this problem, a is a non-negative integer and b is a positive integer.

Write a program that finds all arithmetic progressions of length n in the set S of bisquares. The set of bisquares is defined as the set of all integers of the form p2 + q2 (where p and q are non-negative integers).

TIME LIMIT: 5 secs

PROGRAM NAME: ariprog

INPUT FORMAT

Line 1:	N (3 <= N <= 25), the length of progressions for which to search
Line 2:	M (1 <= M <= 250), an upper bound to limit the search to the bisquares with 0 <= p,q <= M.

SAMPLE INPUT (file ariprog.in)

5
7

OUTPUT FORMAT

If no sequence is found, a single line reading ‘NONE’. Otherwise, output one or more lines, each with two integers: the first element in a found sequence and the difference between consecutive elements in the same sequence. The lines should be ordered with smallest-difference sequences first and smallest starting number within those sequences first.

There will be no more than 10,000 sequences.

SAMPLE OUTPUT (file ariprog.out)

CODE

Java

C++

Pascal

ANALYSIS

Felix Arends & Saber Fadaee

This can be done by brute force, enumerating over all possible sequences. It has to be done a little carefully in order to get it to run in time, however.

Precalculate the bisquares, first of all. Calculate both a sorted list of the bisquares, along with a boolean array saying whether each number between 1 and 125000 (the maximum bisquare possible, for p,q < 250) is a bisquare.

Go through the ‘skip value’s in increasing order, starting at 1, and continuing along as the sequence starting at 1 and continuing along by adding the ‘skip value’ doesn’t exceed the maximum bisquare. For each bisquare, determine if the sequence starting at that location (and with the current ‘skip value’) consists of all of bisquares. If so, output it.

Here is the solution of Felix Arends from Germany (modified by Iran’s Saber Fadaee):

#include <stdio.h>
#include <assert.h>
#include <string>

using namespace std;

// open files
FILE *fin = fopen ("ariprog.in", "r");
FILE *fout = fopen ("ariprog.out", "w");

// global variables
unsigned int N, M, maxMM;
unsigned int numbers [65000];
unsigned int number_size = 0;
unsigned char num_available [125001];
unsigned char dist_available [125001];
int have_res = 0;
int skipstep = 1;

// read the input

int read_input () {
    fscanf (fin, "%d %d", &N, &M);
    return 0;
}

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

void asm_num (int a, int b) {
    for (unsigned int n = 1; n < N; n++)
        if (num_available [a + n * b] == 0) return;

    fprintf (fout, "%d %d\n", a, b);
    have_res ++;
    if (have_res==1)
        skipstep = b;

}

void asm_num () {
    for (unsigned int b = 1; b < maxMM; b+=skipstep) {
        if (dist_available [b]) {
            for (unsigned int p = 0; p < number_size && numbers [p] + (N -
1) * b <= maxMM; p++)
                asm_num (numbers [p], b);
        }
    }
}

int process () {
    memset (num_available, 0, sizeof (unsigned char) * 125001);
    memset (dist_available, 0, sizeof (unsigned char) * 125001);

    for (unsigned int m1 = 0; m1 <= M; m1++) {
        for (unsigned int m2 = m1; m2 <= M; m2++) {
            int n = m1 * m1 + m2 * m2;

            if (!num_available [n]) {
                num_available [n] = 1;
                numbers [number_size++] = n;
            }
        }
    }

    qsort (numbers, number_size, sizeof (unsigned int), cmp_int);

    maxMM = M * M + M * M;
    for (unsigned int n1 = 0; n1 < number_size; n1++) {
        unsigned int _n1 = numbers [n1];
        for (unsigned int n2 = n1 + 1; n2 < number_size && _n1 + (numbers
[n2] - _n1) * (N - 1) <= maxMM; n2++) {
            assert (numbers [n2] - _n1 >= 0 && numbers [n2] - _n1 < 125001);
            if (num_available [_n1 + (numbers [n2] - _n1) * (N - 1)] &&
                num_available [_n1 + (numbers [n2] - _n1) * (N - 2)])
                dist_available [numbers [n2] - _n1] = true;
        }
    }

    asm_num ();

    if (!have_res) fprintf (fout, "NONE\n");

    return 0;
}

int main () {
    read_input ();
    process ();
    fclose (fin);
    fclose (fout);
    return 0;
}

UaE ProGrammeR

Here is an even faster solution of “UaE ProGrammeR”:

#include <fstream>
#include <iostream>

using namespace std;
void quicksort (int[], int ,int);
int pivotlist (int[], int,int);

ofstream out ("ariprog.out");  

int n;
int main () {
    ifstream in ("ariprog.in");       
                            
    bool array[125001] = {false}, noneF;
    int m, upper, upperdef, def, p; 
    int places[300000], pl = 0;
    noneF = true;
    
    in>>n>>m;
    
    for (int i = 0; i <= m; i++)
        for (int j = 0; j <= m; j++) {
            if (!array[i*i+j*j]) {
                places[pl] = i*i+j*j;   //Saving generated numbers
                pl++;
            }
            array[i*i+j*j] = true;
        }
    
    upper = 2*m*m;
    upperdef = upper/(n-1);
    
    quicksort (places, 0, pl-1);
    
    for ( def = 1; def<=upperdef; def++) // Loop to check for solutions
                                       // It looks for solutions in
                                       // correct order so you 
                                       // print the solution directly
                                       // without sorting first, thnx to who said:
                                       // Trade Memory for Speed !!
    {
        for ( p = 0; places[p]<=(upper-((n-2)*def)); p++) {
            bool is;
            is = true;
            int where;

            for (int c = (n-1); c>=0 ; c--)
                    if (!array[places[p]+c*def]) {
                        is = false;
                        where = (p+c*def);
                        break;
                    }
    
            if (is) {
                noneF = false;
                out<<places[p]<<" "<<def<<endl;
            }
        }
    }
    
    if (noneF)
        out<<"NONE"<<endl;
    
    return 0;
}

void quicksort (int array[], int start, int last) {
    int pivot;
    if (start < last) {
        pivot = pivotlist(array, start,last);
        quicksort (array, start,pivot-1);
        quicksort (array, pivot+1,last);
    }
}

int pivotlist(int array[], int f, int l) {
    int pivotpoint;
    int pivotvalue, temp;
    
    pivotvalue = array[f];
    pivotpoint = f;
    
    for (int i = f+1;i<=l; i++) {
       	if (array[i]<pivotvalue) {	
      	    pivotpoint++;
            temp = array[i];
            array[i] = array[pivotpoint];
            array[pivotpoint] = temp;
   	 }
   }
   temp = array[f];
   array[f] = array[pivotpoint];
   array[pivotpoint] = temp;
   
   return pivotpoint;
}