Sushi variegato (yutaka)

Aiuto
1

Ho scritto questo codice per risolvere Sushi variegato, ho fatto qualche test ma una volta sottomesso risolveva solo pochi casi è ho ottenuto 0/100, qualche suggerimento per risolvere questo problema? Avevo letto di usare la programmazione dinamica ma non saprei come applicarla.

Grazie in anticipo.

#include <iostream>
#include <stdio.h>
#include <set>
#include <math.h>

using namespace std;


int taglia(int N, int V[])
{
    int ris = 1;

    auto TipiPresenti = set<int>(); // contiene i pezzi di sushi presenti nel tagliere(uno per tipo)

    int ultimo = 0;
    TipiPresenti.insert(V[0]);

    int z = 0; //pezzi diversi dall'adiacente
    int k = 0; // pezzi ripresenti 

    for (int i = 1; i < N; i++)
    {
        int tipo = V[i];

        if (tipo != ultimo)
        {
            if (TipiPresenti.find(tipo) != TipiPresenti.end())
            {
                ris += pow(2, z) - pow(2, k);
                k++;
            }
            else
            {
                ris += pow(2, z);
                TipiPresenti.insert(tipo);
            }
            z++;
        }
        ultimo = tipo;
    }
    return ris % 1000000007;
}
2

Senza ricordarmi il problema ma guardando solo il tuo codice posso dirti:
stai facendo il modulo solo alla fine, se un problema ti chiede un risultato sotto modulo vuol dire che non ci sta negli int a 64 bit, neanche negli step intermedi, quindi devi tenere sempre tutto sotto modulo in modo che non vada in overflow.
(nota che (a*b)%m = ((a%m)*(b%m))%m e stessa cosa col +)
Inoltre usi la funzione pow di cmath, che sebbene andando in O(1), serve per elevare floating point, non interi, per elevare interi dovresti scriverti fastexp (anche pecrhe non ho guardato bene ma quei pow che fai dubito ci stiano anche nei long double)

1 Mi Piace
3

Grazie, ma purtroppo non è solo quello il problema perchè la seconda subtask comprende casi che raggiungo un risultato massimo di 16 384 quindi non va in overflow in quei casi.

4

La tua soluzione è sbagliata, per capire perché basta guardare una cosa del tipo 01010101.
Ti do degli hint per una soluzione corretta:

Sia dp[i] la soluzione al problema per l’intervallo [0,i]

Sapendo i valori di dp[j] per tutti i j in [0,i-1] posso trovare dp[i]?

Iteriamo sulla posizione dell’ultimo taglio, allora dp[i] è la somma di dp[j] su tutti i j tali che posso fare l’ultimo taglio subito dopo j senza avere due cosi uguali nell’ultimo intervallo. Questi j come si dispongono?

Non è difficile notare che sono un suffisso di [0,i-1], quindi possiamo averne la somma velocemente, come?

Prefix sums

1 Mi Piace
5

Non ho capito come assegnare i valori di dp[0] e dp[1] in un semplice caso 1 2 3, il risultato è 4, quindi se dp[2] deve essere uguale a 4 come assegno i valori a dp[0] e dp[1]?

6

Assumo i pezzi di sushi 1-indexed così il caso 0 è quando non ci sono pezzi, quindi il risultato è 1.
Siccome non ci sono pezzi uguali dp[i] è la somma dei precedenti,
dunque dp[1] =dp[0]=1 e dp[2] = dp[0]+dp[1] =2, dp[3]=1+1+2=4.

1 Mi Piace
7

Ho applicato questo metodo però per controllare che nel ultimo intervallo non ci siano tipi di sushi uguali controllo e inserisco uno alla volta i pezzi di sushi fin quando non ne trovo uno uguale, tutto questo usando il set.find(), c’è un modo migliore? Perchè mi va fuori tempo.

int taglia(int N, int V[])
{
    long long int ris = 1;

    vector <int> dp(N+1);

    dp[0] = 1;

    for (int i = 0; i < N; i++)
    {
        auto tagliere = set<int>();
        tagliere.insert(V[i]);
        dp[i+1] = dp[i];
        for (int k = i-1; k > -1; k--)
        {
            if (tagliere.find(V[k]) == tagliere.end())
            {
                dp[i+1] = (dp[i + 1] + dp[k]) % 1000000007;
                tagliere.insert(V[k]);
            }
            else
            {
                k = -1;
            }
        }
    }
    return dp[N] % 1000000007;
}
8

Al momento hai una complessità di O(n²logn), che prende TLE molto spesso, per evitare puoi osservare che l’ultimo posto dove puoi tagliare aumenta quando aumenta i e l’unica cosa che può cambiarlo è l’elemento i.
Per quello che stai facendo poi il set non serve, basta un vector di bool.

1 Mi Piace
9

Ho prodotto una soluzione in 0(n^2) ma ancora è troppo lenta, come altro potrei migliorarla?

int taglia(int N, int V[])
{
    vector <int> dp(N + 1);

    dp[0] = 1;
    int ultimo = -1;

    for (int i = 0; i < N; i++)
    {
        dp[i + 1] = dp[i];
        for (int k = i - 1; k > ultimo; k--)
        {
            if (V[k] != V[i])
            {
                dp[i + 1] = (dp[i + 1] + dp[k]) % 1000000007;
            }
            else
            {
                ultimo = k;
            }
        }
    }
    return dp[N];
}
10

Riguarda i miei ultimi messaggi, ci sono le due osservazioni chiave per passare a O(n)

1 Mi Piace
11

Applicando il prefix sums come mi avevi suggerito e usando un vettore per salvarmi le posizioni dei pezzi di sushi sono riuscito a risolverlo.
Grazie mille per la pazienza.

1 Mi Piace