Espressioni senza operatori

Ho un problema con il problema eso...
La mia idea è costruire un albero per ogni sequenza eso tenendo in ogni nodo un bool per sapere se la parentesi che identifica è tonda o quadra, la sequenza dei numeri e i puntatori ai nodi successivi. Nella sequenza dei numeri inserisco tutti i numeri positivi e per identificare una sotto-parentesi un numero negativo man mano decrescente partendo da -5. In questo modo quando c'è un numero negativo so che al suo posto devo mettere la sequenza di numeri di un sotto-nodo, in particolare -5 corrisponde al primo sotto-nodo della lista, -6 al secondo, ...
Dopo aver costruito tutti gli alberi decido di ordinare tutte le sequenze di numeri di tutti i nodi: se il nodo identifica una parentesi tonda ordino la sequenza in senso crescente, se la parentesi è quadra controllo se il primo numero è maggiore dell'ultimo e se sì ribalto la sequenza.
A questo punto ho ordinato l'albero sfruttando le regole delle parentesi e costruisco una lista di soli numeri interi per ogni albero. Controllando quante e quali liste sono uguali arrivo alla soluzione.
L'algoritmo mi sembra corretto però risolve solo i primi due test-case e sbaglia tutti gli altri senza andare in time-out. Dove sbaglio?

Infatti l’algoritmo è corretto. Io l’ho fatto senza costruirmi l’albero, ma il concetto è identico. Semplicemente al momento dell’acquisizione vedo tutte le sequenze tra parentesi (non spiego come, è facile arrivarci) e metto tutte le sequenze in una map che ha come identificativo la sequenza stessa e come valore l’intero negativo. Se una determinata sequenza viene trovata nella map (così come hai fatto tu, solo che controllo sia in un verso che nell’altro nel caso delle quadre. Hai pensato se il primo e l’ultimo numero nelle parentesi quadre sono uguali?), sostituisco l’intero all’interno della sequenza originale, se non l’ho trovata creo un nuovo intero (decrementando l’ultimo intero utile) e la inserisco nella map.

Come vedi è molto simile, ma l’ho fatto senza alberi (la map dovrebbe implementare un heap già di suo).

PS: Ovviamente la map dev’essere comune per tutte le sequenze. Non ho capito bene se a te due sotto-sequenze uguali in sequenze diverse hanno lo stesso intero. Magari prova a postare il codice

Hai pensato se il primo e l’ultimo numero nelle parentesi quadre sono uguali?

Il testo dice “All’interno di una ESO non ci sono due numeri positivi uguali e non ci sono coppie di parentesi vuote, ovvero () oppure [], senza alcun elemento interno.”

Il codice è qua:

#include <algorithm>
#include <stdio.h>
#include <stdlib.h>
#include <deque>
#include <string>
#include <math.h>

using namespace std;

class Nodo{
	public:
		bool tonda;
		deque<int> num;
		deque<class Nodo*> succ;
};

// costrusco ricorsivamente l'albero della sequenza passata per parametro e ritorno un puntatore alla radice al main
Nodo* insert(int vet[], int s, int e){
	
	Nodo* node;
	node = new Nodo();
	
	if(vet[s] == -1)
		node->tonda = true;
	else
		node->tonda = false;

	node->num.resize(0);
	s++;
	e--;
	
	int i;
	int neg = -5;
	for(i=s; i<=e; i++)
		if(vet[i] > 0)
			node->num.push_back(vet[i]);
		else{
			int par = 1;
			int _s = i;
			int _e;
			while(par != 0){
				
				i++;
				if(vet[i] == -1 || vet[i] == -3)
					par++;
				else
					if(vet[i] == -2 || vet[i] == -4)
						par--;
			}
			_e = i;
			node->succ.push_back(insert(vet, _s, _e));
			node->num.push_back(neg);
			neg--;
		}
	
	return node;
}
/*
void visit(Nodo* node, int num){
	printf("\n<%d> %d:\t",node->tonda, num);
	for(int i=0; i<node->num.size(); i++)
		printf("%4d", node->num[i]);
		
	for(int i=0; i<node->succ.size(); i++)
		visit(node->succ[i], 0-i-5);
}
*/

// costruisco la sequenza senza parentesi e la ritorno al main
deque<int> getSeq(Nodo* node){
	
	deque<int> out;
	
	for(int i=0; i<node->num.size(); i++)
		if(node->num[i] >= 0)
			out.push_back(node->num[i]);
		else{
			deque<int> t = getSeq(node->succ[0-node->num[i]-5]);
			for(int j=0; j<t.size(); j++)
				out.push_back(t[j]);
		}
			
	
	return out;
}

// ordino tutte le sequenze di numeri dei nodi
void order(Nodo* node){
	
	// se la parentesi è tonda ordino tutto in modo crescente
	if(node->tonda)
		sort(node->num.begin(), node->num.end());
	else
		// altrimenti la parentesi è quadra, e se il primo numero è maggiore dell'ultimo ribalto la sequenza
		if(node->num.size() > 1)
			if(node->num[0] > node->num[node->num.size()-1]){
				for(int i=0; node->num.size()-i-1 > i; i++)
					swap(node->num[i], node->num[node->num.size()-i-1]);
			}
	
	// ordino tutti i sottonodi
	for(int i=0; i<node->succ.size(); i++)
		order(node->succ[i]);
	
}

main(){
	FILE *pF = fopen("input.txt","r");
  	int n,m;
  	fscanf(pF,"%d %d",&n,&m);

  	int i,j,c;
  	int vet[m];
  	
  	deque<class Nodo*> eso;
  	
  	for(c=0;c<n;c++){
     	fscanf(pF,"\n%d",&vet[0]);
     	for(j=1;j<m;j++)
        	fscanf(pF," %d",&vet[j]);
        	
        // costruisco l'albero
        eso.push_back(insert(vet, 0, m-1));
        
  	}
  	fclose(pF);
  	
  	
  	deque<deque<int> > ris;
  	for(i=0; i<eso.size(); i++){		
        // ordino l'albero
        order(eso[i]);
        // costruisco le sequenze ordinate
        ris.push_back(getSeq(eso[i]));
  	}
		
  	
  	// count[i] contiente il numero delle sequenze uguali alla (i+1)^ sequenza compresa se stessa
  	int count[n];
  	for(i=0; i<n; i++)
  		count[i] = 0;
  		
  	// lista delle posizioni delle sequenze uguali alla (i+1)^ sequenza compresa se stessa
  	deque<deque<int> > position(n);
  	position[0].push_back(1);
  	count[0] = 1;
  	int flag;
  	
  	// per tutte le sequenze tranne la prima
  	for(i=1; i<ris.size(); i++){
		// controllo se è uguale a una delle sequenze precedenti
		for(j=0; j<i; j++){
			
			flag = 1;
			
			for(c=0; c<ris[i].size(); c++)
				if(ris[i][c] != ris[j][c]){
					flag = 0;
					break;
				}
			
			// se si incremento count e aggiungo la posizione alla lista
			if(flag){
				count[j]++;
				position[j].push_back(i+1);
				break;
			}
			
		}
		
		// altrimenti creo un nuovo gruppo
		if(!flag){
			count[i]++;
			position[i].push_back(i+1);
		}
		
  	}
  	
  	pF = fopen("output.txt", "w");
  	c = 0;
  	for(i=0; i<n; i++)
  		if(count[i] > 0)
  			c++;
  	fprintf(pF, "%d", c);
  	for(i=0; i<n; i++)
  		if(count[i] > 0){
			fprintf(pF, "\n%d", count[i]);
			for(j=0; j<position[i].size(); j++)
				fprintf(pF, " %d", position[i][j]);
  		}
  	fclose(pF);
}

( http://pastebin.com/grvaAmq4 )

Hai pensato se il primo e l'ultimo numero nelle parentesi quadre sono uguali?

Il testo dice "All’interno di una ESO non ci sono due numeri positivi uguali e non ci sono coppie di parentesi vuote, ovvero () oppure [], senza alcun elemento interno."

marcoBeretta


Ah va bene, non avevo letto.

Il tuo codice ha proprio l'errore che pensavo. Ad ogni ESO ricominci il conteggio da -5, mentre in realtà dovresti mantenere le ESO che hai salvato in precedenza (con il relativo intero negativo che le identifica) e ricominciare il conteggio dall'ultimo intero utile. Come fai tu finirai inevitabilmente a considerare uguali due ESO che non lo sono, ma che hanno la stessa sequenza di interi pur non avendo le stesse "sotto-ESO".

Sicuro di quello che dici? Quando chiama la funzione getSeq sostituisco a tutti i numeri negativi le sottosequenze che stanno sotto nell’albero quindi nella sequenza finale non ci sono parentesi.

Inoltre ogni nodo ha la sua sequenza di sotto nodi che può essere identificata univocamente,(-5 uguale indice 0, -6 uguale 1, …)

Forse non ho capito per bene il tuo algoritmo, ma credo che il tuo ricominciare sempre da -5 per ogni ESO sia un errore. Inoltre ho appena notato che chiami la procedura swap, mentre dovresti richiamare reverse. Swap scambia i valori iniziale e finale, mentre tu devi ribaltare tutta la sequenza.

Quando chiamo la swap lo faccio in un ciclo per avere lo stesso effetto della reverse (che non sapevo esistesse), infatti adesso ho messo la reverse e l’effetto è lo stesso.

Inoltre continuo a non capire il fatto di ricominciare sempre da -5… ricomincio da -5 in ogni nodo perchè è un’informazione che resta dentro il nodo stesso e non dovrebbe andare ad influenzare altri nodi o altre eso…

Invece dovrebbe. Mettiamo che tu abbia questa ESO:

( 1 2 3 ( 1 2 ) [ 3 4 ] ( 2 1 ) ( 2 5 ) )
In questo caso dovresti analizzare l’ESO partendo dalle parentesi interne ed ottenere un risultato del genere dopo il primo passaggio:
( 1 2 3 -5 -6 -5  -7 )
Dopo di che ordini questa sequenza e le assegni in altro intero negativo (-7).
Poi cominci con la ESO successiva, che potrebbe essere questa:
( 1 ( 1 2 ) 2 [ 4 3 ] 3 ( 1 2 3 ) )
Questa avrà dopo il primo passaggio questa sequenza:
( 1 -5 2 -6 3 -8 )
Ordini e le assegni un altro numero negativo (-9).
Come puoi notare tra le due ESO gli interi -5 e -6 rappresentano la stessa sequenza.
Facendo questo lavoro per tutte le ESO dell’input ridurrai il lavoro ad un semplice confronto tra interi.

Non mi sembra che il tuo programma faccia questo

Non è vero che "tra le due ESO gli interi -5 e -6 rappresentano la stessa sequenza" perchè all'interno del nodo c'è anche una lista di puntatori a sottonodi in cui sono contenute le reali sottosequenze.

Nella prima ESO -5 farà riferimento ad un sottonodo con la sequenza 1 2, -6 corrisponderà a 3 4, ... continuo a non capire...

Queste sono le sequenze di interi che finiscono nella deque "ris". Queste sono le sequenze che comparo alla fine...

ESO 1:
 45 18 21 91 72 81 29 47 84 65 12 15 19 34 58
ESO 2:
 12 65 47 84 29 81 72 91 18 21 34 45 19 15 58
ESO 3:
 45 18 21 91 72 81 29 47 84 65 12 15 19 34 58

Come puoi vedere i numeri negativi sono stati sostituiti dalle corrispettive sottosequenze

Ok solo ora ho capito cosa fa esattamente il tuo programma. Mi stavo fissando troppo perché pensavo che avessi in mente il mio stesso algoritmo, però in realtà sono leggermente diversi.

OK. Io non riesco a capire dove sbaglio perché l’algoritmo mi sembra corretto e l’implementazione anche…

Forse ho capito… Correggimi se sbaglio. Mettiamo di avere queste due ESO (che effettivamente sono uguali):

ESO1 (1 2 [3 4] [5 6])
ESO2 (1 2 [5 6] [3 4])
Il tuo algoritmo (a quanto ho capito) dovrebbe ordinarle in questo modo:
([5 6] [3 4] 1 2)
([3 4] [5 6] 1 2)
Però così ti risulteranno diverse. Questo perché i numeri negativi li assegni man mano che incontri altre parentesi, quindi l’ordine in cui le incontri fa sì che due sotto-ESO siano in ordine decrescente.

Un altro errore che sembra fare l’algoritmo è quello di togliere le parentesi indiscriminatamente, cioè mettiamo l’esempio:

ESO1 ([1 2])
ESO2 ((1 2))
Il tuo algoritmo le considera uguali, ma in realtà non lo sono (credo almeno).
Un altro errore che sembra fare l'algoritmo è quello di togliere le parentesi indiscriminatamente, cioè mettiamo l'esempio:
ESO1 ([1 2])
ESO2 ((1 2))
Il tuo algoritmo le considera uguali, ma in realtà non lo sono (credo almeno).

Lawliet

Il mio programma che fa 100/100 le considera uguali, quindi non so se è necessario che anche le parentesi siano uguali...
Forse ho capito.. Correggimi se sbaglio. Mettiamo di avere queste due ESO (che effettivamente sono uguali):
ESO1 (1 2 [3 4] [5 6])
ESO2 (1 2 [5 6] [3 4])
Il tuo algoritmo (a quanto ho capito) dovrebbe ordinarle in questo modo:
([5 6] [3 4] 1 2)
([3 4] [5 6] 1 2)
Però così ti risulteranno diverse. Questo perché i numeri negativi li assegni man mano che incontri altre parentesi, quindi l'ordine in cui le incontri fa sì che due sotto-ESO siano in ordine decrescente.

Lawliet

Questo è sicuramente un errore
Un altro errore che sembra fare l'algoritmo è quello di togliere le parentesi indiscriminatamente, cioè mettiamo l'esempio:
ESO1 ([1 2])
ESO2 ((1 2))
Il tuo algoritmo le considera uguali, ma in realtà non lo sono (credo almeno).

Lawliet

Questo non so se è possibile che accada...

Per questo ho scritto “credo”. L’ho detto perché il mio programma non le considera uguali, quindi magari poteva essere un altro errore.

Risolto grazie!

Mi intrometto con una soluzione alternativa, si può associare ad ogni ESO un “id” ( hash ) mi
tramite una funzione di hash che riordina in modo opportuno l’espressione e poi ne applica una serie di operazioni aritmetiche :wink:
Molto più efficiente, corta da scrivere e utilizza molta molta meno memoria!