# Bug in Sushi Variegato (Yutaka)

**URL:** <https://forum.olinfo.it/t/bug-in-sushi-variegato-yutaka/8142>\
**Category:** Aiuto\
**Created:** [29 Marzo 2023, 2:02pm UTC](https://forum.olinfo.it/t/bug-in-sushi-variegato-yutaka/8142 "2023-03-29T14:02:34Z")\
**Posts on this page:** 3\
**Page:** 1

<div class="post-metadata">

**Author:** ![dalpone](https://forum.olinfo.it/user_avatar/forum.olinfo.it/dalpone/32/2830_2.png) [@dalpone](https://forum.olinfo.it/u/dalpone)\
**Post date:** [29 Marzo 2023, 2:02pm UTC](https://forum.olinfo.it/t/bug-in-sushi-variegato-yutaka/8142/1 "2023-03-29T14:02:34Z")

</div>

Codice:

```auto
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define nl '\n'
#define ll long long
const int mod = 1e9 + 7;
const int mxn = 1e6 + 100;
int taglia(int N, int V[]) {
	ll dp[N+1];
	ll pref[N+1];
	memset(dp, 0, sizeof(dp));
	memset(pref, 0, sizeof(pref));
	dp[0] = 1;
	pref[0] = 1;
	vector<int> lastSeen(mxn, -1);
	int lastD = 0;
	for (int i = 1; i <= N; i++) {
		// Devo confrontare questo con il massimo tra lastD e l'ultima istanza trovata di se' stesso
		lastD = max(lastSeen[V[i-1]], lastD);
		dp[i] = pref[i-1] - (lastD ? pref[lastD-1] : 0);
		dp[i] %= mod;
		pref[i] = pref[i-1] + dp[i];
		pref[i] %= mod;
		lastSeen[V[i-1]] = i;
	}
	return dp[N];
}

```

Credo che l’idea sia corretta. La spiego per chiarezza:  
dp[i] = numero di modi di dividere l’array fino alla posizione i-1  
Posso porre divisioni all’array in tutte le posizioni precedenti, fino alla ultima posizione in cui un piatto sarebbe ripetuto.  
Uso prefix sum per velocizzare questa somma.  
Eppure questo codice prende 53/100, qualcuno puo’ consigliarmi cosa c’e’ di sbagliato?  
Grazie 🙂

---

<div class="post-metadata">

**Author:** ![qwfwq](https://forum.olinfo.it/user_avatar/forum.olinfo.it/qwfwq/32/2974_2.png) [@qwfwq](https://forum.olinfo.it/u/qwfwq)\
**Post date:** [29 Marzo 2023, 5:17pm UTC](https://forum.olinfo.it/t/bug-in-sushi-variegato-yutaka/8142/2 "2023-03-29T17:17:24Z")

</div>

Il problema è che in dp[i] la differenza può risultare negativa. Basta solo correggere quel punto.

---

<div class="post-metadata">

**Author:** ![dalpone](https://forum.olinfo.it/user_avatar/forum.olinfo.it/dalpone/32/2830_2.png) [@dalpone](https://forum.olinfo.it/u/dalpone)\
**Post date:** [29 Marzo 2023, 5:49pm UTC](https://forum.olinfo.it/t/bug-in-sushi-variegato-yutaka/8142/3 "2023-03-29T17:49:53Z")

</div>

Riusciresti a fornirmi un esempio? Non riesco a capire come sia possibile…  
Upd: ok ho inserito un controllo ed effetitvamente puo’ diventare negativo  
Ora devo capire come sia possible ahahahah  
Ahhh ho capito!  
Siccome prendo il modulo, potrebbe succedere una iterazione porta la pref sum sopra a mod, e quindi viene ridotta considerevolmente, e se dopo sottraggo tale ridotta pref sum con una precedente “non ridotta”, il risultato diventa negativo. Grazie mille!