Aiutino per Olympic Pizza

Aiuto
1

Sto cercando di risolvere questo problema, ma faccio solo 70/100

Questo è più o meno l’algoritmo:

void Order(int N, int *A) {
	if(is_cookable(N, A)) {
		cook_it(N, A);
		Bake(order_num);
	}
	else {
		add_queue(order_num, N, A);
	}
	order_num++;
	return;
}

void Delivery(int I) {
	ing[I]++;
	elaborate_queue();
}

Quindi in pratica faccio la simulazione come richiesto dal problema.

le funzioni is_cookable e cook_it vengono eseguite in O(N) dove N è al massimo 8
add_queue anche viene eseguito in poco più di O(N), perchè copio il vettore A nella coda che è così strutturata:

struct order {
    int ord, N;
    int A[8];
};

deque<order> Q;

mentre elaborate_queue varia in base alla dimenzione della deque

void elaborate_queue() {
	int size = Q.size();
	for(int i = 0; i < size; i++) {
		if(is_cookable(Q[i].N, Q[i].A)) {
			cook_it(Q[i].N, Q[i].A);
			Bake(Q[i].ord);
			Q.erase(Q.begin()+i);
			break;
		}
	}
	return;
}

Ora, per far si che non sfori il tempo di esecuzione, usando questo algoritmo dovrei trovare un modo di avere una coda il cui primo elemento è sempre un ordine che può essere preparato, in questo modo evito la ricerca nell’intera coda.

Il punto è che come posso farlo??

Il problema visto sotto un altro punto di vista potrebbe somigliare ad un problema di query ed update…ma non so…

Qualche consiglio?
2

Sai qualcosa di bitmasking?


Comunque, invece di una deque, io userei una list, dato che ha erase in O(1) e non in O(N)
3
Sai qualcosa di bitmasking?

Comunque, invece di una deque, io userei una list, dato che ha erase in O(1) e non in O(N)

mark03

si già provato con le list, ma non cambia nulla almeno secondo i tempi dati dal correttor

bitmasking per rappesentare gli 8 ingredienti? Ci avevo pensato ma non mi sembrava Una buona idea

In che modo intendi tu?

4

Usando il bitmasking il check passa da O(N) a O(1). Ma ciò che veramente importante è questo: nota che i tipi di pizze sono solo 256 (2^8) mentrebil numero di pizze può arrivare a 100000. Quindi…

5

Posso chiedere lumi sul bitmasking?

6
Posso chiedere lumi sul bitmasking?

marcoBeretta

Ecco qui :)
http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=bitManipulation
7
Posso chiedere lumi sul bitmasking?

marcoBeretta

Ecco qui :)

wil93

Grazie ora guardo!

edit: ho capito come funziona ma non saprei come utilizzarlo per risolvere il problema... un indizio?
edit 2: risolto grazie!
8

Ora ho:
is_cookable in O(1);
cook_it in O(N); //perchè comunque devo tenere per forza un array di interi per tenere conto di QUANTI ingredienti ho.
add_queue in O(1);

e risolvo un testcase in più.

gli ultimi 2 li salta ancora.

Ora la struttura della coda è questa:

struct order {
	int ord;
	char I;
};
list<order> Q;
tengo con un char gli ingredienti della pizza
e così controllo se la pizza si puù fare:

bool is_cookable(char I) {
	return ((ing_ava & I) == I);
}

e la faccio così:

void cook_it(char I) {
	for(int i = 0; i < 8; i++) {
		if((I & 1 << i) != 0) {
			ing_num[i]–;
			if(ing_num[i] == 0) ing_ava &= ~(1 << i);
		}
	}
	return;
}

9
Ora ho:
is_cookable in O(1);
cook_it in O(N); //perchè comunque devo tenere per forza un array di interi per tenere conto di QUANTI ingredienti ho.
add_queue in O(1);

e risolvo un testcase in più.

gli ultimi 2 li salta ancora.

Ora la struttura della coda è questa:

struct order {
	int ord;
	char I;
};
list<order> Q;
tengo con un char gli ingredienti della pizza
e così controllo se la pizza si puù fare:

bool is_cookable(char I) {
	return ((ing_ava & I) == I);
}

e la faccio così:

void cook_it(char I) {
	for(int i = 0; i < 8; i++) {
		if((I & 1 << i) != 0) {
			ing_num[i]--;
			if(ing_num[i] == 0) ing_ava &= ~(1 << i);
		}
	}
	return;
}

simone.pri

Come ho già detto, perchè iterare su 100000 potenziali pizze, quando i tipi effettivi di pizze sono solo 256?
10

E in che modo tengo conto dell’ordine delle pizze?

dovrei avere tipo una struttura del genere:
priority_queue< priority_queue<int, vector<int>, greater<int> >, vector< priority_queue<int> >,  priority_cmp> Q;

una coda di priopriorità di una coda di priorità
la coda contiene al più 256 elementi, (i tipi di pizza) e ogni “tipo” contiene una coda con il numero degli ordini delle pizze di quel tipo (ordinate dal più piccolo al più grande)

Ma sono dubbioso di questa struttura O:

11
E in che modo tengo conto dell'ordine delle pizze?

dovrei avere tipo una struttura del genere:
priority_queue< priority_queue<int, vector<int>, greater<int> >, vector< priority_queue<int> >,  priority_cmp> Q;

una coda di priopriorità di una coda di priorità
la coda contiene al più 256 elementi, (i tipi di pizza) e ogni "tipo" contiene una coda con il numero degli ordini delle pizze di quel tipo (ordinate dal più piccolo al più grande)

Ma sono dubbioso di questa struttura O:

simone.pri

Assolutamente no! Ti basta un array di vector lungo 256 posizioni. Ad ogni pizza corrisponde un posto nell'array e nel vector corrispondente fai il push del numero degli ordini (che sarà, ovviamente, ordinato dato che le pizze vengono date in ordine)
12

Io ho fatto così:

queue<int> V[256];
In realtà ,poi, è la prima cosa a cui avevo pensato,
solo che mi sembrava che l’elaborate impiegasse 256*256
invece giustamente basta solo una ricerca di 256

Scusa per la cavolata D: ahaha

E soprattuto grazie per la mano

13
Io ho fatto così:
queue<int> V[256];
In realtà ,poi, è la prima cosa a cui avevo pensato,
solo che mi sembrava che l'elaborate impiegasse 256*256
invece giustamente basta solo una ricerca di 256

Scusa per la cavolata D: ahaha

E soprattuto grazie per la mano

simone.pri

Di niente :D