Numeri di Figonacci : Problema

Questo codice risolve solamente le prime 2 subtask , la 3 completamente sbagliata e nella 4, gli ultimi quattro test vanno fuori tempo fino ad arrivare intorno a 1.984s,cosa mi consigliate di implementare/corregere?

 #include  <iostream>
 #include <fstream>
 #include <string.h>
 #include <limits.h>
 #include  <math.h>

using namespace std;
ifstream in("input.txt");
ofstream out("output.txt");

int main(){

    int N,M;

	in>>N>>M;

	int f[N],max = 0;

    f[0] = -1;

    f[1] = 0;

    for(int i = 2; i<N+1; i++){		

			for(int j = i-2; j>=0; j--){
			
			    max = max + (f[i-1] - f[j]);

			}

			f[i] = max;

			max = 0;
	}

	out<<(f[N]%M + M)%M<<endl;
}

Non ho fatto ancora il problema, ma è da implementare con la dinamica molto probabilmente, magari con la memoization.

La tua soluzione è una quadratica, che con N=10^6 va fuori tempo limite. L’obiettivo qui sarebbe una soluzione lineare, che però ha bisogno di una formula di ricorrenza “decente”, ovvero una formula di ricorrenza che si basi su un numero fisso di termini precedenti e non su tutti come nella descrizione data dal problema.
Quello che ti serve è qualcosa sullo stile della ricorsione di fibonacci:

F(N) = F(N - 1) + F(N - 2)

In questo problema la formula è un po’ più complessa ma è possibile ricavarla con un minimo di attenzione.

Dario

p.s.: Qualcuno sa se si può arrivare a un tempo logaritmico come con fibonacci?

1 Mi Piace

Ok grazie per le risposte ora vedrò come implementarlo

Ciao dopo un pò di tempo sono tornato su questo problema e ho trovato questa formula che comunque mi fa rimanere su quei 30 pt.

        int f[N];
        f[0] = -1;
    	f[1] = 0;
    	f[2] = 1;
    	
        for(int i = 3; i<N+1; i++){
        	f[i] = (f[i-1] * (i-1))-(f[i-3] * (i-2));	    
    	}
      out<<(f[N]%M + M)%M<<endl;

La formula non mi torna, come ci sei arrivato?
Comunque quello che sicuramente non fai è applicare il modulo a ogni iterazione, cosa che ti fa sbagliare il risultato.

1 Mi Piace

Ah grazie, mi è bastato aggiungere questa riga per ottenere 100 pt.

for(int i = 3; i<N+1; i++){
        	f[i] = (f[i-1] * (i-1))-(f[i-3] * (i-2));	    
            f[i] = (f[i] % M + M) % M;
    	}

Per quanto riguarda la formula mi sono scritto i valori della sequenza, e da li osservandola,(e provando dei calcoli) sono arrivato a questa formula

A questo punto, se può servire a qualcuno, questa è la formula che ho usato io:

f[i] = f[i - 1] + (i - 1) * (f[i - 1] - f[i - 2])

1 Mi Piace

per il tempo logaritmico non saprei
ragionando qua
se
f(n)=f(n-1)+f(n-2)
f(n-1)=f(n-2)+f(n-3)
allora
f(n)=2\cdot f(n-2)+f(n-3)

se
f(n-2)=f(n-3)+f(n-4)
allora
f(n)=2\cdot f(n-3)+2\cdot f(n-4)+f(n-3)=3\cdot f(n-3)+2\cdot f(n-4)

oserei una congettura tale che
f(n)=f(i)\cdot f(n-i)+f(i-1)\cdot f(n-i-1)
non saprei, sicuramente il quesito è interessante

Vedo che stai lavorando con fibonacci, la soluzione in O(logN) funziona con l’esponenziazione rapida delle matrici.

Fib_0 = 1
Fib_1 = 1

Definiamo s_i = \begin{bmatrix} Fib_i\\\ Fib_{i - 1} \end{bmatrix} , s_1 = \begin{bmatrix} 1\\\ 1 \end{bmatrix}

Possiamo calcolare gli elementi successivi come s_i = s_{i-1}\cdot \begin{bmatrix} 1 & 1\\ 1 & 0 \end{bmatrix} = s_1 \cdot \begin{bmatrix} 1 & 1\\ 1 & 0 \end{bmatrix}^i

Quindi per ottenere Fib_i basta calcolare \begin{bmatrix} 1 & 1\\\ 1 & 0 \end{bmatrix}^i in O(\log{i}) e poi moltiplicare \begin{bmatrix} 1\\\ 1 \end{bmatrix} per il risultato.

Il problema è che questo tipo di definizione funziona solo per ricorrenze lineari, mentre tutte le ricorrenze per figonacci che ho trovato vogliono la moltiplicazione.

1 Mi Piace

Teoricamente hai ragione: se moltiplicare due matrici 2x2 ci costa O(1),
calcolare \begin{bmatrix} 1 & 1 \cr 1 & 0 \cr \end{bmatrix}^i si fa in O(\log i).

Questa premessa cade però vista la rapida crescita dei numeri di fibonacci: quatttro normali interi a 32bit non riusciranno a contenere i valori degli elementi della matrice senza overflow.
Raramente verrà chiesto di calcolare per intero Fib_i con i>30, quindi la soluzione lineare è accettabilissima.
Da qui la questione: è possibile calcolare Fib_i\mod{C} per un qualche C ragionevole -i.e. fitta in un intero 32 bit- in O(\log i), o comunque in complessità minore di O(i)?

Yup.
Basta calcolare le matrici modulo C.

#include <cstdio>

constexpr int MOD = 1000000007;

int fib_linear(long long N)
{
	int f0 = 1, f1 = 1;
	for(long long i = 2; i < N; i++)
	{
		int tmp = f1;
		f1 = (f0 + f1) % MOD;
		f0 = tmp;
	}
	return f1;
}

void mat_mul(int mat[2][2], const int mul[2][2])
{
	int a = (mat[0][0] * 1LL * mul[0][0] + mat[0][1] * 1LL * mul[1][0]) % MOD;
	int b = (mat[0][0] * 1LL * mul[0][1] + mat[0][1] * 1LL * mul[1][1]) % MOD;
	int c = (mat[1][0] * 1LL * mul[0][0] + mat[1][1] * 1LL * mul[1][0]) % MOD;
	int d = (mat[1][0] * 1LL * mul[0][1] + mat[1][1] * 1LL * mul[1][1]) % MOD;
	mat[0][0] = a;
	mat[0][1] = b;
	mat[1][0] = c;
	mat[1][1] = d;
}

void fastexp(int mat[2][2], long long N)
{
	if(N <= 1) return;
	int mul[2][2] = {{1, 1}, {1, 0}};
	fastexp(mat, N / 2);
	mat_mul(mat, mat);
	if(N % 2) mat_mul(mat, mul);
}

int fib_logarithmic(long long N)
{
	int mat[2][2] = {{1, 1}, {1, 0}};
	fastexp(mat, N - 1);
	return mat[0][0];
}

int main()
{
	long long N;
	scanf("%lld", &N);
	printf("O(N) dp solution:         %d\n", fib_linear(N));
	printf("O(logN) fastexp solution: %d\n", fib_logarithmic(N));
}

Ho provato la velocità di questo codice, per N = 2\cdot10^9 il calcolo lineare prende ~13s, quello logaritmico ~0s. Ho anche provato N meno ragionevoli (N = LLONG\_MAX) e comunque non sono riuscito a ottenere tempi superiori a ~0s.

In questo codice ho usato una definizione leggermente diversa di Fib_i per evitare alla fine la moltiplicazione per \begin{bmatrix} 1\\ 1 \end{bmatrix}:

\begin{bmatrix} 1 & 1\\ 1 & 0 \end{bmatrix}^i = \begin{bmatrix} Fib_{i + 1} & Fib_i\\ Fib_i & Fib_{i - 1} \end{bmatrix}

1 Mi Piace

Ho trovato un altro algoritmo in O(\log{N}\log{\log{N}}) per Fibonacci, rigorosamente senza nessun goto:

Fib_1 = 0
Fib_2 = 1

Fib_{2n} = Fib_n^2 + Fib_{n + 1}^2
Fib_{2n + 1} = Fib_{n + 1} \cdot (Fib_{n + 1} + 2Fib_n)

http://www.cs.utexas.edu/users/EWD/ewd06xx/EWD654.PDF

Visto che parte da 0 e non da uno, N \le LLONG\_MAX - 1

3 Mi Piace

è super necroposting, ma mi sono accorto adesso che se

mi verrebbe da dire allora questa congettura è vera