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);
}
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…
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...
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.
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.
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.
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 Molto più efficiente, corta da scrivere e utilizza molta molta meno memoria!
