Algoritmi - Qualifiche Facebook Hacker Cup - Find The Min

Nota: l'ottimizzazione che avevo in mente era questa:
Fermarmi dopo il ritrovamento della sequenza

#puts '-----Valori conosciuti+minimi calcolati----(n)---------'		
for j in $k..(2*$k)
   m[j]=findmin(j-$k,$k,m)					
end

Da lì calcolare l'ultimo elemento facendo il mod della distanza rimanente tra k e n con la lunghezza della sequenza
per scoprire il valore dell'elemento n-esimo...

Spero che almeno il ragionamento sia giusto ;-)

abbiamo trovato un miglioramento ulteriore, questo :
fuori dal for : ret=(n-1)%(k+1);
dentro il for :
if (i>k+ret) return s[ret];

non cambiare le condizioni del for.. può essere che n sia minore di 2k

Qui il mio codice (C++).

Compilare con -DCPP11 per usare una hash table normale (ci vuole però un compilatore che supporti lo standard C++11)
Senza -DCPP11 viene usata la map del C++ che è sostanzialmente un BST, è un po' più lento.

Note:
- La soluzione è identica all'approccio usato da piero, solo con 2 ottimizzazioni (quelle usate poi anche da Maury).
- C'è un backward goto che fa un po' schifo, ma il codice è talmente breve che ce lo lascio lo stesso

In ogni caso, tempo di esecuzione su core i7 1.5s

#include <iostream>
#include <fstream>

#ifdef CPP11
#include <unordered_map>
#else
#include <map>
#endif

#include <deque>

using namespace std;
typedef unsigned long long ul;

int main() {
	fstream f("test_cases.txt", ios::in);
	if(!f.is_open()) {
		cout << "File not found " << endl;
		return 1;
	}
	ul num_tests, n, k, a, b, c, r;
	ul temp;
	f >> num_tests;
	ul n_tests = num_tests;
	while(num_tests) {
		f 	>> n >> k
			>> a >> b >> c >> r;
		
		#ifdef CPP11
		unordered_map<ul, ul> wnd;	
		#else
		map<ul, ul> wnd;	
		#endif
		
		deque <ul> m(k,0);		
		temp = a;
		m[0] = a;	
		wnd.insert(pair<ul,ul>(a,1));
		for(ul i=1; i<k; ++i) {
			temp = (b*temp + c) %r;
			m[i] = temp;			
			if(wnd.find(temp) != wnd.end()) {
				wnd[temp]++;
			} else {
				wnd.insert(pair<ul,ul>(temp,1));
			}
		}	
		ul next = 0, i = k, m0;
		next = 0;
		while(wnd.find(next) != wnd.end()) 
			next++;
		goto first_el_jump;
		while(i<n) {
			while(wnd.find(++next) != wnd.end());
first_el_jump:
			wnd.insert(pair<ul,ul>(next,1));
skip_search:	
			i++;
			m.push_back(next);
			if(next == k) {
				next = m[(n-i-1)%(k+1)];
				break;
			}
			m0 = m[0];
			m.pop_front();
			if(wnd[m0] == 1) {
				if(m0 > next) {
					wnd.erase(m0);
				} else {
					next = m0;
					goto skip_search;
				}
			} else {
				wnd[m0]--;



			} 	
		}
		cout << "Case #" <<  n_tests - num_tests + 1 << " :" << next << endl;
		num_tests--;
	}		
	return 0;
}

Stanotte ho letteralmente sognato come risolvere il problema!

Ci mette 0.09 secondi!

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

long int testcase(long int a,long int b, long int c, long int r, long int n, long int k) {
    long int s[k+1],i;
    short int m[k+1];
    int l=0,tmp=0,ret=(n-1)%(k+1);
    //Preveniamo errori
    if (k<2) return 0;
    memset(m,0,sizeof(m));
    //Generazione primi k numeri secondo la formula
    s[0]=a;
    if (a<=k)
        m[a]=1;
    for(i=1;i<k;i++)
    {
        long long int tmp1=b%r;
        long long int tmp2=s[i-1]%r;
        long long int ltmp=tmp1*tmp2;
        ltmp=ltmp%r;
        long long int tmp3=ltmp;
        long long int tmp4=c%r;
        long long int final=(tmp3+tmp4)%r;
        s[i]=final;
        //Se il numero è influente mi segno quanti ce ne sono (serve a evitare problemi di numeri ripetuti..)
        if (s[i]<=k)
            m[s[i]]++;
    }
    //printf("\n");
    //Generazione numeri successivi
    for (i=0;i<n-k;i++) {
        //Se siamo oltre il primo passaggio
        if (i>0) {
            //Libero un numero se questo è influente (i numeri maggiori di k non son influenti per l'algoritmo)
            if (s[i-1]<=k)
                m[s[i-1]]--;
            //Se mi ero salvato la posizione di l
            if (tmp) {
                //Reimposto la sua posizione
                l=tmp;
                tmp=0;
            }
            //Se il numero è più piccolo della posizione in cui son arrivato
            if (s[i-1]<l) {
                //Torno indietro e mi salvo la posizione di l (per tornarci dopo)
                tmp=l;
                l=s[i-1];
            }
        }
        //Cerco un buco libero
        while (m[l])
            l++;
        //Segno che non è libero
        m[l]=1;
        //printf("%d ",l);
        //Se son al punto di restituire un risultato
        if (i>ret) return l;
    }
    return l;
}

int main() {
    FILE *f,*f2;
    int cont,i;
    long int n,k,a,b,c,r;
    f = fopen("input.txt","r");
    f2 = fopen("output.txt","w");
    fscanf(f,"%d",&cont);
    for (i=0;i<cont;i++) {
        fscanf(f,"%d %d",&n,&k);
        fscanf(f,"%d %d %d %d",&a,&b,&c,&r);
        printf("Case #%d : %d\n",i+1,testcase(a,b,c,r,n,k));
    }
    fclose(f);
    fclose(f2);
    return 0;
}

Bella soluzione!

son riuscito a ottimizzare ancora, questo è l'output :
Case #1 : 58
Case #2 : 29
Case #3 : 76
Case #4 : 41
Case #5 : 90001
Case #6 : 21563
Case #7 : 573
Case #8 : 0
Case #9 : 6
Case #10 : 12
Case #11 : 38
Case #12 : 19906
Case #13 : 2
Case #14 : 8
Case #15 : 30023
Case #16 : 42
Case #17 : 26
Case #18 : 9999
Case #19 : 3860
Case #20 : 12

Process returned 0 (0x0) execution time : 0.015 s
Press any key to continue.

Questo è il codice :

/*
    Program developed by Maurizio Carboni (maury91@gmail.com)
*/
#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>

int *res;

//long int testcase(long int a,long int b, long int c, long int r, long int n, long int k) {
void testcase(int x[7]) {
    int a=x[1],b=x[2],c=x[3],r=x[4],n=x[5],k=x[6];
    long int s[k+1],i;
    short int m[k+1];
    int l=0,tmp=0,ret=(n-1)%(k+1);
    //Preveniamo errori
    if (k<2) return 0;
    memset(m,0,sizeof(m));
    //Generazione primi k numeri secondo la formula
    s[0]=a;
    if (a<=k)
        m[a]=1;
    for(i=1;i<k;i++)
    {
        long long int tmp1=b%r;
        long long int tmp2=s[i-1]%r;
        long long int ltmp=tmp1*tmp2;
        ltmp=ltmp%r;
        long long int tmp3=ltmp;
        long long int tmp4=c%r;
        long long int final=(tmp3+tmp4)%r;
        s[i]=final;
        //Se il numero è influente mi segno quanti ce ne sono (serve a evitare problemi di numeri ripetuti..)
        if (s[i]<=k)
            m[s[i]]++;
    }
    //printf("\n");
    //Generazione numeri successivi
    for (i=0;i<=ret+1;i++) {
        //Se siamo oltre il primo passaggio
        if (i>0) {
            //Libero un numero se questo è influente (i numeri maggiori di k non son influenti per l'algoritmo)
            if (s[i-1]<=k)
                m[s[i-1]]--;
            //Se mi ero salvato la posizione di l
            if (tmp) {
                //Reimposto la sua posizione
                l=tmp;
                tmp=0;
            }
            //Se il numero è più piccolo della posizione in cui son arrivato
            if (s[i-1]<l) {
                //Torno indietro e mi salvo la posizione di l (per tornarci dopo)
                tmp=l;
                l=s[i-1];
            }
        }
        //Cerco un buco libero
        while (m[l])
            l++;
        //Segno che non è libero
        m[l]=1;
    }
    res[x[0]]=l;
}

int main() {
    FILE *f,*f2;
    int cont,i,*vett;
    long int n,k,a,b,c,r;
    f = fopen("input.txt","r");
    f2 = fopen("output.txt","w");
    fscanf(f,"%d",&cont);
    pthread_t pth[cont];
    res=(int*)malloc(sizeof(int)*cont);
    for (i=0;i<cont;i++) {
        fscanf(f,"%d %d",&n,&k);
        fscanf(f,"%d %d %d %d",&a,&b,&c,&r);
        vett = (int*)malloc(sizeof(int)*7);
        vett[0]=i;
        vett[1]=a;vett[2]=b;vett[3]=c;vett[4]=r;vett[5]=n;vett[6]=k;
        pthread_create(&pth[i],NULL,testcase,vett);
    }
    for (i=0;i<cont;i++) {
        pthread_join(pth[i],NULL);
    }
    for (i=0;i<cont;i++) {
        fprintf(f2,"Case #%d : %d\n",i+1,res[i]);
    }

    fclose(f);
    fclose(f2);
    return 0;
}

Belle soluzioni!

Grazie per il vostro aiuto!