Problema esame - ABC 2016

Aiuto
1

Un saluto a tutti!
Sono in difficoltà con il problema “esame”; in pratica la soluzione che do passa tutti i subtask tranne il #3, #6 e #11. RIsultato: 10/100. :anguished:

La soluzione credo essere in programmazione dinamica. Calcolo quindi le soluzioni ottimali per un esame con solo il prof 0, con 0 e 1 (il massimo fra i due), per i successivi parte l’algoritmo “dinamico” calcolando il massimo fra la soluzione dinamica già calcolata fino al prof precedente (senza considerare il corrente) e la somma fra il prof corrente e la dinamica di due indici prima.

Arrivati all’ultimo elemento bisogna tenere in considerazione il primo elemento, in modo che non compaiano entrambi. Tengo un vettore di bool assieme alle soluzioni dinamiche per ricordarmi se la soluzione ad indice i contiene o meno l’elemento ad indice 0; arrivato all’ultimo indice mi regolo di conseguenza.

Temo di essermi spiegato in modo poco comprensibile, però stasera non mi riesce di meglio :smile: se qualcuno avesse già risolto, o avesse idee, sarebbe assai gradito. Per completezza incollo il codice :slight_smile:

#include <cstdio>
#include <vector>
#define MAXN 1000

FILE * fr, * fw;

int teacher[MAXN];
int n = 0;

int solve(){	
	int dynamic[n];
	dynamic[0] = teacher[0];
	
	std::vector<bool> first_used (n, true);
	
	if (teacher[0] > teacher[1])
		dynamic[1] = teacher[0];
	else{
		dynamic[1] = teacher[1];
		first_used[1] = false;
	}
	
	int i;
	for (i = 2; i<n-1; i++){
		if (dynamic[i-1] > dynamic[i-2]+teacher[i]){
			dynamic[i] = dynamic[i-1];
			first_used[i] = first_used[i-1];
		}
		else{
			dynamic[i] = dynamic[i-2]+teacher[i];
			first_used[i] = first_used[i-2];
		}	
	}
	
	//check if i-2 uses first element
	if (first_used[i-2]){
		//maximum between: i-1, i-2 with last, i-2 with first
		
		if (dynamic[i-1] >= dynamic[i-2]+teacher[i]-teacher[0] &&
				dynamic[i-1] >= dynamic[i-2]){
			// use i-1
			dynamic[i] = dynamic[i-1];
		}
		
		else if (dynamic[i-2] >= dynamic[i-1] + teacher[i] - teacher[0]){
			//use i-2 with first
			
			dynamic[i] = dynamic[i-2];
		}
		else{
			//use i-2 without first, with last
			dynamic[i] = dynamic[i-2] + teacher[i] - teacher[0];
		
		}
	}
	else{
		//first element not used in optimal solution - execute loop one more time 
		if (dynamic[i-1] > dynamic[i-2]+teacher[i]){
			dynamic[i] = dynamic[i-1];
			first_used[i] = first_used[i-1];
		}
		else{
			dynamic[i] = dynamic[i-2]+teacher[i];
			first_used[i] = first_used[i-2];
		}
	}
	
	
	int max_d = -1;
	for (int i = 0; i<n; i++){
		if (max_d < dynamic[i])
			max_d = dynamic[i];
	}
	
	return max_d;
}

int main(){
	fr = fopen ("input.txt", "r");
	fw = fopen ("output.txt", "w");
	
	fscanf (fr, "%d", &n);
	
	for (int i = 0; i<n; i++)
		fscanf (fr, "%d", teacher+i);
	
	fprintf (fw, "%d", solve());
	
	fclose (fr);
	fclose (fw);
	return 0;
}

( http://pastebin.ubuntu.com/23068166/ )

2

Ciao,
Praticamente l’errore si trova nel momento in cui consideri l’ultimo numero: se la soluzione contiene l’indice zero giustamente lo togli, ma togliendolo potrebbe capitare che sia possibile prenderne altri.
Prova a considerare questo input:
6
8 1 4 5 1 9
Una volta arrivati al 9 avrai:
dinamic[3]=13;
dinamic[2]=12:
first_used[3]=true;
first_used[2]=true;
Il tuo programma stampa come soluzione ottimale
dinamic[3]+teacher[5]-teacher[0]=14
Ma non tiene in considerazione che togliendo teacher[0] puoi prendere teacher[1] ottenendo 15

4 Mi Piace
3

Quoto quanto detto da Mr_Brionix :slight_smile:
Se il problema sorge quando togli dalla soluzione il prof 0, come fai a evitare il conflitto senza toglierlo dalla soluzione dopo averlo considerato? Anche se dovessi far partire due volte la funzione di DP, considera che tra una soluzione in O(x) e una soluzione in O(2x) nella pratica c’è poca differenza :wink:

4

Grazie mille!!!
Ero entrato in crisi anche perché non riuscivo ad indovinare un input che mi desse l’errore :grin: ora è tutto chiaro.
Da oggi in poi le soluzioni già calcolate della dp non le tocco più :stuck_out_tongue_winking_eye:

In breve la correzione: ho ampliato l’array dynamic a 2*n; calcolo una volta le soluzioni eliminando il primo elemento e una volta eliminando l’ultimo. Vettore di bool non più necessario, come nemmeno le condizioni dopo il ciclo.

#include <cstdio>
#define MAXN 1000

FILE * fr, * fw;

int teacher[MAXN];
int n = 0;

int solve(){	
	int dynamic[2*n];
	for (int i = 0; i<2*n; i++)
		dynamic[i] = -1;
	
	dynamic[0] = teacher[0];
	
	if (teacher[0] > teacher[1])
		dynamic[1] = teacher[0];
	else
		dynamic[1] = teacher[1];
	
	int i;
	for (i = 2; i<n-1; i++){
		if (dynamic[i-1] > dynamic[i-2]+teacher[i])
			dynamic[i] = dynamic[i-1];
			
		else
			dynamic[i] = dynamic[i-2]+teacher[i];
	}
	
	dynamic[n] = teacher[n-1];
	if (teacher[n-1] > teacher[0])
		dynamic[n+1] = teacher[n-1];
	else
		dynamic[n+1] = teacher[0];
	
	for (int j = 1; j<n-2; j++){
		if (dynamic[n+j] > dynamic[n+j-1]+teacher[j])
			dynamic[n+j+1] = dynamic[n+j];
			
		else
			dynamic[n+j+1] = dynamic[n+j-1]+teacher[j];
	}
	
	int max_d = -1;
	for (int i = 0; i<2*n; i++){
		if (max_d < dynamic[i])
			max_d = dynamic[i];
	}
	
	return max_d;
}

int main(){
	fr = fopen ("input.txt", "r");
	fw = fopen ("output.txt", "w");
	
	fscanf (fr, "%d", &n);
	
	for (int i = 0; i<n; i++)
		fscanf (fr, "%d", teacher+i);
	
	fprintf (fw, "%d", solve());
	
	fclose (fr);
	fclose (fw);
	return 0;
}

( http://pastebin.ubuntu.com/23070165/ )

Grazie ancora a tutti per l’aiuto

1 Mi Piace