Oppure

Loading
26/01/13 19:05
pierotofy
Facebook Hacker Cup: facebook.com/…

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

Problema:

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:
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:
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):
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): 

#!/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 26/01/13 19:06
Il mio blog: piero.dev
26/01/13 20:05
tasx
Urca tra poco ci arrivo... sbrigo il secondo e arrivo ;)
aaa
27/01/13 2:09
Maury91
Postato originariamente da pierotofy:


Problema:

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:
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:
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[i]=(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 : 
#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 27/01/13 2:28
aaa
27/01/13 3:22
pierotofy
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: piero.dev
27/01/13 4:52
Maury91
ok capito..
ho tentato questa soluzione ma si impalla... ma credo il ragionamento sia corretto : 
#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 27/01/13 6:00
aaa
27/01/13 12:37
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).
aaa
27/01/13 13:24
Maury91
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 

#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 27/01/13 13:32
aaa
27/01/13 13:37
Il Totem
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.
aaa