Gordon Ramsay

O primă observaţie trivială este aceea că x_i ≤ fr_i unde fr_i este numărul de apariţii al alimentului i.

Soluţie cu backtracking: 10 puncte

Generăm toate variantele posibile ale vectorului x pentru toate t-urile posibile şi luăm soluţia care aduce costul maxim.

Soluţie în O(N³): 25 puncte

A doua observaţie trivială este că alimentele sunt independente. Dacă ne fixăm un t, atunci putem calcula pentru fiecare aliment în parte x-ul care aduce profit cât mai mare pentru alimentul respectiv.
Astfel soluţia este să iterăm prin toate t-urile, iar pentru fiecare aliment i încercăm toate x_i de la 0 până la fr_i. Pentru un t fixat si un x_i fixat, putem calcula în O(N) profitul adus.
Numărul de operaţii făcute de program o să fie N * (fr₁ * N + fr₂ * N + … + fr_K * N) = N * (fr₁ + fr₂ + … + fr_K) * N = N³ operaţii, rezultă complexitate O(N³).

Soluţie în O(N²*logN + N*K*logN) - 40 puncte:

Putem optimiza soluţia de mai sus modificând verificarea pentru un t fixat. Calculăm un vector buck unde buck_i = numărul de clienţi satisfăcuţi în bucketul i (intervalul [i * t, i * t + t) ) dacă am avea un număr infinit de alimente. Dacă ne fixăm un x, atunci numărul de porţii servite va fi min(x, buck₁) + min(x, buck₂) + … + min(x, buck_{N / t}) porţii. Putem calcula vectorul buck_i foarte uşor folosind sume parţiale. Numărul de bucketuri pentru un t fixat va fi N / t, deci vectorul buck se calculează în O(N / t). Deoarece calculăm profitul maxim pentru fiecare aliment separat, vectorul buck va fi calculat de K ori, deci pentru calculele intermediare unde avem un t fixat o să facem N * K / t operaţii, deci în total o să facem N * K / 1 + N * K / 2 + … + N * K / N = N * K * (1 / 1 + 1 / 2 + … + 1 / N) = N * K * log N calcule intermediare.
Pentru un aliment i şi pentru un t fixat, iterăm prin toate valorile posibile ale lui x_i şi calculăm profitul maxim în O(N / t), deci numărul de operaţii pentru a calcula profitul maxim fără calculele intermediare o să fie N * (1 / 1 + 1 / 2 + … + 1 / N) * (fr₁ + fr₂ + … + fr_K) = N² * logN.
Complexitatea finală o să fie O(N²*logN + N*K*logN).

Soluţie în O(N*K*log²N) - 70 puncte

Un alt lucru care ne deranjează este faptul că verificăm multe valori irelevante ale lui x_i.
Notăm cu f_i(a) = profitul obţinut pentru alimentul i daca x_i ar fi egal cu a. Să zicem că am calculat f_i(a) unde buck_l ≤ a < a + 2 ≤ buck_l+1. Dacă ne uităm atent, o să vedem ca f_i(a + 1) = f_i(a) + C şi f_i(a + 2) = f_i(a + 1) + C = f_i(a) + 2 * C. Astfel putem observa că graficul funcţiei f_i este o linie frântă şi nu are sens să calculăm valoarea funcţiei decât vârfurile acesteia, deci în punctele buck₁, buck₁,... , buck_{N / t}.
Pentru a evalua toate punctele, le sortăm, şi le parcurgem de la cel mai mic la cel mai mare. Fie i₁, i₂, …, i_{N / t} indicii numerelor astfel încât buck{i₁} ≤ buck{i₁} ≤ … ≤ buck{i_{N / t}}. Deoarece vrem să calculăm suma min(x, buck₁) + min(x, buck₂) + … + min(x, buck_{N / t}), o să ţinem minte de fiecare dată suma pe prefixe. Dacă evaluăm indicele i_x, numărul de alimente de pe care se scoate profit o să fie buck_i1 + buck_i1 + … + buck_ix + (N - x) * buck_ix alimente.
Complexitatea va deveni O(N*K*log²N), dar în practică se comportă mai bine, deoarece un log din complexitate este supraestimat.

Soluţie în O(N*K*logN) - 100 puncte

Dacă analizăm şi mai bine funcţia, o să observăm că este convexă, mai exact aceasta creşte până într-un punct şi după scade, ba chiar mai mult, putem afla care punct este optimul printr-o parcurgere sau chiar cu formulă. Pentru a vedea care e optimul, să zicem că am calculat numărul de alimente de pe care scoatem profit pentru punctul buck_i. Verificăm ce se întâmpla dacă am mai lua un aliment în plus. Pentru toate elementele din buck care sunt mai mici, profitul total o să scadă cu cost * mai_mici şi o să crească cu profit * (N - mai_mici). Dacă ne uităm mai atent, o să vedem că pantele nu depind de vectorul buck şi ca sunt descrescătoare. Putem printr-o parcurgere să aflăm mai_mici, deci ştim că buck_{imai_mici} o să fie punctul optim. Putem să îl aflăm cu funcţia kth_element care merge în timp liniar, deci complexitatea finală o să fie O(N*K*logN).