Algoritmi - [OII] Numeri antipatici

Ciao a tutti!
Ho cercato di risolvere questo problema proposto alle olimpiadi..
81.208.32.83/oii/2009/olimpiadiItaliane/…

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)

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

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.

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

#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.

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).

Ecco sì.. c'ero arrivato. Ho chiesto proprio per questo Non mi viene in mente niente..

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).