Algoritmi - Qualifiche Facebook Hacker Cup - Find The Min

Forum - Algoritmi - Qualifiche Facebook Hacker Cup - Find The Min

Pagine: [ 1 2 3 4 5 ]

pierotofy (Admin)
Guru^2

Messaggi: 6230
Iscritto: 04/12/2003

Postato alle 20:05
Sabato, 26/01/2013

Facebook Hacker Cup: https://www.facebook.com/hackercup?fref=ts

Qualcuno e' riuscito a risolverlo con un algoritmo veloce? (Deve terminare entro 5 minuti).

Problema:

Testo quotato

After sending smileys, John decided to play with arrays. Did you know that hackers enjoy playing with arrays? John has a zero-based index array, m, which contains n non-negative integers. However, only the first k values of the array are known to him, and he wants to figure out the rest.

John knows the following: for each index i, where k <= i < n, m[ i] is the minimum non-negative integer which is *not* contained in the previous *k* values of m.

For example, if k = 3, n = 4 and the known values of m are [2, 3, 0], he can figure out that m[3] = 1.

John is very busy making the world more open and connected, as such, he doesn't have time to figure out the rest of the array. It is your task to help him.

Given the first k values of m, calculate the nth value of this array. (i.e. m[n - 1]).

Because the values of n and k can be very large, we use a pseudo-random number generator to calculate the first k values of m. Given positive integers a, b, c and r, the known values of m can be calculated as follows:

m[0] = a
m[i ] = (b * m[i - 1] + c) % r, 0 < i < k
Input
The first line contains an integer T (T <= 20), the number of test cases.
This is followed by T test cases, consisting of 2 lines each.
The first line of each test case contains 2 space separated integers, n, k (1 <= k <= 105, k < n <= 109).
The second line of each test case contains 4 space separated integers a, b, c, r (0 <= a, b, c <= 109, 1 <= r <= 109).
Output
For each test case, output a single line containing the case number and the nth element of m.

Input di esempio:

Testo quotato

5
97 39
34 37 656 97
186 75
68 16 539 186
137 49
48 17 461 137
98 59
6 30 524 98
46 18
7 11 9 46

Output:

Testo quotato

Case #1: 8
Case #2: 38
Case #3: 41
Case #4: 40
Case #5: 12

Input usato per la valutazione (questo dev'essere eseguito in meno di 5 minuti):

Testo quotato

20
131 74
1 9 10 78736
177 73
7 7 5 56401
164 96
76 2 193 164
137 49
48 17 461 137
1000000000 100000
999999999 1 999999999 1000000000
249718282 93729
1 5 6 999917908
640834505 28785
3 9 1 999946125
1000000000 1
12 7 74 12
28 21
6 5 1 85919
59 26
14 19 681 59
186 75
68 16 539 186
232959116 56689
4 9 1 999903057
110 53
7 7 1 64417
97 39
34 37 656 97
714311129 39521
9 5 9 999998192
220 88
1 8 3 58265
78 51
3 5 5 51230
1000000000 100000
99999 1 99999 100000
977365070 59489
8 5 9 999966210
46 18
7 11 9 46

Questa e' la mia soluzione (troppo lenta):

Codice sorgente - presumibilmente Delphi

#!/usr/bin/ruby
 
counter = 0
numElements = 0
file = File.new("find_the_mintxt.txt", "r")
while (line = file.gets)
    counter = counter + 1
        if counter == 1
                numElements = line.to_i
        else
                nkline = line.chomp
                abcrline = file.gets.chomp
                m = []
                n,k = nkline.split(' ')[0].to_i, nkline.split(' ')[1].to_i
                a,b,c,r = abcrline.split(' ')[0].to_i, abcrline.split(' ')[1].to_i,  abcrline.split(' ')[2].to_i,  abcrline.split(' ')[3].to_i
 
                dic = {}
                dic[a] = 1
 
                m[0] = a
                for i in 1..(k - 1)
                        m[i] = (b * m[i - 1] + c) % r
                        if dic[m[i]]
                                dic[m[i]] += 1
                        else
                                dic[m[i]] = 1
                        end
                end
 
                for i in k..(n - 1)
                        c = 0
                        c += 1 while not dic[c].nil? #<---- LENTO, come si fa ad accelerare?
                        m[i] = c
 
                        if dic[m[i]]
                                dic[m[i]] += 1
                        else
                                dic[m[i]] = 1
                        end
                        
                        dic[m[i - k]] -= 1
                        dic.delete(m[i - k]) if dic[m[i - k]] == 0
                end
 
        puts "Case ##{counter - 1}: #{m[n-1]}"
        end
end
file.close

Che ne pensate?

Ultima modifica effettuata da pierotofy il 26/01/2013 alle 20:06

Il mio blog: https://piero.dev

tasx (Dev Team)
Expert

Messaggi: 439
Iscritto: 15/12/2008

Postato alle 21:05
Sabato, 26/01/2013

Urca tra poco ci arrivo... sbrigo il secondo e arrivo

Maury91 (Member)
Expert

Messaggi: 531
Iscritto: 18/09/2006

Postato alle 3:09
Domenica, 27/01/2013

Testo quotato

Postato originariamente da pierotofy:

Problema:

Testo quotato

Input di esempio:

Testo quotato

5
97 39
34 37 656 97
186 75
68 16 539 186
137 49
48 17 461 137
98 59
6 30 524 98
46 18
7 11 9 46

Output:

Testo quotato

Case #1: 8
Case #2: 38
Case #3: 41
Case #4: 40
Case #5: 12

Ho creato i primi k valori di m con la formula
m[0]=a;
m=(b*m[i-1]+c)%r;

e mi torna che m contiene :
34 71 82 4 28 43 16 84 78 50 81 64 17 24 89 69 8 79 87 92 83 41 39 62 40 2 51 21 75 36 48 7 42 76 73 59 26 66 91

come può il risultato (ovvero l'n-esimo valore di m) essere 8 se 8 è contenuto in già nei primi k elementi?

Magari ho capito male il testo...
quello che ho capito è questo :

i primi k valori della matrice son calcolati secondo la formula che danno loro e con le loro variabili...

i valori da k a n li dobbiamo calcolare noi.. e sappiamo che ogni valore che calcoliamo è il valore minimo che non è contenuto nella parte antecedente della matrice..

se è come ho capito questo è il codice che ho pensato :

Codice sorgente - presumibilmente C++

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

int comp(const int * a,const int * b)
{
if (*a==*b)
return 0;
else
if (*a < *b)
return -1;
else
return 1;
}

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],i,p,now;
s[0]=a;
for (i=1;i<k;i++)
s[i]=(b*s[i-1]+c)%r;
//Ordino l'array
qsort(s,k,sizeof(long int),comp);
//Setto che il numero a cui sono ora è 0 e l'elemento di s che controllo è 0
now=p=0;
for (i=k;i<n;i++) {
while(now>=s[p]) {
if (now==s[p])
now++;
else
p++;
}
now++;
}
return now-1;
/*for (i=0;i<n;i++)
printf("%d ",m[i]);*/
}

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);
fprintf(f2,"Case #%d : %d\n",i+1,testcase(a,b,c,r,n,k));
}
fclose(f);
fclose(f2);
return 0;
}

L'ho provato sui dati di piero... ci mette circa 30 secondi

Ultima modifica effettuata da Maury91 il 27/01/2013 alle 3:28

pierotofy (Admin)
Guru^2

Messaggi: 6230
Iscritto: 04/12/2003

Postato alle 4:22
Domenica, 27/01/2013

I primi *k* elementi, nel senso che ad ogni indice i devi considerare i k elementi precedenti.

Ad esempio, se k = 5 e n = 10, per i = 8 devi considerare gli elementi 3,4,5,6,7 (5 elementi precedenti, omettendo 0,1,2).

Il mio blog: https://piero.dev

Maury91 (Member)
Expert

Messaggi: 531
Iscritto: 18/09/2006

Postato alle 5:52
Domenica, 27/01/2013

ok capito..
ho tentato questa soluzione ma si impalla... ma credo il ragionamento sia corretto :

Codice sorgente - presumibilmente C++

#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;
} findmin;
 
findmin *min,*f_del;
 
void insert_order(findmin *ins) {
    findmin *s;
    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],ii,i,p,now,to_del;
    findmin *max,*l_del,*l_min=NULL,*sup,*l_ins;
    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]=(b*s[i-1]+c)%r;
        sup=(findmin*)malloc(sizeof(findmin));
        sup->num=s[i];
        l_ins->next_del=sup;
        insert_order(sup);
        l_ins=sup;
    }
    for (i=k;i<n;i++) {
        now=0;
        if (min->num==0) {
            //if (l_min==NULL)
                sup=min;
            /*else {
                sup=l_min;
            }*/
            while((sup->next!=NULL)&&(now>=sup->num)) {
                if (now==sup->num)
                    now++;
                else {
                    sup=sup->next;
                }
            }
            if (sup->next==NULL)
                now=sup->num+1;
            l_min=sup;
        }
 
        //Eliminazione
        if (f_del->prev!=NULL)
            f_del->prev->next = f_del->next;
        else
            min=f_del->next;
        if (f_del->next!=NULL)
            f_del->next->prev = f_del->prev;
        sup=f_del;
        f_del=f_del->next_del;
        free(sup);
        sup=(findmin*)malloc(sizeof(findmin));
        sup->num=now;
        l_ins->next_del=sup;
        insert_order(sup);
        l_ins=sup;
    }
    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;
}

Ultima modifica effettuata da Maury91 il 27/01/2013 alle 7:00

Il Totem (Admin)
Guru^2

Messaggi: 3635
Iscritto: 24/01/2006

Postato alle 13:37
Domenica, 27/01/2013

Secondo me c'è qualche trucco per dedurre il nuovo elemento. Qualsiasi algoritmo con complessità lineare non può andar bene (e non c'è modo di scendere al di sotto di O(n) con questo approccio).

Maury91 (Member)
Expert

Messaggi: 531
Iscritto: 18/09/2006

Postato alle 14:24
Domenica, 27/01/2013

Testo quotato

Postato originariamente da Il Totem:

Secondo me c'è qualche trucco per dedurre il nuovo elemento. Qualsiasi algoritmo con complessità lineare non può andar bene (e non c'è modo di scendere al di sotto di O(n) con questo approccio).

allora ho scoperto le seguenti cose :
esiste una serie di k+1 elementi che si ripete sempre, quindi basta calcolare questi...

ho trovato un modo per "dedurre il nuovo elemento" ma sto avendo alcuni problemi a ottimizzare il codice

Codice sorgente - presumibilmente C++

#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;
} findmin;
 
findmin *min,*f_del;
 
void insert_order(findmin *ins) {
    findmin *s;
    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;
    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]=(b*s[i-1]+c)%r;
        sup=(findmin*)malloc(sizeof(findmin));
        sup->num=s[i];
        l_ins->next_del=sup;
        insert_order(sup);
        l_ins=sup;
    }
    l=k;
    for (i=k;i<n;i++) {
        if (stalled) {
            now=s[i%(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;
            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;
            l_ins->next_del=sup;
            
            //Qua sta il problema non riesco a fare l'inserimento ordinato con questo codice... si crea uno scompenso e il risultato risulta diverso...
 
            /*if (l_min->prev != NULL)
                printf("\n>>%d %d %d - %d<<\n",l_min->prev->num,sup->num,l_min->num,min->num);
            else
                printf("\n>>%d %d<<\n",sup->num,l_min->num);*/
            /*if (sup->num<min->num){
                min->prev=sup;
                sup->next=min;
                min=sup;
            } else {
                //Se è la fine
                if (sup->num>=l_min->num){
                    l_min->next=sup;
                    sup->prev=l_min;
                    sup->next=NULL;
                } else {
                    sup->prev=l_min->prev;
                    l_min->prev->next=sup;
                    sup->next=l_min;
                    l_min->prev=sup;
                }
            }*/
 
            insert_order(sup);
 
            l_ins=sup;
            s[i%(k+1)]=now;
            //printf("\n%d ",now);
            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;
}

il mio scopo è aumentare l'efficienza dell'algoritmo non usando insert_order quando inserisco i nuovi visto che per rilevare quale numero mettere ho già gli elementi tra i quali inserirlo... non riesco a capire cosa c'è di sbagliato nella parte commentata visto che impazzisce...

Ultima modifica effettuata da Maury91 il 27/01/2013 alle 14:32

Il Totem (Admin)
Guru^2

Messaggi: 3635
Iscritto: 24/01/2006

Postato alle 14:37
Domenica, 27/01/2013

Probabilmente quella serie è dovuta all'algoritmo che genera i numeri pseudocasuali. Comunque una lista non è la struttura dati migliore. E poi se mischi il codice che gestisce la lista con quello che risolve il problema non si capisce molto: sono su due livelli di astrazione diversi.

Maury91 (Member)
Expert

Messaggi: 531
Iscritto: 18/09/2006

Postato alle 14:39
Domenica, 27/01/2013

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...

http://www.facebook.com/photo.php?fbid=4859555939057&set=a ...

http://www.facebook.com/photo.php?fbid=4859688902381&set=a ...

Ultima modifica effettuata da Maury91 il 27/01/2013 alle 15:00

Pagine: [ 1 2 3 4 5 ]