Jak rozwiązać optymalnie zadanie Cukierki?

Ja zrobiłem to dość prosto - do mapy t[możliwa_końcowa_suma_cukierków]=ilość_rozwiązań; dodawałem kolejno opakowania od najmniejszego. Niestety dla przypadków typu:

5000
1 2 3 4 5 6 7 .... 4999 5000

nie kończyło się to w rozsądnym czasie, przez co nie przechodziło dwóch ostatnich grup testów (8/10). Wygląda że się robiło O(n^3 log n).

Zauważ że wszystkie sumy powyżej 5000 są sumowane przy dodawaniu kolejnego pudełka więc nie ma sensu ich rozróżniać zatem wystarczy zliczać tylko początkowe 5000 a powyżej w jeden worek.

Ja mam rozwiązanie O(n^2)

Robiłem programowanie dynamiczne, w dp[i] trzymam ilość sposobów utworzenia poprawnego ciągu dającego sumę i (tablica ma rozmiar 5000). Ciąg na wejściu sortuję niemalejąco. Możemy zauważyć, że jeżeli da się utworzyć poprawny ciąg o sumie a[i]-1 lub większej, to można dodać do niego element a[i] i ciąg nadal będzie poprawny. Zatem robię coś podobnego do problemu plecakowego, dla kolejnych elementów a[i] przechodzę pętlą for (int j=5000; j>=a[i]-1; j--) i wykonuję dp[j+a[i]] += dp[j]; oczywiście wszystko moduluję. Zostaje jeszcze jedna obserwacja - j+a[i] może być większe od 5000. Warto zauważyć, że wtedy opłaca się zwiększyć dp[5000], ponieważ na wejściu mamy liczby do 5000, więc każdy poprawny ciąg dający sumę 5000 lub większą da się przedłużyć. Wystarczy zatem zmienić dp[j+a[i]] += dp[j]; na dp[min(5000, j+a[i])] += dp[j]; (oczywiście wszystko modulujemy). Na koniec sumujemy wszystkie wartości dp[i] dla i = 1, ... , 5000

Dodanie std::min(..., 5000) spowodowało że się wykręca w max 1,5s :/

W zasadzie wystarczy rozbijać do max(a)-2, bo dla max(a) będziemy sumować koszyki >= max(a)-1.

Tak samo 8/10. Też nie zauważyłem tego o czym napisał Tomasz, ale zmęczony już byłem :)

Też mam 8/10, ale z innego powodu. Łapałem w worek elementy większe niż 5000, ale zapomniałem je liczyć do sumy. I wtedy przychodził element a_i=5000 i program stwierdzał, że on jest za duży i nie przetworzy więcej. Więc 8/10, bo testy 3h i 8h dały zły wynik :D

Dowód poprawności rozw. przez programowanie dynamiczne.

Niech X to zbiór szukanych (nazwijmy je właściwymi) podzbiorów zbioru A.
Zał, że dokładamy element p do A gdzie p >= max(A), i chcemy zaktualizować X. W zaktualizowanym zbiorze X będą te zbiory co wcześniej i dodatkowo pewne podzbiory A z dodanym elementem p.

Jeżeli B jest podzbiorem A i sum(B) <= p - 2 to wart. p - 1 nie da się utworzyć przez dodanie p, czyli nie da się utworzyć szukanego zbioru ze zbioru B.
Dalej zał, że sum(B) >= p - 1.

Dołożenie p do właściwego podzbioru B zbioru A spowoduje utworzenie szukanego zbioru, jeżeli sum(B) >= p - 1 - każda z liczb z przedziału [p + 1, sum(B) + p] zostanie utworzona poprzez dodanie do p pewnego podzbioru B, a liczby z przedziału [1, p - 1] są utworzone przez podzbiory B bo sum(B) >= p - 1.

Dołożenie p do niewłaściwego podzbioru B zbioru A nigdy nie spowoduje utworzenia szukanego zbioru.

Lemat. Niech B = {b_1, b_2, ..., b_k}, b_1 <= b_2 <= ... <= b_k.
Jeżeli każdą z sum z przedziału [1, b_k] da się utworzyć przy pomocy podzbiorow B to każdą sumę z [1, sum(B)] też da się utworzyć.
Dowod lematu. Każdą sumę z przedziału [1, b_k] da się utworzyć => każdą sumę z przedziału [1, b_l] da się utworzyć przy pomocy {b_1, b_2, ..., b_l} dla 1 <= l < k.
Wtedy dla każdego 1 <= l <= k każdą sumę z przedziału [b_k + b_(k-1) + ... b_(l+1), b_k + b_(k-1) + ... b_(l+1) + b_l - 1] też da się utworzyć po dodaniu do b_k + b_(k-1) + ... b_(l+1) liczby z przedziału [1, b_l] czyli pewnego podzbioru {b_1, b_2, ..., b_l}.

Z lematu wynika, że dla niewłaściwego zbioru B istnieje liczba z przedziału [1, b_k - 1], której nie da się utworzyć, ale b_k <= p, czyli nie da się jej utworzyć też po dodaniu p do B.

Programowane dynamiczne pisałem podobne jak wyżej, przetwarzam liczby z A w kolejności rosnącej. W dp[i] trzymam ilość sposobów utworzenia poprawnego ciągu dającego sumę i (tablica ma rozmiar 5000). Dodatkowo trzymam zmienną przechowującą liczbę wszystkich szukanych zbiorów.