B.F.S. (streaming)

Aiuto
1

sono su sto problema da abbastanza tempo, ho provato un po’ di approcci ma si sono rivelati tutti sbagliati, per diversi motivi. Il primo è stato di tipo sorting and searching + programmazione dinamica, con questo codice:

#include <bits/stdc++.h>
using namespace std;
using ll = long long int;

struct utenti{
    ll prezzo;
    ll film;
};

ll ind, biglietto;
vector<utenti> v;

void aggiorna(ll &budget, int i){
    biglietto = v[i].prezzo;
    budget -= v[i].film;
}

ll inzialize(ll &budget, int n){
    while(v[ind].film > budget && ind < n) ind ++;
    biglietto = v[ind].prezzo;
    budget -= v[ind].film;
    return v[ind].prezzo - v[ind].film;
}


ll bfs(int n, ll budget, vector<int> prezzi, vector<int> film){

    v.resize(n);
    vector<ll> dp;

    for(int i = 0; i < n; i++){
        v[i].prezzo = prezzi[i];
        v[i].film = film[i];
    }

    sort(v.begin(), v.end(), [](utenti a, utenti b) { 

        if(a.prezzo - a.film == b.prezzo - b.film) return a.film < b.film;
        return a.prezzo - a.film > b.prezzo - b.film; 

    });
    
    if((v[0].prezzo - v[0].film) < 0) return 0;
    
    dp.push_back(inzialize(budget, n));

    if(ind == n) return 0;

    for(int i = ind+1; i < n; i++){

        if(v[i].prezzo - v[i].film <= 0) return dp.back();

        if(v[i].film > budget) continue; 

        if(biglietto > v[i].prezzo){

            ll guadagno = (dp.back() - (dp.size())*(biglietto - v[i].prezzo)) + (v[i].prezzo - v[i].film);

            if(dp.back() < guadagno){

                dp.push_back(guadagno);
                aggiorna(budget, i);

            }

        }else{

            dp.push_back(max(dp.back(), dp.back() + (biglietto - v[i].film)));
            budget -= v[i].film;

        }
        
    }

    return dp.back();
}

ma sono riuscito a fare solo 5/100 con errori di tipo “output not correct”, quindi non riuscivo sempre a trovare la soluzione ottima, tranne che in 27/71 testcase, di cui tutti i testcase del subtask 3.

Allora li ho capito c’è bisogno di controllare quasi tutte le possibili combinazioni di utenti per capire il prezzo del biglietto da impostare. Quindi ho pensato ad un approccio backtracking, ma ottimizzando qualcosina grazie all’ordinamento del vettore in base al prezzo, e qualche if che taglia un po’ di rami dell’albero delle chiamate che la mia funzione fa. Il codice è questo:

#include <bits/stdc++.h>
using namespace std;
using ll = long long int;

struct utenti{
    ll prezzo;
    ll film;
};
vector<utenti> v;

ll best = 0;

void backtracking(ll spese, ll budget, int n, ll income = 0, int taken = 0){
    //cout<<"spese:"<<spese<<" | n:"<<n<<" | income:"<<income<<" | taken:"<<taken<<endl;
    if(n < 0){
        if(spese <= budget) best = max(best, income - spese);
        return;
    }

    if(spese + v[n].film > budget) best = max(best, income - spese);
    else backtracking(spese + v[n].film, budget, n-1, v[n].prezzo * (taken + 1), taken+1);

    backtracking(spese, budget, n-1, income, taken);

    return;   

}


ll bfs(int n, ll b, vector<int> p, vector<int> f){

    for(int i = 0; i < n; i++){
        if(p[i] - f[i] <= 0) continue;
        if(f[i] > b) continue;
        v.push_back({p[i], f[i]});
    }

    sort(v.begin(), v.end(), [](utenti a, utenti b){return a.prezzo < b.prezzo;});

    backtracking(0, b, v.size()-1);

    return best;
}

/*int main(){
    int n;
    ll q;
    cin >> n >> q;
    vector<int> p(n), f(n);
    for(int i = 0; i < n; i++) cin >> p[i];
    for(int i = 0; i < n; i++) cin >> f[i];

    cout<<bfs(n, q, p, f);

}*/

Anche se l’approccio è backtracking ho fatto un algoritmo molto poco elegante, però si dovrebbe capire un minimo la solita questione: “ogni volta ho 2 possibilità: considerare l’untente o no”. Solo che in questo caso faccio 7/100 con 25/71 testcase, per errori di tipo “Execution timed out” che ci può stare visto la complessità, però di questo passo non so proprio come poter ottimizzare la ricerca. è l’approccio sbagliato oppure si può ottimizzare ancora? Mi manca qualche tecnica avanzata da studiare?

2

In effetti è un esercizio a trabocchetto. Si chiama B.F.S, si presenta come un knapsack, in realtà la soluzione ottimale è

Greedy in O(N \cdot log N).

Qui sotto ti lascio qualche hint verso la soluzione.

Inanzitutto, la prima osservazione da fare è che tutti i membri per cui vale F_i \ge P_i si possono scartare, perchè non sarà mai conveniente impostare la quota a P_i. Si possono anche scartare tutti i membri che hanno F_i > K. Immagino si possa dimostrare che conviene ma sono troppo pigro per farlo :slight_smile: .
Torna anche utile ordinare tutti i membri rimasti in ordine decrescente usando come criterio P_i.

Ora, l’altro dettaglio essenziale è che, una volta impostata una quota P, ogni membro che è disposto a pagare la quota pagherà P e non P_i.
Il profitto del club sarà quindi (P \cdot K) - D, dove K sono le persone ammesse al club se si imposta la quota P, mentre D è il costo totale dei film dei membri selezionati. Stiamo quindi cercando di massimizzare (P \cdot K) - D.
Per fare ciò dobbiamo avere più persone possibili tali che \sum_{i=1}^{n} F_i \le F. Dovremo quindi, per ogni quota, trovare il massimo numero di persone che possiamo ammettere al club in modo che il costo complessivo dei diritti sia minore o uguale a quello che siamo disposti a spendere. Quindi calcolare (P \cdot K) - D e trovare il massimo valore che può assumere.

Spero di essere stato abbastanza chiaro, se hai bisogno di altro chiedi pure!

1 Mi Piace