Olimpiadi della Matematica Torino - OliMaTO - Forum

Giovanni98 ha scritto:Ma guarda che i limiti di tempo sono altissimi, tipo 5 minuti per il secondo

Non so quali siano le tue fonti, ma 5 minuti mi sembra veramente TANTO. I limiti per $N$ non li so, ma a rigor di logica dovrebbero dare punteggio pieno solo alle soluzioni $O(N)$, mentre se il tempo limite è 5 minuti ci sta dentro persino una $O(\text{Ackermann(N)})$.

EDIT: a quanto pare invece il tempo limite è proprio nell'ordine dei minuti...

Allora Livex, studiandolo un pò l'algoritmo risolutivo era

Se il segno $i$-esimo è '+' stampo il massimo (fra i numeri rimasti), se invece è '-' stampo il minimo. Il codice è il seguente...
Ovviamente l'input va fatto da file in gara ma io mi scoccio di farlo e uso il cin ahahahahahah

Siccome non ho niente da fare farò qualche osservazione a caso sul codice.

1. Non funziona. La condizione del for è i < vett.size(), ma i aumenta di 1 ad ogni ciclo, e al contempo vett.size() diminuisce di 1. Quindi ti fermerai a $N/2$ e non a $N$ come vorresti.
2. Il sort all'inizio è totalmente inutile, il vettore è già ordinato di suo.
3. L'algoritmo è in realtà quadratico. Infatti la cancellazione di un elemento diverso dall'ultimo in un vector $V$ è $O(V.size())$.
4. Di conseguenza il vector non va bene. Potresti usare al suo posto una deque, che ha eliminazione all'inizio e alla fine in $O(1)$ ammortizzato, ma perchè non usare semplicemente due variabili massimo e minimo che contengono, rispettivamente, il massimo e il minimo numero ancora disponibili?

Considera che l'algoritmo che ho provato ad implementare:

-segnava in un vettore i cambi di segno (quando si passa da "<" a ">" e viceversa).
-suddivideva la stringa in [tex]k[/tex] blocchi in cui c'erano o solo ">" o solo "<"
-per ciascuno di questi blocchi c'era una while che caricava un vettore in cui calcolavo di quanti numeri fosse minore ogni posizione.
-alla fine convertivo il vettore in una stringa da stampare (per esempio 0>1>3<0>1 diventava 5>3>1<4>2).

...bug ovunque.

Sul sort hai ragione (l'ho metto di consueto, non ci ho pensato), sulla condizione non mi trovo, non accade quello che dici scusami....riguardo alle cose del vector sono cose che non conosco e riguardo le variabili inizialmente avevo trovato problemi che mi scocciavo di risolvere.

Sorry, avevo letto vett.size() invece che segni.size(). Per quanto riguarda le variabili, di che problemi parli?

Non ricordo (l'ho fatto in 2 minuti senza controllare, giusto per dare l'idea a Livex, peró problemi sull'output).

Nella mia scuola hanno fatto (si, hanno, stupida regola per la quale non si può partecipare in quinta.) tutti l'1, il 2 chi completo e chi in parte, il 3 nessuno. O almeno, così dicono.

Ho avuto l'impressione che ci fosse un eccessivo dislivello di difficoltà fra il secondo e il terzo problema... così facendo temo si troveranno un sacco di gente con lo stesso punteggio (30 o giù di lì).

Ma quindi il 3 qui non l'ha risolto proprio nessuno?

Delfad0r ha scritto:Ho avuto l'impressione che ci fosse un eccessivo dislivello di difficoltà fra il secondo e il terzo problema... così facendo temo si troveranno un sacco di gente con lo stesso punteggio (30 o giù di lì).

Ma quindi il 3 qui non l'ha risolto proprio nessuno?

Io non ho proprio partecipato, ma non credo che riuscirei a farlo... Comunque penso che sarà a 34 l'ammasso di gente, o a 36, comunque giù di lì...