Algoritmi - Qualifiche Facebook Hacker Cup - Find The Min

si ma se uso l'insert_order quando ho già qual'è il nodo in cui inserire perdo di efficienza...

a me la lista sembra la struttura migliore per gestire il problema... tra tutti gli algoritmi che ho provato... questo senza nemmeno essere ottimizzato risulta il più veloce...

facebook.com/…

facebook.com/…

Beh, considera che sai a priori quanti elementi gestire, quindi la struttura dati migliore è l'array. E' più compatta, poiché usa un blocco continuo di soli dati, mentre la lista è sparsa e usa molti puntatori e per muoverti da un nodo all'altro devi dereferenziare. Inoltre puoi usare sia accesso sequenziale che casuale.

ma conta che devo avere un doppio ordine...
hai un'ordine di eliminazione.. e un'ordine per determinare gli elementi... con l'array è scomodo...

Io credo di aver risolto(forse ma non penso) comunque non riesco ad allocare array di dimensioni tanto elevate (1000000000 ) elementi come posso risolvere?

non ti serve salvarli tutti quanti in un'array, conta che hai ripetizioni di dimensione k+1, mai di più...

Si ora me ne sono reso conto anch'io pero' sto cercando di ottimizzare il processo di inserimento dei valori superiori a k che mi servono ad arrivare alla 1° ripetizione della successione

Questo è il massimo di ottimizzazione che son riuscito a ottenere...

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

typedef struct findmin_t {
    int num;
    struct findmin_t* prev;
    struct findmin_t* next;
    struct findmin_t* next_del;
    int exist;
} findmin;

findmin *min,*f_del;

void insert_order(findmin *ins,findmin *start) {
    findmin *s;
    if (start!=NULL)
        s=start;
    else
        s=min;
    if (ins->num<=s->num) {
        s->prev=ins;
        ins->next=s;
        min=ins;
    } else {
        while((s->num<ins->num)&&(s->next!=NULL)) {
            s=s->next;
        }
        if (s->num<ins->num) {
            s->next=ins;
            ins->prev=s;
            ins->next=NULL;
        } else {
            ins->prev=s->prev;
            s->prev->next=ins;
            ins->next=s;
            s->prev=ins;
        }
    }
}

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,now;
    findmin *exit=NULL,*l_del,*l_min=NULL,*sup,*l_ins,*found,*ff;
    double db=b,dc=c;
    int stalled=0;
    int l;
    s[0]=a;
    min = (findmin*)malloc(sizeof(findmin));
    min->num=a;
    min->prev=NULL;
    min->next=NULL;
    min->next_del=NULL;
    f_del=l_ins=min;
    for (i=1;i<k;i++) {
        s[i]=(int)(db*s[i-1]+dc)%r;
        sup=(findmin*)malloc(sizeof(findmin));
        sup->num=s[i];
        sup->exist = 1;
        l_ins->next_del=sup;
        insert_order(sup,NULL);
        l_ins=sup;
    }
    l=k;
    printf("loaded!\n");
    for (i=k;i<n;i++) {
        if (stalled) {
            return s[(n-1)%(k+1)];
        } else {
            now=0;
            if (min->num==0) {
                if (l_min==NULL)
                    sup=min;
                else {
                    //Ultimo numero piccolo inserito
                    //Se il numero uscente
                    if (exit->num<l_min->num) {
                        if (l_ins->num<exit->num) {
                            now = l_ins->num;
                            sup = l_ins;
                        }
                        else {
                            now = exit->num;
                            sup = exit;
                        }
                    }
                    else{
                        if (l_ins->num<l_min->num) {
                            now = l_ins->num;
                            sup = l_ins;
                        }else {
                            now = l_min->num;
                            sup = l_min;
                        }
                    }
                    //printf("^%d^ ",now);
                    if (sup->prev!=NULL)
                        sup = sup->prev;
                    //sup=min;
                    //printf("-%d,%d,%d-",exit->num,l_min->num,l_ins->num);
                }
                while((sup->next!=NULL)&&(now>=sup->num)) {
                    if (now==sup->num)
                        now++;
                    else {
                        sup=sup->next;
                    }
                }
                //printf(">%d< ",sup->num);
                if (sup->num==now)
                    now++;
                l_min=sup;
            }
            //Eliminazione
            if (f_del->prev!=NULL) {
                f_del->prev->next = f_del->next;
                f_del->exist = 0;
            } else
                min=f_del->next;
            if (f_del->next!=NULL)
                f_del->next->prev = f_del->prev;
            if (exit!=NULL)
                free(exit);
            exit=f_del;
            f_del=f_del->next_del;
            sup=(findmin*)malloc(sizeof(findmin));
            sup->num=now;
            sup->exist = 1;
            l_ins->next_del=sup;
            if (l_min!=NULL) {
                ff=l_min->prev;
                if (!ff->exist)
                    ff = min;
                while (!ff->exist) {
                    ff = ff->prev;
                    if (ff==NULL)
                        ff=min;
                }
                insert_order(sup,ff);
            }
            else
                insert_order(sup,NULL);

            l_ins=sup;
            s[i%(k+1)]=now;
            //printf("%d (%d)\n",now,exit->num);
            if ((now==k)&&(i%k==0)) stalled=1;
        }
    }
    return now;
}

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;
}

l'output sull'input di piero ristretto ai primi 5 elementi risulta :

i primi 4 valori combaciano il 5 no : a me esce 999900000