Aiuto Ois_MagnaMagna


#1

Buongiorno. Sto cercando di risolvere ois_magnamagna, e in teoria il codice qui sotto, almeno per i casi di esempio, in locale funziona. Tuttavia il correttore mi segnala tutti i casi errati con una violazione di memoria con signal 9 (che se non sbaglio dovrebbe significare che uso troppa memoria, al contrario del signal 11).
Qualcuno riesce a suggerirmi un modo per diminuire le variabili in uso? Purtroppo non vedrei come poter togliere l’array con cui memoizzo le soluzioni ottime, che, credo, comporterebbe una perdita di tempo non sostenibile. Grazie.

#include <fstream>
#include <string.h>
#include <math.h>
using namespace std;
ifstream in ("input.txt");
ofstream out("output.txt");
int n;
int v[1001];
pair<int,string> memo[1001][1001][2];

double lf, rf;
int l,r;
string g;

string giorgio(int s, int d){
	lf=0; rf=0;
	for(int i=s;i<=d;i++){
		lf+=pow(-1, i-s)*(v[i]/pow(2,i-s));
		rf+=pow(-1, i-s)*(v[d+s-i]/pow(2,i-s));
	}
	if(lf>rf)return "L";
	else if(rf>lf)return "R";
	else return "-1";
}
int rec(int s,int d, int turno){
    
	if(turno==0){
		if(s==d){
			memo[s][d][0].second="R";
			
		return v[s];
		}
		if(memo[s][d][0].first!=-1){
			//return memo[s][d][0];
			
			return memo[s][d][0].first;
			
		}
		
        l=v[s]+rec(s+1,d,1);
        r=v[d]+rec(s, d-1, 1);
		if(l>r){
	
		memo[s][d][0].second="L";
		}	
		else{
		 
		memo[s][d][0].second="R"; 
		}
		memo[s][d][0].first=max(l,r);
		return memo[s][d][0].first;
	}
	else{
		if(s==d){
			
			memo[s][d][1].second="R";
			return 0;
		}
		if(memo[s][d][1].second!="-1"){
			
			return memo[s][d][1].first;
		}
		g=giorgio(s,d);
		
		if(g=="-1"){
		
		l=v[s]+rec(s+1, d, 0);
			r=v[d]+rec(s, d-1, 0);
			if(l>r){
			memo[s][d][1].first=l;
			memo[s][d][1].second="L";
			
			}
			else {
			memo[s][d][1].first=r;
			memo[s][d][1].second="R";
		
			}
			return max(l,r);
		}
		else{
		
		 memo[s][d][1].second=g;
		 if(g=="L")memo[s][d][1].first=rec(s+1, d, 0);
		 else memo[s][d][1].first=rec(s, d-1, 0);
		 return memo[s][d][1].first;
		}
	}
}
int main(){
	in>>n;
	for(int i=0;i<n;i++){
		in>>v[i];
	}
	for(int i=0;i<n;i++){
		for(int y=0;y<n;y++){
			memo[i][y][0].first=-1;
			memo[i][y][0].second="-1";
			memo[i][y][1].first=-1;
			memo[i][y][1].second="-1";
		}
	}
	rec(0, n-1, 0);
	/*for(int i=0;i<n;i++){
		cout<<sol[i]<<" "<<endl;
	}*/
	int o=0;
	int p=n-1;
	int cont=0;
	while(o<=p){
		out<<memo[o][p][cont%2].second<<" ";
		if(memo[o][p][cont%2].second=="L")o+=1;
		else p-=1;
		cont++;
	}
}

EDIT: Probabilmente i testcase non sono fatti benissimo, perché mettendo come grandezza agli array 900, pur essendo il limite n<=1000, il codice totalizza 70/100, senza mai andare fuori memoria. Il problema ora è il tempo per gli ultimi 5 casi, ma anche qui chiedo consigli perché non saprei dove migliorare il codice. Grazie.


#3

Non so se può servire:
Ho provato il tuo codice e mi sembra che dentro memo[][][].second non metti stringhe ma solo un carattere quindi invece di

pair<int,string> memo[1001][1001][2];
mettendo
pair<int,char> memo[1001][1001][2];
e facendo le dovute sostituzioni nelle assegnazioni non si va fuori memoria
inoltre le variabili l e r dovrebbero essere locali alla cur() e non globali
da ultimo ho tolto la stampa dello spazio fra i caratteri (negli esempi non c’è)
Comunque anche così negli ultimi 5 testcase va in time out e fa 70/100.
Se vuoi posto il codice modificato.
Da ultimo la funzione giorgio può anche restituire -1 è un carattere anche lui!.
Peraltro quella funzione mi sembra molto lenta: ricalcolare tutto ogni volta con i numeri double…
mi sa che non c’è memoizzazione che tenga.


#4

A me risulta sizeof(string)=24 byte int 4 byte ma il tutto <int,string> probabilmente viene allineato a 32 byte 1002x1002x2x32=64*1.004.004=64.256.256 byte solo per memo


#5

Grazie per la risposta. In effetti alcune modifiche, come quella delle variabili globali, le avevo già fatte, ma mi ero dimenticato di aggiornate il codice qui sul forum. Usando char al posto di string la memoria va bene. Tuttavia non riesco a capire come potrei modificare il codice, ed eventualmente solo la funzione Giorgio, per renderlo più veloce. Devo cambiare approccio? Grazie.


#6

Su questo non saprei darti un consiglio non ho approfondito la comprensione della tua soluzione a sufficienza, però proverei a velocizzare la funzione Giorgio. La mia soluzione non usa la funzione pow() e precalcola e memorizza sia le potenze di (-.5)^n che tutte le misure destre e sinistre e credo in maniera più rapida. La tua ogni volta ricalcola le potenze di 2^n usando pow e poi dividere per quelle
quando 2^n+1=2*2^n è sicuramente più veloce pow(2,n+1) e tutte queste potenze possono essere calcolate una tantum iterativamente con la formula precedente messe in un array e riutilizzate dentro la Giorgio.
Potrebbe venir fuori qualcosa del genere:

char giorgio(int s, int d){
	double lf, rf;
	int segno;
	lf=0; rf=0;
	for(int i=s;i<=d;i++){
		segno=(i-s)%2==0?1:-1;
		lf+=segno*(v[i]*pow(.5,i-s));
		rf+=segno*(v[d+s-i]*pow(.5,i-s));
		//lf+=pow(-1, i-s)*(v[i]/pow(2,i-s));
		//rf+=pow(-1, i-s)*(v[d+s-i]/pow(2,i-s));
	}
	if(lf>rf)return 'L';
	else if(rf>lf)return 'R';
	else return -1;
}

con le pow sostituite come dicevo sopra. Tentar non nuoce.

P.S. ho provato la tua soluzione ritoccata e con la nuova funzione Giorgio: verdetto 100/100 e senza neanche applicare tutto quello che avevo proposto e neanche il calcolo di segno serve.


#7

Grazie! Ora da 100/100