Pagina 8 di 9

Re: Olimpiadi di informatica - Selezione territoriale 2015

MessaggioInviato: 15/04/2015, 19:33
da Delfad0r
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...

Re: Olimpiadi di informatica - Selezione territoriale 2015

MessaggioInviato: 15/04/2015, 19:42
da Giovanni98
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...

Testo nascosto:
Codice: Seleziona tutto
#include <fstream>
#include <algorithm>
#include <iostream>
#include <math.h>
#include <vector>
#include <cstdlib>
using namespace std;

typedef long int li ;

int main()
{

    li numero ;
    cin >> numero ;
   
    string segni ;
    cin >> segni ;
   
    vector<li> vett ;
    for (li i = 0; i < numero ; i++)
        vett.push_back(i+1);
   
    for (li i = 0; i < segni.size() ; i++)
    {    if (segni[i]=='<')
         {  cout << vett[0] << " "; vett.erase(vett.begin()); }
         else
         { cout << vett[vett.size()-1] << " "; vett.pop_back();}
    }
    cout << vett[0] << endl ;
   
    return 0;
   
}

Ovviamente l'input va fatto da file in gara ma io mi scoccio di farlo e uso il cin ahahahahahah

Re: Olimpiadi di informatica - Selezione territoriale 2015

MessaggioInviato: 15/04/2015, 19:56
da Delfad0r
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?

Re: Olimpiadi di informatica - Selezione territoriale 2015

MessaggioInviato: 15/04/2015, 20:01
da Livex
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.

Re: Olimpiadi di informatica - Selezione territoriale 2015

MessaggioInviato: 15/04/2015, 20:06
da Giovanni98
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.

Re: Olimpiadi di informatica - Selezione territoriale 2015

MessaggioInviato: 15/04/2015, 20:07
da Delfad0r
Sorry, avevo letto vett.size() invece che segni.size(). Per quanto riguarda le variabili, di che problemi parli?

Re: Olimpiadi di informatica - Selezione territoriale 2015

MessaggioInviato: 15/04/2015, 20:09
da Giovanni98
Non ricordo (l'ho fatto in 2 minuti senza controllare, giusto per dare l'idea a Livex, peró problemi sull'output).

Re: Olimpiadi di informatica - Selezione territoriale 2015

MessaggioInviato: 16/04/2015, 14:30
da mr96
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.

Re: Olimpiadi di informatica - Selezione territoriale 2015

MessaggioInviato: 16/04/2015, 15:46
da Delfad0r
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?

Re: Olimpiadi di informatica - Selezione territoriale 2015

MessaggioInviato: 16/04/2015, 15:50
da mr96
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ì...