Truffa al sushi

Ciao, ho provato a risolvere questo CMSocial - a social coding app ma riesco a fare al massimo 84/100. Ho provato diverse soluzioni ma o andavano fuori tempo o sbagliavano. Quella migliore è stata creare un vettore lungo B e per r volte, per ogni elemento in D guardare ogni casella e se l’avevo raggiunta in precedenza allora posso raggiungere anche la j+D[i] esima. E per ogni giro su N e B guardo se ho aggiunto almeno una posizione, in caso contrario mi fermo perché non ne ho aggiunte e non se ne aggiungeranno quindi più.

int sushi(int N, int B, int D[]) {
	int i,j;
	int v[100001];
	for(i=0;i<B+1;++i)v[i]=-1;
	v[0] = 0;
	int r = 0;
	int m;
	int flag;
	while(v[B]==-1){
		++r;
		flag = 1;
		for(i=0;i<N;++i){
			for(j=B-D[i];j>=0;--j){
				if(v[j]!=-1){
					if(v[j+D[i]]!=1)flag = 0;
					v[j+D[i]] = 1;
				}
			}
		}
		if(flag)break;
	}
	if(flag)return -1;
	return r;
}

Qualche consiglio su come si possa migliorare?
Intuitivamente ho capito che era simile a un “coin change” ma non so come modificarlo in maniera da minimizzare il numero di monete diverse e non il numero di monete totali. Ho provato anche approcci più “dp” con strutture dati dinamiche ma uscivano di tempo hmm…

Ho provato a risolvere il problema anche io alla mia maniera e poi a confrontarmi con il tuo codice:
Il risultato e’ che al momento ho una soluzione altrettanto valida e invalida e completamente diversa dalla tua
Sicuramente eseguendo il tuo codice ti posso dire che il time limit exceeded e’ dovuto al while che va all’infinito, perche’ altrimenti non si spiegherebbe come le altre soluzioni con gli stessi ordini di grandezza siano ampiamente nei tempi limiti
Per quella questione ho tentato di mettere su dei testcase che mandassero in loop il programma ma senza successo

Quindi scrivo piu’ che altro me approfitto per aggiungermi alla coda e chiedere se qualcuno piu’ esperto di me riesce a risolvere il problema che ha il mio programma:

const int INF = INT32_MAX;
typedef vector<int> vi;
typedef pair<int, vi> pvi;

int sushi(int n, int b, vector<int> dishes) {
   sort(dishes.begin(), dishes.end()); // serve per una lieve ottimizzazione
   vector<pvi> val(b+1, pvi(INF, vi())); // inizializzo una griglia di (b+1)*(n) per la memoizzazione
   // ogni riga della griglia e' composta da una coppia di un numero che rappresenta il massimo dei piatti dello stesso tipo
   // e da un vettore che contiene il numero di piatti per ogni tipologia
   // se provo a inizializzare da subito la griglia intera vado fuori memoria nell'ultimo subtask,
   // quindi inserisco solo un vettore vuoto
   val[0].first = 0; // caso base, per non spendere niente non si ordina niente
   for (int i = 1; i < b+1; i++) { // scorre i B+1 ipotetici budget
      for (int c = 0; c < n; c++) { // scorre il menu
         if (i-dishes[c] >= 0) { 
            pvi prev = val[i-dishes[c]]; // serve solo per accorciare il codice
            if (prev.second.size() < c+1) prev.second.resize(c+1, 0);
            // se il vettore e' troppo corto per arrivare fino all'indice del piatto, estendilo
            // QUI E' DOVE IL CODICE VA FUORI TEMPO PERCHE' IL RESIZE E' IN O(n)
            if (val[i].first >= max(prev.first, prev.second[c]+1)) { // se prendere quel piatto risulta vantaggioso
               prev.second[c]++; // aumenta nella lista dei piatti ordinati
               prev.first = max(prev.first, prev.second[c]); // aggiorna il risultato della riga
               val[i] = prev; // aggiorna il modo migliore di ordinare
            }
         } else break; // possibile solo se i piatti sono in ordine crescente
      }
   }
   int res = val[x].first;
   return (res == INF) ? -1 : res; // ho controllato che non dia wrong answer
}

grazie in anticipo

1 Mi Piace

A riguardo l’altro giorno ho poi trovato la soluzione dell’autore ed è abbastanza tosta, non sono sicuro se possa condividere il link ma essendo online immagino di si, nel caso qualcuno mi modifichi il messaggio a9StE3 - Online C++0x Compiler & Debugging Tool - Ideone.com