Dieta di poldo (ricorsione)

Ciao a tutti. Ho bisogno di aiuto con il problema “la dieta di poldo”. Ho provato a risolverlo con una funzione ricorsiva ma non capisco perchè non funziona. Spero che qualcuno sappia dirmi dove sbaglio, grazie.

#include <iostream>

#include <fstream>

#include <vector>

using namespace std;

vector<int> v;

int n;

int contatore = 1;

int max(int a, int b)

{

    if (a > b)

    {

        return a;

    }else{

        return b;

    }

}

int function (int k)

{

   

    for (int i = k+1; i < n; i++)

    {

        if (v[i] < v[k])

        {

            contatore = max(contatore, 1 + function(i));

        }

       

    }

   

    return contatore;

   

}

int main()

{

    freopen("input.txt", "r", stdin);

    freopen("output.txt", "w", stdout);

    int risultato = 1;

    int appoggio = 0;

    cin >> n;

    //riempimento del vettore in input

    for (int i = 0; i < n; i++)

    {

        cin >> appoggio;

        v.push_back(appoggio);

        appoggio = 0;

    }

    //richiamo la funzione

    for (int j = 0; j < n; j++)

    {

        risultato = max(risultato, function(j));

        contatore = 1;

    }

   

    //stamp il rislutato

    cout << risultato;

    return 0;

}

Ciao @flp_o3,
Non sono la persona più qualificata del mondo nel spigare programmazione dinamica, di conseguenza se cometto qualche imprecisione spero che qualcuno più abile in questo campo possa coreggermi!

Per il resto questo messaggio sarà diviso in tre parti:

  • Nella prima cercherò di spiegarti come mai il tuo codice non funziona e ti farò vedere il codice funzionanente che riprende la tua idea di risoluzione.
  • Nella seconda ti mostrerò la soluzione a mio avviso più semplice per risolvere questo problema nel modo corretto senza uscire dai limiti di tempo.
  • Nella terza invece ci saranno dei piccoli trucchetti e corezzioni di alcuni errori presenti nel tuo codice che spero possano esserti utili in futuro

Prima parte:

L’ide di base è che esiste una fuzione f(k) tale che, quando calcolata, resituisce il valore della sequenza più lunga che si ferma nella posizione k dell’array. Di conseguenza, per trovare la soluzione al problema, è sufficiente iterare su tutti gli elementi dell’array per trovare la sequenza più lunga in generale. Cioe:

soluzione = \max_{\substack{k = 0 \dots N - 1}} \left(f(k)\right)

L’idea alla base è giusta, il problema è che la tua implementazione è errata! Il main in generale è abbastanza corretto, ma la funzione function che definisci a riga 33 è sbagliata. Infatti con il for a riga 39 stai richiamando la funzione ricorsivamente, ma su dei valori che dovrebbe calcolare dopo. Infatti la funzione non può calcolare le sequenze maggiori che partono da numeri più avanti di k se non ha un modo di recuperare quelle che partono da numeri minori. Inoltre manca un caso base per fare in modo che la ricorsione funzioni.

Vediamo come si risolve questo problema ricorsivamente seguengo l’idea indicata sopra:

La nostra funzione f(k) ci restituisce il valore della sequenza più lunga che termina alla posizione k dell’array. Il caso base in questo caso è f(0) = 1 in quanto se ho un solo elemento l’unica sequenza che posso formare è lunga 1. Per risolvere il problema allora definisco ricorsivamente la funzione in modo tale da poterla costruire da valori “più piccoli” di k: f(k) = \max\left(1, \max_{\substack{i = 0 \dots k-1 \\ v[i] < v[k]}} \left(f(i)\right) + 1\right)

In pratica cosa significa la formulona che ho scritto sopra? Che se voglio sapere qual’è la sequenza più lunga che termina in k io devo controllare tutte le sequenze che finisco in posizioni minori di k (i = 0 \dots k-1) che posso prendere (v[i] < v[k]), e ovviamente prendere la maggiore, sommandoci
1 essendo l’elemento k compreso nella sequenza che voglio calcolare.

Un esempio di codice che implementa questa soluzione:

Soluzione 1
#include <bits/stdc++.h>
using namespace std;

vector<int> v;

int f(int k) {
    if(k == 0)
        return 1;

    int sol = 1;
    
    for(int i = k - 1; i >= 0; i--) {
        if(v[i] > v[k])
            sol = max(sol, f(i) + 1);
    }

    return sol;
}

int main() {
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);

    //lettura inputs

    int n;
    cin >> n;

    int temp;

    for(int i = 0; i < n; i++) {
        cin >> temp;
        v.push_back(temp);
    }


    //calcolo della soluzione

    int sol = 1;

    for(int i = 0; i < n; i++)
        sol = max(sol, f(i));

    cout << sol;

    return 0;
}

Se provi a sottomettere questa soluzione però noterai che il punteggio sarà solo di 35/100, in quanto la ricorsione è troppo lenta. La complessità risulta infatti \mathcal O(2^N) (grazie a @MyK_00L). Vediamo come ottimizzarla!

Seconda parte:
Qui entra in gioco la programmazione dinamica! Infatti l’idea della DP (che è la sigla per dynamic programming) sta nel memorizzare i risultati calcolati in modo da non calcolarli vuovamente. Se ci si fa caso infatti, per ogni valore di k, quando si calcola f(k) si ricalcolano da capo tutti i valori di f(h) dove h < k. Basterebbe quindi memorizzare in un vettore i valori di f(k) già calcolati in modo da non rifarlo tutte le volte. Una soluzione potrebbe essere la seguente:

Soluzione 2
#include <bits/stdc++.h>
using namespace std;

vector<int> v, valori;
vector<bool> calculated;

int f(int k) {
    if(k == 0)
        return 1;

    if(calculated[k])
        return valori[k];
    
    calculated[k] = true;

    for(int i = k - 1; i >= 0; i--) {
        if(v[i] > v[k])
            valori[k] = max(valori[k], f(i) + 1);
    }

    return valori[k];
}

int main() {
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);

    //lettura inputs

    int n;
    cin >> n;

    int temp;

    for(int i = 0; i < n; i++) {
        cin >> temp;
        v.push_back(temp);
        valori.push_back(1);
        calculated.push_back(false);
    }


    //calcolo della soluzione

    int res = 1;

    for(int i = 0; i < n; i++)
        res = max(res, f(i));

    cout << res;

    return 0;
}

L’array valori serve per memorizzare i valori di f(k) in modo da non ricalcolarli tutte le volte, e lo si inizializza a 1 in quanto ogni sequenza è formata da almeno un elemento. Inoltre l’array calculated è un vettore di booleane (cioè ogni cella dell’array può assumere solo due valori, vero o falso) che tiene traccia dei valori già calcolati. Dentro la funzione f bisogna solo controllare, prima di inziare a fare tutti i calcoli, che il valore cercato non sia già stato calcolato in precedeza (if(calculated[k])), e in caso positivo si returni semplicmente il valore (return valori[k]).

Con questi accorgimenti si arriva ad un 100/100 e ad una complessità di \mathcal O(N^2), quindi il problema potrebbe essere finito qui…e invece no!

Infatti molti problemi di DP sono facili da pensare ricorsivamente, ma più veloci e più comodi da implementare iterativamente. Ti lascio di seguito la soluzione senza l’utilizzo della ricorsione, se hai qualche dubbio scrivi pure che ti spiego come funziona, perché ti sarà sicuramente utile per problemi futuri!

Soluzione 3
#include <bits/stdc++.h>
using namespace std;

int main() {
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);

    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int N;
    cin >> N;

    vector<int> v(N);

    for(int i = 0; i < N; i++) cin >> v[i];

    vector<int> sol(N, 1);

    for(int j = 1; j < N; j++) {
        for(int i = 0; i < j; i++) {
            if(v[j] < v[i])
                sol[j] = max(sol[j], sol[i] + 1);
        }
    }

    cout << *max_element(sol.begin(), sol.end());

    return 0;
}

Esistono soluzioni ancora più effcienti che hanno complessità \mathcal O(NlogN). Ma sono assolutamente esagerate per questo problema.

Terza parte:
Siamo finalmente giunti alla parte conclusiva di questo lunghissimo messaggio dove ti lascio alcuni suggerimenti e trucchi che ti potrebbero essere utili in generale per scrivere codice più veloce ed efficiente:

  1. Al posto di includere tante librerie diverse scrivi semplicemente #include <bits/stdc++.h> e hai tutto quello che ti serve

  2. La funzione max è già implementata in C++, non ti serve scriverla tutte le volte da capo

  3. Chiamare una funzione function non è il massimo, in quanto il nome risulta ambiguo ad alcuni editor e compilatori. Dai nomi brevi, significativi e poco ambigui

  4. Generalmente avere variabili globali che si modificano dentro a funzioni ricorsive è molto rischioso, cioè devi essere molto bravo e sapere costa stai facendo per usarle bene (la tua variabile contatore). Io personalmente ti sconsiglio di usarle se sei alle prime armi

  5. Attento alle dichiarazioni dei for. Nella tua funzione function dichiari i = k + 1, ma se poi chiami la tua funzione con il parametro k = n - 1, i diventerà uguale ad n e si andranno a fare dei casini con gli indici dei vettori

  6. Quando prendi in input un vettore un usare push_back. Infatti anche se sulla wiki c’è scritto che ha un tempo costante non è proprio vero, ed è abbastanza lento qando i numeri diventano tanti. Piuttosto dichiara inizialmente la grandezza del vettore (tanto la sai sempre visto che hai N) e successivamente utilizza un semplice cin >> v[i]. Se il vettore è globale e si dichiara prima che tu prenda in input N, allora puoi semplicemente ridimensionarlo appena hai il numero di elementi che contiene con v.resize(N).
    Come suggerisce @MyK_00L puoi anche scrivere for(int &i:v)cin>>i. Vedi te cosa preferisci

  7. Se aggiungi queste tre istruzioni al tuo programma prenderà gli input più velocemente: ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

  8. È inutile ri-inizializzare una variabile a zero se poi la prendi in input (riga 87 del tuo programma).

  9. Evita di utilizzare così tanti spazi tra un’istruzione e un altra, rende il codice molto dispersivo e difficile da leggere

Per il resto dovrei averti detto tutto quello che potevo. Se hai qualche domanda falla pure senza problemi (soprattuto se non hai capito qualcosa della spiegazione).

1 Mi Piace

La complessita’ della prima soluzione dovrebbe essere \mathcal{O}(2^n) (edited, me dumb), ma aggiungedo una memo a quella funzione diventa \mathcal{O}(n^2)
Comunque esistono diverse soluzioni simili a quelle proposte per questo problema in \mathcal{O}(n \cdot log{n}) (se nella prima soluzione al posto di fare una ricerca lineare del massimo si usa una struttura dati tipo fenwick tree, assume questa complessita’ (obv a quel punto la implementi iterativa tho), oppure c’e’ anche una soluzione con binary search).
random side note: push_back e’ costante amortizzato, di fatto puoi considerarlo costante, ma tanto fai prima a scrivere

vector<int> v(n);
for(int &i:v)cin>>i;

che e’ piu veloce

1 Mi Piace

ciao samuele, intanto grazie mille per l’aiuto!
Ho capito dove sbaglaivo però volevo farti qualche domanda.
Capisco quello che hai scritto nella parte due della risposta ma non capisco perchè sia necessario l’array di booleani, dato che siamo sicuri che le sequenze che terminano con i valori precedenti alla k siano già stati calcolati, o sbaglio? Infatti io ho riscritto la funzione però ho inserito direttamente un array contenente i risultati della funzione per ogni valore di k e in teoria dovrebbe funzionare. Il problema è che quando lo sottopongo sul portale di allenamento prendo 55/100. Questo però probabilmente perchè il tempo di compilazione viene 2.5 secondi, ma non capisco perchè così tanto.
e infine ti volevo chiedere anche come evitare di dichiarare la variabile “contatore” globale, dato che non penso sia corretto dichiararla nella funzione nel caso sia ricorsiva, dato che così facendo si dichiarerebbe ad ogni ricorsione.

#include <bits/stdc++.h>

using namespace std;

int v[3000];

int appoggio[3000];

int n;

int contatore = 1;

int SeriePanini (int k)

{

    if (k == 0)

    {

        return 1;

    }

    for (int i = k; i > 0; i--)

    {

        if (v[i] > v[k])

        {

            contatore = max(contatore, 1 + appoggio[i]);

        }

    }

    return contatore;

}

int main()

{

    freopen("input.txt", "r", stdin);

    freopen("output.txt", "w", stdout);

    int risultato = 1;

    cin >> n;

    //riempimento del vettore in input

    for (int i = 0; i < n; i++)

    {

        cin >> v[i];

    }

    //richiamo la funzione

    for (int j = 0; j < n; j++)

    {

        appoggio[j] = SeriePanini(j);

        contatore = 1;

    }

    //stamp il rislutato

    for (int a = 0; a < n; a++)

    {

        risultato = max(risultato, appoggio[a]);

    }

    cout << risultato;

    return 0;

}

Ciao @flp_o3,
Il tuo codice è praticamente giusto! Bisogna solo modificare 3 cose che probabilente ti sei dimenticato di aggiungere oppure proprio non ci hai fatto caso:

  1. Nel testo del problema è sempre indicata la grandezza massima dell’input. E se controlli il testo dice che n (la quantità di numeri in input) è sempre minore o uguale a 1000. Di conseguenza se dichiari i tuoi due array con una grandezza massima di 3000 non riuscirai a contenere tutti i numeri che ti vengono dati nei vari testcase!
  2. Nella tua funzione ricorsiva la variabile i parte da k, ma questo concettualemente è sbagliato in quanto tu devi controllare solo le sequenze prima della posizione k, e non k stessa visto che la stai calcolando.
  3. Nella condizione del for hai messo i > 0. Errore piuttosto comune visto che non si è abituati a scrivere for al cotrario. Ma in questo modo la sequenza che parte a posizione 0 non la controlli mai visto che la i si ferma a 1.

Fatti questi piccoli aggiustamenti il tuo programma prende un soddisfacente 100/100!

Codice corretto
#include <bits/stdc++.h>

using namespace std;

int v[10001];

int appoggio[10001];

int n;

int contatore = 1;

int SeriePanini (int k)

{

    if (k == 0)

    {

        return 1;

    }

    for (int i = k - 1; i >= 0; i--)

    {

        if (v[i] > v[k])

        {

            contatore = max(contatore, 1 + appoggio[i]);

        }

    }

    return contatore;

}

int main()

{

    freopen("input.txt", "r", stdin);

    freopen("output.txt", "w", stdout);

    int risultato = 1;

    cin >> n;

    //riempimento del vettore in input

    for (int i = 0; i < n; i++)

    {

        cin >> v[i];

    }

    //richiamo la funzione

    for (int j = 0; j < n; j++)

    {

        appoggio[j] = SeriePanini(j);

        contatore = 1;

    }

    //stamp il rislutato

    for (int a = 0; a < n; a++)

    {

        risultato = max(risultato, appoggio[a]);

    }

    cout << risultato;

    return 0;

}

Per le domande:

  1. Hai ragione, l’array di booleani è inutile! Abbiamo già sicuramente calcolato tutti i valori precedenti visto che il for che calcola i valori della fuzione parte da 0. Se però partisse dal fondo dell’array e cioè da N - 1 in quel caso allora servirebbe.
  2. Il tempo di compilazione è totalmente ininfluente sull’assegnazione del punteggio!
  3. In realtà è corretto dichiarare la varibiale “contatore” dentro la funzione in quanto globalmente non ti serve a nulla. Quella variabile viene usata soltanto dentro quella funzione, quindi è molto più “pulito” farla rimanere interna. Non importa se si ridichiara ad ogni ricorsione, in quanto le dichiarazioni non si andrebbero a sommare visto che ogni volta che la funzione termina, quella variabile viene “cancellata” dalla memoria.

Dovrei aver risposto a tutto, ma se hai ancora dubbi scrivi pure!

P.S. Il tuo programma, scritto in questo modo e con l’ausilio dell’array per memorizzare, non è più ricorsivo ma è diventato iterativo! Non so se te ne sei accorto…

ciao @samuelemusiani ho corretto tutto e adesso è 100/100!
Grazie mille, non solo per l’aiuto per la risoluzione del problema, ma anche per tutti i consigli generali sulla programmazione. Mi hai fatto capire molte cose che finora nessuno mi aveva spiegato. Grazie davvero tanto per la disponibilità.