Problema Classifica senza fili

Ciao a tutti,
mi sto preparando per le gare nazionali e mi sono scontrato con questo problema dell’anno scorso.
Per ora sono riuscito a totalizzare 71 punti dividendo il vettore classifica in vari sottoblocchi lunghi ognuno inizialmente radice di N (square root decomposition?). Così facendo solo due input superano il tempo massimo (uno nel 5 e uno nel 7 subtask).
Il problema penso sia ancora l’erase necessario per la funzione squalifica.
Esiste un modo per migliorare questo approccio o devo cambiare del tutto strategia?

Ciao,
per decidere se vale la pena provare a ottimizzare il codice devi vedere di quanto tempo sfori dal limite massimo.
Se il tuo codice supera di meno del 10% il limite massimo (es. fino a 1,100 sec nel caso peggiore con limite di tempo di 1,000 sec) secondo me si può ancora provare a fare qualcosa mentre se sfora di troppo tempo credo che servirà inventarsi qualcos’altro.
Spero di essere stato d’aiuto.

Ti ringrazio per la risposta.
Il caso peggiore (su un tempo massimo di 2 secondi) è 2.396 quindi un po’ sopra il 10%… dici che è il caso di cambiare?
Perché ho letto un topic simile sul forum risalente a un anno fa e si parlava di soluzioni con range tree e alberi binari bilanciati… Ho provato a cercarli su internet per informarmi ma non ci ho capito molto se non che in c++ corrispondono ai Set e Map, men che meno come applicarli al problema.

0,396 secondi non è poco, credo convenga cambiare approccio).
Provo a spiegarti cosa siano in breve:
-albero binario (di ricerca):
è una struttura dati molto semplice da implementare formata da vari nodi (ognuno dei quali con al più due nodi figli).
Ogni nodo contiene un valore (solitamente un numero, ma questo valore può essere anche una string o in generale un tipo qualsiasi per cui abbia senso in concetto di ordinamento) e questo valore non può essere cambiato se vogliamo evitare che strane cose avvengano e pertanto sono da considerarsi immutabili (come i valori-chiare nelle map della STL).
La ragione per cui serve che un valore chiave sia immutabile è la seguente:
quando si aggiunge un nuovo valore all’albero (che non sia il primo che altrimenti finirebbe nella radice) si prende la radice e
(n è il valore da aggiungere, radice->val è il valore chiave del nodo radice)

function aggiungi(n, radice)
. se n < radice->val
. | se radice ha un nodo figlio alla sua sinistra
. | | aggiungi(n, radice->sin)
. | altrimenti
. | | crea un nodo contenente n alla sinistra di radice
. altrimenti
. | se radice ha un nodo figlio alla sua destra
. | | aggiungi(n, radice->des)
. | altrimenti
. | | crea un nodo contenente n alla destra di radice
end function

(Nota che se si usa questo codice è meglio evitare di inserire due volte lo stesso valore n all’interno dell’albero.)

Se crei una struct nodo così
struct nodo{
nodo
int val;
nodo* des, sin;
}

risulta anche abbastanza facile implementare un albero binario così.
Poi puoi realizzare anche una funzione di ricerca all’interno dello stesso che, funzionando in modo simile a quella di inserimento, verifichi se un dato valore è presente o meno nell’albero.
Nota che in un albero implementato come quello sopra ogni nodo si trova alla destra di tutti i nodi che contengono al loro interno una chiave di valore minore di quella del nodo in questione.
L’albero che viene fuori usando questa funzione aggiungi non è però sempre un albero bilanciato (per capire cosa significa immagina di inserire in questo ordine nell’albero i valori 1, 2, 3, 4 e 5: noteresti che l’albero (con la radice contenente il numero 1) verrebbe sbilanciato verso destra mentre se i valori vengono inseriti così: 2, 1, 3, 2 e 4, senza il noti che viene creato un albero “alto” 2 se si prosegue verso sinistra e alto 3 se si prosegue verso destra e che quindi ha la foglie (i suoi nodi senza figli) tutte alla stessa altezza (più o meno).
Il fatto che un albero binario sia bilanciato fa sì che effettuale una ricerca al suo interno sia sempre in ln(n).
Esistono modi per tenere un albero sempre bilanciato ma onestamente non so come si faccia.

-RangeTree:
immagina un albero in cui tutti i valori sono contenuti nelle foglie e nei nodi è contenuta un’informazione sulle foglie discendenti di questo: es. quante sono, qual è la somma o il minimo/massimo di questi valori.
Credo che per Classifica senza fili il rangetree possa servire a sapere quanti concorrenti sono ancora in gioco prima del giocatore x.

Spero di esserti stato chiaro e utile e mi scuso per essere stato un po’ troppo prolisso. :sweat_smile:

P.S.: rangetree e alberi vari possono essere implementati anche senza puntatori usando degli array con miglioramenti nelle prestazioni non trascurabili in questi esercizi.

Alle nazionali potrebbero servirti gli alberi, quindi guardali bene, io per il range tree ho usato questo video (https://www.youtube.com/watch?v=ZBHKZF5w4YU&t=1363s), e per la Lazy Propagation questo (https://www.youtube.com/watch?v=xuoQdt5pHj0&t=1528s) che sono abbastanza chiari, l’unica pecca è che l’implementazione che trovi in descrizione è in java, puoi tradurla o implementarla tu, oppure crearti una classe apposita come suggerito da @lukecavabarrett qui (Segment Tree help)

Può risultarti utile anche il Fenwick Tree o Binary Index Tree che può trovare qui (https://www.youtube.com/watch?v=CWDQJGaN1gY), rimane sempre il “problema” del codice in java

Gli alberi in generale sono trattati anche qui (https://cses.fi/book.html)

Vi ringrazio entrambi,
nei prossimi giorni cercherò di darmi da fare e capirci dentro qualcosa ahahah

Sì può avere la comodità delle classi pur usando un segment tree allocato come vettore Heap.
In generale, ogni qualvolta ci sono concetti ripetititivi e un attimo intricati, quindi dove è facile commettere errori banali, personalmente preferisco gestire le cose con delle classi.

Una (piccola ma importante) nota.
Il tempo visualizzato non è il tempo che la vostra soluzione impiegherebbe lasciandola in esecuzione per un tempo indeterminato. Immaginatevi infatti di sottoporre un algoritmo a complessità esponenziale che richiederebbe anni per essere valutato fino in fondo. Quale tempo dovrebbe mostrarvi il correttore?

È evidente quindi che il tempo mostrato ha significato solo quando è inferiore al tempo limite prefissato per il problema. In caso contrario, CMS prova a fermare l’esecuzione non appena si accorge che il tempo limite è stato superato. Questo tipicamente accade dopo qualche frazione di secondo dal superamento del limite ed è il tempo che viene mostrato all’utente.

1 Mi Piace

io ho notato però che CMS fa abortire il programma (o quantomeno i MIEI programmi :joy:) solo quando si avvicina a tempo limite + 1 secondo quindi a meno che i miei non siano tutti casi eccezionali il risultato ottenuto da @rego dovrebbe essere attendibile.

Capisco, grazie mille per l’informazione :slightly_smiling_face:

Sono riuscito a risolverlo con un albero, grazie ancora a tutti :grin:

1 Mi Piace