City Redevelopment (renovations)

durante la prima gara delle olimpiadi di informatica di quest’anno era capitato questo problema, e nonostante non conoscessi ancora i segment tree ho voluto provare a risolverlo per prendere i punti delle prime tre subtask(60/100) tuttavia ancora adesso non riesco a capire cosa ci sia di sbagliato in questo codice, e prima di scrivere la soluzione “veloce” vorrei capire cosa sbaglia il programma che ho scritto.
praticamente uso la definizione dei numeri triangolari per calcolare il numero di possibili risultato solo se il range di valori non rientra in uno dei casi speciali che non rispetta questa formula, questo è il codice:

#pragma GCC optimize ("Ofast") 
#pragma GCC optimization ("unroll-loops")
#include <bits/stdc++.h>
#define mod 1000000007

using namespace std;
ifstream in("input.txt");
ofstream out("output.txt");
// input data
int N, Q, K, type;
vector<int> V;

int main() {
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    in >> N >> Q >> K;
    V.resize(N+1);
    for (int i=1; i<=N; i++){
        in >> V[i];
        V[i]=max(V[i],K);
	}

    for (int i=0; i<Q; i++) {
        in >> type;
        if (type == 1) {
            // building update
            int a, b;
            in >> a >> b;
			V[a]=max(b,K);

        }
        if (type == 2) {
            // redevelopment planning
            int l, r, s;
            in >> l >> r >> s;
			for(int j=l;j<=r;j++)s-=V[j];
			if(s<0) out <<0<< endl;
            else if(s==0)out<<1<<endl;
            else if(l==r)out<<1<<endl;
            else if((r-l)==1)out<<s+1;
            else if(s==1)out<<r-l+1<<endl;
            else{
                int n=r-l+s-1;
                out<<(long long)(n*(n+1)/2)%mod<<endl;
            }
        }
    }
    return 0;
}

Il problema non l’ho svolto, ma mi hai fornito un suggerimento, per cui nell’ultima condizione non dovrebbero essere tutte le disposizioni possibili:

int n = r-l+s-1;
out << (long long)(n*(n+1)/2)%mod << endl; 

ma tutte le combinazioni possibili di edifici con totale s:

out << (C r-l+s, s)%mod << endl;
1 Mi Piace

Esatto, stai cercando di calcolare in quanti modi diversi puoi dividere N elementi in x gruppi, dove N sono i livelli di bellezza che ti avanzano mentre x sono gli edifici. Per farlo puoi immaginare di avere N + x - 1 elementi e devi sceglierne x - 1 da utilizzare come separatori degli x gruppi. Per esempio se dividere N = 5 elementi in x = 3 gruppi allora è equivalente a dire che hai 7 elementi e ne dovrai scegliere 2 per formare i gruppi.
comb
In questo caso scegliendo come separatori il terzo ed il quinto elemento ottieni come numero di elementi per gruppo 2, 1, 2.

Quello che stai cercando è quindi quanti modi hai di prendere x-1 elementi su un totale di N+x-1, , tale calcolo corrisponde al coefficiente binomiale {N+x-1} \choose {x -1}.

1 Mi Piace

ah, capisco, quindi in realtà i miei “casi speciali” erano soltanto delle colonne del coefficiente binomiale, compresi i numeri triangolari. Quindi il mio errore è stato il non conoscere la formula per risolvere quest’esercizio?

p.s. la bibbia spiega anche questo tipo di esercizi?