Muraglia (ST) help

Aiuto
1

Salve a tutti, sto provando a risolvere muraglia da qualche giorno e sono riuscito (almeno penso) a creare correttamente il segment tree e a sviluppare la funzione update però non riesco a creare la funzione chiedi.
Ho seguito il consiglio di usare la funzione get_first su questo sito ma non ottengo i valori che cerco e in generale non so interpretarli perché non mi è molto chiaro cosa fa questa funzione.
Ecco il codice fin’ora:

#include<bits/stdc++.h>
using namespace std;
vector<int> nodes;
int size;
void build(int u, int sx, int dx, vector<int> data){

    if(dx - sx == 1){
        if(sx < data.size())
            nodes[u] = data[sx];
    }
    else{
        int m = (sx+dx)/2;
        build(2*u, sx, m, data);
        build(2*u+1, m, dx, data);
        nodes[u]= max(nodes[2*u], nodes[2*u+1]);
    }
}
void inizializza(int N, vector<int> data){
	size = 1;
	
    while(size < N)
        size *= 2;
    nodes.assign(2*size, -1); // totale nodi=2*N-1
    build(1, 0, size, data);
}
void cambia(int x, int h){
	int p = size + x; //size è il primo del vector
	nodes[p] = h;
	while(p>1){
		p/=2; //risalgo
		nodes[p] = max(nodes[2*p], nodes[2*p+1]);
	}
}
int succ(int pos, int sx, int dx, int a, int b, int x){ // a, b estremi
	if(sx > b or dx < a) return -1;
	if(a <= sx and dx <= b){
		if(nodes[pos] <= x)	return -1;
		while(sx != dx){
			int m = sx + (dx-sx)/2;
			if(nodes[2*pos] > x){ 
				pos = 2*pos;
				dx = m; 
			}
			else{
				pos = 2*pos+1;
				sx = m+1;
			}
		}
		return sx;
	}
	int m = sx + (dx-sx)/2;
    int rs = succ(2*pos, sx, m, a, b, x);
    if(rs != -1) return rs;
    return succ(2*pos+1, m+1, dx, a, b, x);
}
//pair<int, int> 
int chiedi(int x){
	int pos = succ(1, x+1, 2*size, x+1, 2*size, x);
	return pos;
}
int main(){
    int N = 14;
    vector<int> data = {7, 4, 78, 2, 6, 4, 1, 9, 10, 7, 100, 56, 8, 1};
    inizializza(N, data);
    for(int i=1; i<nodes.size(); i++){		//stampo il ST
        if(i==2 or i==4 or i==8 or i==16) cout<<"\n";
        cout<<nodes[i]<<"\t";
    }
    cambia(7, 3);	//test update
    cout<<"\n\n";
    cout<<chiedi(1)<<endl; //test chiedi
    return 0;
}
2

Ciao, la funzione:

int succ(int pos, int sx, int dx, int a, int b, int x) {}

restituisce la possizione p della torre nell’intervallo [a,b] che soddisfa la condizione data[p] > x, se non la trova return -1.
Quelli che non sono corretti sono i valori che passi in :

int chiedi(int x) {
int pos = succ(1, x+1, 2size, x+1, 2size, x);
return pos;
}

3

Ciao, ho provato ha inserire vari valori nella chiamata ma non ottengo mai l’output corretto.

int pos = succ(1, size+x+1, 2*size, size+x+1, 2*size, nodes[x + size]);

Di sicuro dovevo inserire la size perché sto lavorando nel ST e non nell’array, poi il mio ragionamento è che la funzione parte dalla radice perché pos raddoppia ogni volta, poi sx e dx sono gli intervalli dove cerco il valore (che presumo siano il successivo di x fino alla fine nelle foglie del ST) e a e b alla fine non cambiano mai in b di sicuro va la fine in a ho messo 1, size, size+x+1 ma l’output risulta sempre errato.
Di sicuro non mi trovo con qualcosa ma non riesco a capire cosa :sweat_smile:

4

Ciao, per come è stato definito il segment tree gli intervalli per determinare la posizione del successivo di data[ x ] sono rispettivamente [0,size-1] e [x,size-1], chiaramente se non trova alcuna posizione restituisce -1.

5

La funzione chiedi dovrebbe restituire due numeri, uno più piccolo di x e uno più grande

pair<int, int> chiedi(int x)
6

Ciao, ti ringrazio per l’aiuto perché ora sembra che ora la parte di destra è sistemata; sto provando a sistemare la parte a sinistra con qualche modifica alla get_first (cambiando solo gli estremi di ricerca mi da sempre il risultato più a sinistra invece di quello più vicino a x) e ho modificato m in modo che si sposti a sinistra cosi

    int m = dx - (dx-sx)/2;

(ovviamente ho anche cambiato il nome della funzione per la ricorsione) ma mi va in errore e il sanitizer mi dice heap-buffer-overflow.
Come sei riuscito a sistemare il bastione precedente?

#include<bits/stdc++.h>
using namespace std;
vector<int> nodes;
int size;
void build(int u, int sx, int dx, vector<int> data){

    if(dx - sx == 1){
        if(sx < data.size())
            nodes[u] = data[sx];
    }
    else{
        int m = (sx+dx)/2;
        build(2*u, sx, m, data);
        build(2*u+1, m, dx, data);
        nodes[u]= max(nodes[2*u], nodes[2*u+1]);
    }
}
void inizializza(int N, vector<int> data){
    ::size = 1;
    
    while(::size < N)
        ::size *= 2;
    nodes.assign(2*::size, -1); // totale nodi=2*N-1
    build(1, 0, ::size, data);
}
void cambia(int x, int h){
    int p = ::size + x; //size è il primo del vector
    nodes[p] = h;
    while(p>1){
        p/=2; //risalgo
        nodes[p] = max(nodes[2*p], nodes[2*p+1]);
    }
}
int succ(int pos, int sx, int dx, int a, int b, int x){ // a, b estremi
    if(sx > b or dx < a) return -1;
    if(a <= sx and dx <= b){
        if(nodes[pos] <= x) return -1;
        while(sx != dx){
            int m = sx + (dx-sx)/2;
            if(nodes[2*pos] > x){ 
                pos = 2*pos;
                dx = m; 
            }
            else{
                pos = 2*pos+1;
                sx = m+1;
            }
        }
        return sx;
    }
    int m = sx + (dx-sx)/2;
    int rs = succ(2*pos, sx, m, a, b, x);
    if(rs != -1) return rs;
    return succ(2*pos+1, m+1, dx, a, b, x);
}
int prec(int pos, int sx, int dx, int a, int b, int x){ // a, b estremi
    if(sx > b or dx < a) return -1;
    if(a <= sx and dx <= b){
        if(nodes[pos] <= x) return -1;
        while(sx != dx){
            int m = dx - (dx-sx)/2;
            if(nodes[2*pos] > x){ 
                pos = 2*pos;
                dx = m; 
            }
            else{
                pos = 2*pos+1;
                sx = m+1;
            }
        }
        return sx;
    }
    int m = dx - (dx-sx)/2;
    int rs = prec(2*pos, sx, m, a, b, x);
    if(rs != -1) return rs;
    return prec(2*pos+1, m+1, dx, a, b, x);
}

pair<int, int> chiedi(int x){
    int pos = succ(1, 0, ::size-1, x, ::size-1, nodes[x+::size]);
    int pos_ = prec(1, 0, ::size-1, 0, x, nodes[x+::size]);
    pair<int, int> a = make_pair(pos_, pos);
    return a;
}
7

Ciao, quello che devi cambiare nella funzione prec() rispetto alla succ() non è il modo di calcolare m, esso rimane invariato, si tratta semplicemente del valore medio tra [sx,dx]:

m = (sx+dx)/2

Quello che, invece, devi modificare nella funzione per trovare il precedente sono i nodi del segment tree, quelli di sinistra 2i al posto di quelli di destra 2+1, per il modo i cui sono distribuiti i nodi all’interno dell’albero.

8

Susami ma non sono familiare con i segment tree, devo modificare sx e dx così?

int prec(int pos, int sx, int dx, int a, int b, int x){ // a, b estremi
    if(sx > b or dx < a) return -1;
    if(a <= sx and dx <= b){
        if(nodes[pos] <= x) return -1;
        while(sx != dx){
            int m = (dx-sx)/2;
            if(nodes[2*pos] > x){ 
                pos = 2*pos;
                sx = m; 
            }
            else{
                pos = 2*pos+1;
                dx = m+1;
            }
        }
        return sx;
    }
    int m = (dx-sx)/2;
    int rs = prec(2*pos, sx, m, a, b, x);
    if(rs != -1) return rs;
    return prec(2*pos+1, m+1, dx, a, b, x);
}

cosi continua a darmi errore non so come muovermi, grazie per tutto il supporto

9

Attenzione:
m = (sx + dx)/2;

oppure anche:
m = sx + (dx - sx)/2;

Quello che non hai fatto, invece, è di invertire i nodi, questo si è importante.

10

Non mi è chiaro cosa significa invertire i nodi, devo rifare la funzione inizializza sul vettore iniziale invertito e usare la get_first sul nuovo segment tree? Non impiegherebbe troppo tempo?
Se vuoi puoi inviarmi qualche snippet di codice così cerco di capire meglio

11

No il segment tree è sempre lo stesso è solo la funzione prec() che deve essere implementata, non essendo forse abbastanza chiaro con “invertire i nodi da pari a dispari e viceversa”, devi in pratica sostituire, ad esempio:

if(nodes[2*pos+1] > x) { 
...
}
else {
...
 }

invece di:

if(nodes[2*pos] > x) { }

chiaramente tra parentesi devi mettere i valori giusti.
Lo stesso devi fare poi nelle altre righe della funzione.

12 
int prec(int pos, int sx, int dx, int a, int b, int x){
    if(sx > b or dx < a) return -1;
    if(a <= sx and dx <= b){
        if(nodes[pos] <= x) return -1;
        while(sx != dx){
            int m = sx + (dx-sx)/2;
            if(nodes[2*pos+1] > x){ 
                pos = 2*pos+1;
                sx = m+1; 
            }
            else{
                pos = 2*pos;
                dx = m;
            }
        }
        return sx;
    }
    int m = sx + (dx-sx)/2;
    int ls = prec(2*pos+1, m+1, dx, a, b, x);
    if(ls != -1) return ls;
    return prec(2*pos, sx, m, a, b, x);
}

Ho invertito la condizione come hai detto e ho sistemato le altre variabili ma continua ad andare in segmentation fault, penso di aver dato a sx e dx ogni valore possibile ma continua a non funzionare :sweat_smile:

13

Il vector data deve essere passato alla funzione per reference per questo motivo va in TLE.
Poi attenzione che le 2 funzioni prec() e succ() ti restituiscono -1 se non trovano gli estremi sx e dx al posto di 0 e N-1.
Fatti questi aggiustamenti prendi 100/100.

14

Ora rientro nel tempo e sono anche riuscito a risolvere il segmentation fault ma gli output sono tutti incorretti tranne il secondo caso di esempio, già ad esempio facendo Q 4 nel primo caso d’esempio mi viene calcolato 0 8 al posto di 2 7
Ecco il codice aggiornato

#include<bits/stdc++.h>
using namespace std;
vector<int> nodes;
int size;
int N;
void build(int u, int sx, int dx, vector<int> &data){

    if(dx - sx == 1){
        if(sx < data.size())
            nodes[u] = data[sx];
    }
    else{
        int m = (sx+dx)/2;
        build(2*u, sx, m, data);
        build(2*u+1, m, dx, data);
        nodes[u]= max(nodes[2*u], nodes[2*u+1]);
    }
}
void inizializza(int N, vector<int> data){
    ::size = 1;
    
    while(::size < N)
        ::size *= 2;
    nodes.assign(2*::size, -1); // totale nodi=2*N-1
    build(1, 0, ::size, data);
}
void cambia(int x, int h){
    int p = ::size + x; //size è il primo del vector
    nodes[p] = h;
    while(p>1){
        p/=2; //risalgo
        nodes[p] = max(nodes[2*p], nodes[2*p+1]);
    }
}
int succ(int pos, int sx, int dx, int a, int b, int x){ // a, b estremi
    if(sx > b or dx < a) return -1;
    if(a <= sx and dx <= b){
        if(nodes[pos] <= x) return -1;
        while(sx != dx){
            int m = sx + (dx-sx)/2;
            if(nodes[2*pos] > x){ 
                pos = 2*pos;
                dx = m; 
            }
            else{
                pos = 2*pos+1;
                sx = m+1;
            }
        }
        return sx;
    }
    int m = sx + (dx-sx)/2;
    int rs = succ(2*pos, sx, m, a, b, x);
    if(rs != -1) return rs;
    return succ(2*pos+1, m+1, dx, a, b, x);
}
int prec(int pos, int sx, int dx, int a, int b, int x){ // a, b estremi
    if(sx > b or dx < a) return -1;
    if(a <= sx and dx <= b){
        if(nodes[pos] <= x) return -1;
        while(sx != dx){
            int m = sx + (dx-sx)/2;
            if(nodes[2*pos+1] > x){ 
                pos = 2*pos+1;
                sx = m+1; 
            }
            else{
                pos = 2*pos;
                dx = m;
            }
        }
        return dx;
    }
    int m = sx + (dx-sx)/2;
    int ls = prec(2*pos+1, sx, m, a, b, x);
    if(ls != -1) return ls;
    return prec(2*pos, m+1, dx, a, b, x);
}

pair<int, int> chiedi(int x){
    int pos = succ(1, 0, ::size-1, x, ::size-1, nodes[x+::size]);
    if(pos==-1) pos=N-1;
    int pos_ = prec(1, 0, ::size-1, 0, x, nodes[x+::size]);
    if (pos_==-1) pos_=0;
    pair<int, int> a = make_pair(pos_, pos);
    return a;
}
15

Se sbagli un caso d’esempio, hai qualcosa di immediato su cui debuggare. Traccia l’esecuzione del tuo programma (usando un debugger, o anche solo mettendo cout nei punti importanti) e controlla che tutto sia come te lo aspetti. Quando trovi qualcosa che non va cerca di capire cosa causa il problema e mettilo a posto.
Saper debuggare è estremamente importante, poiché implementare soluzioni funzionanti è parte di ciò che viene richiesto alle OII.

16

La version corretta della funzione prec() era quella pubblicata prima di quest’ultima versione ed è con quella che fa 100/100. L’unico errore che ti rimane da risolvere è quello di stampare N-1 al posto di -1.

1 Mi Piace
17

100/100 Grazie :heart:

Per stampare N-1 nella funzione inizializza che usa N ho preso il valore di N e lo ho assegnato a una variabile globale M nella mia soluzione per poi richiamarla con ::M nella funzione chiedi()