Olimpiadi di informatica - Selezione territoriale 2015

Altre competizioni di carattere scientifico e non: Olimpiadi di Fisica, Olimpiadi di Chimica, Olimpiadi di Biologia, Olimpiadi di Filosofia, ecc...

Re: Olimpiadi di informatica - Selezione territoriale 2015

Messaggioda Delfad0r » 15/04/2015, 19:33

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...
Ultima modifica di Delfad0r il 15/04/2015, 22:04, modificato 1 volta in totale.
Delfad0r
 
Messaggi: 191
Iscritto il: 09/02/2015, 22:19

Re: Olimpiadi di informatica - Selezione territoriale 2015

Messaggioda Giovanni98 » 15/04/2015, 19:42

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
Ultima modifica di Giovanni98 il 15/04/2015, 20:08, modificato 1 volta in totale.
Avatar utente
Giovanni98
 
Messaggi: 1255
Iscritto il: 27/11/2014, 14:30

Re: Olimpiadi di informatica - Selezione territoriale 2015

Messaggioda Delfad0r » 15/04/2015, 19:56

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?
Delfad0r
 
Messaggi: 191
Iscritto il: 09/02/2015, 22:19

Re: Olimpiadi di informatica - Selezione territoriale 2015

Messaggioda Livex » 15/04/2015, 20:01

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.
Livex
 
Messaggi: 994
Iscritto il: 15/03/2013, 15:33

Re: Olimpiadi di informatica - Selezione territoriale 2015

Messaggioda Giovanni98 » 15/04/2015, 20:06

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.
Avatar utente
Giovanni98
 
Messaggi: 1255
Iscritto il: 27/11/2014, 14:30

Re: Olimpiadi di informatica - Selezione territoriale 2015

Messaggioda Delfad0r » 15/04/2015, 20:07

Sorry, avevo letto vett.size() invece che segni.size(). Per quanto riguarda le variabili, di che problemi parli?
Delfad0r
 
Messaggi: 191
Iscritto il: 09/02/2015, 22:19

Re: Olimpiadi di informatica - Selezione territoriale 2015

Messaggioda Giovanni98 » 15/04/2015, 20:09

Non ricordo (l'ho fatto in 2 minuti senza controllare, giusto per dare l'idea a Livex, peró problemi sull'output).
Avatar utente
Giovanni98
 
Messaggi: 1255
Iscritto il: 27/11/2014, 14:30

Re: Olimpiadi di informatica - Selezione territoriale 2015

Messaggioda mr96 » 16/04/2015, 14:30

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.
mr96
 
Messaggi: 1393
Iscritto il: 11/02/2014, 20:37

Re: Olimpiadi di informatica - Selezione territoriale 2015

Messaggioda Delfad0r » 16/04/2015, 15:46

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
 
Messaggi: 191
Iscritto il: 09/02/2015, 22:19

Re: Olimpiadi di informatica - Selezione territoriale 2015

Messaggioda mr96 » 16/04/2015, 15:50

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ì...
mr96
 
Messaggi: 1393
Iscritto il: 11/02/2014, 20:37

PrecedenteProssimo

Torna a Altre Gare

Chi c’è in linea

Visitano il forum: Nessuno e 0 ospiti