Algoritmi - [OII] Numeri antipatici

Forum - Algoritmi - [OII] Numeri antipatici

lolgtfo (Normal User)
Newbie

Messaggi: 5
Iscritto: 16/05/2013

Postato alle 22:08
Giovedì, 16/05/2013

Ciao a tutti!
Ho cercato di risolvere questo problema proposto alle olimpiadi..
http://81.208.32.83:8080/oii/2009/olimpiadiItaliane/numeri ...

Il mio algoritmo funziona per l'input dato come esempio ma va in timeout nei casi del correttore ufficiale, quindi credo che per input grandi vada in crisi e non sia la soluzione adatta ad un problema di questo tipo.

Qualcuno ha qualche idea? (E magari consigli su come affrontare la selezione nazionale delle olimpiadi)

lillogoal (Member)
Rookie

Messaggi: 28
Iscritto: 26/04/2013

Postato alle 22:43
Giovedì, 16/05/2013

Devi scrivere uno pseudo codice? o in quale linguaggio?
Secondo me, continua a riguardare gli esercizi delle vecchie olimpiadi e prova a farli

Phi (Member)
Expert

Messaggi: 241
Iscritto: 30/12/2009

Postato alle 14:15
Venerdì, 17/05/2013

Si possono usare C, C++ e Pascal sicuramente, poi forse anche altri.

Se posti il codice che hai scritto tu possiamo capire meglio qual è il problema.

Comunque dato che N può essere 1'000'000 dovresti scrivere un algoritmo lineare.
Controlla che il tuo lo sia.
Dovresti cercare di "controllare" un numero solo un numero costante di volte.

Ultima modifica effettuata da Phi il 17/05/2013 alle 14:18

lolgtfo (Normal User)
Newbie

Messaggi: 5
Iscritto: 16/05/2013

Postato alle 18:27
Venerdì, 17/05/2013

Niente, semplicemente il mio algoritmo partiva dal primo elemento del vettore e sommava fin quando non raggiungeva un valore maggiore o uguale al numero antipatico. Nel primo caso non incrementavo il contatore dei casi trovati, nel secondo caso lo incrementavo e continuavo a ciclare gli elementi fin quando erano 0 e incrementando il contatore ogni volta che lo erano. Appena veniva trovato un numero diverso da 0, rifaceva la stessa cosa per il secondo elemento del vettore ecc...
E mi rendo conto che per N grandi è abbastanza lento.. il codice credo di averlo perso :rofl:

lolgtfo (Normal User)
Newbie

Messaggi: 5
Iscritto: 16/05/2013

Postato alle 19:09
Sabato, 18/05/2013

Codice sorgente - presumibilmente C++

#include <iostream>
#include <fstream>
using namespace std;
long int N, M;
 
int main() 
{
        ifstream in("input.txt");
        ofstream out("output.txt");
        in>>M>>N;
        long int v[N];
        long int somma=0;
        long int s=0;
        for(int i=0;i<N;i++)
        {
                in>>v[i];
        }
        int j=0;
        for(int i=0;i<N-1;i++)
        {
                somma=v[i];
                j=i+1;
                if(somma==M) s++;
                while(somma<=M && j<N)
                {
                        somma+=v[j];
                        j++;
                        if(somma==M)
                        {
                                s++;
                        }
                }
        }
        out<<s;
        in.close();
        out.close();
}

ora mi risolve tutti i casi nel modo corretto.. ma due mi superano il tempo massimo di 1000 ms.

Phi (Member)
Expert

Messaggi: 241
Iscritto: 30/12/2009

Postato alle 12:39
Domenica, 19/05/2013

Considera la complessità del tuo algoritmo ed il massimo valore di N.
I tuoi 2 cicli for e while richiedono circa N^2 operazione.
Dato che N massimo e 1'000'000 il computer richiederà molto più di 1 secondo per farle.

Devi cercare di scrivere(ed è possibile) un algoritmo che abbia complessità O(n).

lolgtfo (Normal User)
Newbie

Messaggi: 5
Iscritto: 16/05/2013

Postato alle 14:16
Domenica, 19/05/2013

Ecco sì.. c'ero arrivato. Ho chiesto proprio per questo :rofl:

Non mi viene in mente niente..

Phi (Member)
Expert

Messaggi: 241
Iscritto: 30/12/2009

Postato alle 16:05
Domenica, 19/05/2013

Intanto io considererei a parte il caso in cui il numero antipatico sia 0.
Il questo caso basta che per ogni gruppo di 0 consecutivi aggiungi alla soluzione finale in quanti modi puoi scegliere degli zeri consecutivi. Se per esempio ai 5 zeri consecutivi dei aggiungere 5*6/2=15 alla soluzione.

Se il numero antipatico non è zero io comincerei a leggere l'array che tu hai chiamato v[], tenendo 3 varabili inizio, fine e somma. somma conterrà la somma dei numeri fra v[inizio] e v[fine], continuo ad aumentare fine alzando somma finché questa non superà o eguaglia M. Se M viene eguagliato allora aumento S, altrimenti comincio ad aumentare inizio ed a diminuire somma finché questa non è minore o eguaglia M. E così via. Così vedi ogni elemento di v[] poche volte(2 o 3).
Attento però non che quando M viene eguagliato non devi aumentare S di 1, ma devi tenere conto di eventuali zeri che circondato il tratto che hai scoperto avere somma M. Quindi devi contare anche gli zeri che precedono(chiamati zp) e seguono(chiamati zs) ed aggiungere ad s (zp+1)(zs+1).

lolgtfo (Normal User)
Newbie

Messaggi: 5
Iscritto: 16/05/2013

Postato alle 9:42
Martedì, 21/05/2013

ok, grazie

Dopo provo ad implementarlo..