Historical revisionism (bitcoin2)

Aiuto
1

Salve a tutti, sto provando a fare questo esercizio ma ottengo 0/100 con solo i casi esempio corretti, ho generato qualche caso d’input randomicamente e il mio codice restituisce un risultato corretto siccome anche ad un mio amico che ha fatto 65/100(TLE) restituisce lo stesso risultato.
non riesco a capire dove possa essere l’errore.

#include <bits/stdc++.h>

using namespace std;

int n, v[1000], r, memo[305][305][305];

int f(int prec, int att, int pos){
	if(pos==n+2){
        return 0;
    }
	if(v[prec]>v[att]){
		if(v[pos]<v[prec] && v[pos]>v[att]){
			return memo[prec][att][pos]=max(f(att, pos, pos+1)+1, f(prec, att, pos+1));
		}else{
	        return memo[prec][att][pos]=f(prec, att, pos+1);
		}
	}else{
		if(v[pos]>v[prec] && v[pos]<v[att]){
			return memo[prec][att][pos]=max(f(att, pos, pos+1)+1, f(prec, att, pos+1));
		}else{
			return memo[prec][att][pos]=f(prec, att, pos+1);
		}
	}
	return memo[prec][att][pos]=f(prec, att, pos+1);
}

int main(){
	cin >> n;
	v[0]=2000000;
	v[1]=0;
	for(int x=2; x<n+2; x++) cin >> v[x];
	cout << n-max(f(0, 1, 2), f(1, 0, 2));
}
1 Mi Piace
2

Pur essendo \mathcal{O}(N^3) una ricorsione del genere risulta lenta.
Attualmente hai \mathcal{O}(N^3) stati e il tempo per calcolare ogni stato è \mathcal{O}(1), prova a riscriverla in modo da avere \mathcal{O}(N^2) stati e \mathcal{O}(N) per calcolare ogni stato: asintoticamente uguale ma il risparmio di tempo nella pratica è considerevole.

Un’altra cosa: non so se i testcase sono stati già corretti, ma a quanto pare il limite per V è 10^9, quindi occhio quando setti quel v[0] :smile:

3

grazie per l’aiuto, per quanto riguarda V il testo dice: 1 ≤ Vi ≤ 1 000 000 for each i = 0 . . . N − 1
quindi dovrebbe andare bene, ho capito come riscrivere il mio codice in modo da avere O(N^2) stati e come tempo O(N) per stato, non riesco a capire perché risultano giusti solo i casi d’esempio

4

quanto pare il testo è sbagliato, ora faccio 20/100

1 Mi Piace
5

Un’altra cosa: non so se i testcase sono stati già corretti, ma a quanto pare il limite per V è 10^9
, quindi occhio quando setti quel v[0] :smile:

Direi di no: senza aver letto questo topic avevo messo il massimo valore a 2 milioni per stare largo e non facevo un punto, dopo aver letto quanto sopra ho messo 2 miliardi e ora ho solo errori di TLE perchè devo ancora fare la memoizzazione