2. Zabudnutá chata vzorové riešenie

3 47
47 1 42

2

10 7
0 1 0 0 2 1 1 1 0 1

0

Predstavme si, že vieme po akej sume sa budú vedúci skladať. Pomôže nám to? Na chatu chcú ísť všetci vedúci, ktorí môžu, a teda ak sa skladajú po \(5\) eurách, pôjdu všetci tí, ktorí majú aspoň \(5\) eur, ak po \(7\)-mich, tak tí, čo majú aspoň \(7\).

Nech teda každý, kto môže, zaplatí sumu \(S = 5\) eur. Ak postupne prejdeme limity všetkých vedúcich, vieme spočítať, koľko vedúcich na to má. Ostáva nám skontrolovať, či takto dokopy zaplatia za celú chatu. Ak hej, tak máme výsledok, ak nie, tak na chatu nepôjde nikto.

My ale túto sumu \(S\) nepoznáme. Nevadí, vieme vyskúšať všetky prípustné hodnoty \(S\) a pre každú z nich zistiť, koľko vedúcich tak môže ísť na chatu. Stačí nám priebežne si pamätať a upravovať najväčší počet zúčastnených vedúcich, a na konci toto číslo vypísať.

Posledná vec, ktorú musíme domyslieť, je to, aké hodnoty \(S\) máme skúšať:

• \(0\leq S\leq c\) – nedáva zmysel, aby pani domáca dostala od každého vedúceho viac ako je celková cena chaty

• \(0\leq S\leq max(s_i)\) – nemôžeme od chudákov vedúcich chcieť, aby každý zaplatil viac ako má ten najbohatší z nich

n, c = [int(x) for x in input().split()]
limity  = [int(x) for x in input().split()]

max_pocet_veducich = 0

for kolko_plati_kazdy in range(0, min(c, max(limity))+1):
    pocet_veducich = 0

    for limit_veduceho in limity:
        if kolko_plati_kazdy <= limit_veduceho:
            pocet_veducich += 1
    
    if pocet_veducich * kolko_plati_kazdy >= c:
        max_pocet_veducich = max(max_pocet_veducich, pocet_veducich)

print(max_pocet_veducich)

Keďže sa pre každú hodnotu \(S\) pozrieme na finančný limit každého z \(n\) vedúcich, je časová zložitosť tohto riešenia \(O(min(c, max(s_i)) \cdot n)\).

Pamätať si stačí finančné limity vedúcich spolu so zopár premennými – pamäťová zložitosť je preto \(O(n)\).

Hodnoty \(c\) aj \(s_i\) môžu byť však príliš veľké (až \(10^9\)) a preto musíme vymyslieť algoritmus, ktorý od nich buď nebude závisieť, alebo bude závisieť menej ako lineárne.

Skúšajme menej možností

V predošlom riešení sme robili veľa vecí navyše. Keď overujeme sumu \(S\), tak počet vedúcich, ktorí ju vedia zaplatiť sa predsa zmení až vtedy, keď \(S\) nadobudne hodnotu finančného limitu nejakého ďalšieho vedúceho. Stačí nám teda postupne prekontrolovať len \(S = s_i\), kde \(s_i\) označuje finančný limit \(i\)-teho vedúceho.

Toto riešenie sa pre každý limit pozrie na všetkých vedúcich a teda sme prišli na riešenie s časovou zložitosťou \(O(n^2)\). Takto sa na vstupoch dali získať 2 body.

Takéto riešenie dostaneme, ak jednoducho prepíšeme v predošlom programe riadok s for-cyklom na

for kolko_plati_kazdy in limity:

Skúšajme ich v správnom poradí

Skúsme sa pozrieť na druhú fázu nášho algoritmu (pre dané \(S\) chceme rýchlo zistiť, koľko vedúcich má \(s_i \geq S\)). Predstavme si, že by limity boli usporiadané podľa veľkosti: \[s_0 \leq s_1 \leq \dots \leq s_{n-1}\]

Potom vieme predsa pre \(S=s_i\) hneď povedať, koľko vedúcich má limit aspoň \(S\) – je ich presne n-i. To ale znamená, že nemusíme už nič overovať. Vyhrali sme, pretože triediť vieme v čase \(O(n \log n)\). Použitie takéhoto triedenia nám dokopy dá riešenie v celkovej časovej zložitosti \(O(n \log n)\), ktoré na testovači získa plný počet bodov.

Pamäťová zložitosť tohto riešenia je \(O(n)\) – potrebujeme si pamätať finančný limit každého vedúceho, bez toho by sme nevedeli triediť.

#include <vector>
#include <cstdio>
#include <algorithm>

using namespace std;

vector<long long> s;

int main() {

  long long n, c;

  scanf("%lld %lld", &n, &c);

  s.resize(n);
  for (int i=0; i<n; ++i)
    scanf("%lld", &s[i]);

  sort(s.begin(), s.end());

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

    // ak tento veduci nema limit, ze by sa podla neho zvladla zaplatit chata, nezaujima nas
    if ( (s[i]) * (n - i) < c)
      continue;

    // najvacsia odpoved, pretoze n-i bude uz len mensie
    printf("%lld\n", (n-i));
    return 0;
  }

  printf("0\n"); // nenasli sme riesenie
  return 0;

} 

n, c = [int(x) for x in input().split()]
limity  = [int(x) for x in input().split()]

max_pocet_veducich = 0

# metoda sorted s reversed=True nam utriedi limity od najvacsieho
# metoda enumerate nam zo zoznamu limitov vytvori zoznam dvojic 
# [(1, limit najbohatsieho), (2, limit druheho najbohastieho), ... (n, limit najchudobnejsieho)]
for pocet_veducich, najchudobnejsi in enumerate(sorted(limity, reverse=True), start=1):
    if pocet_veducich * najchudobnejsi >= c:
        max_pocet_veducich = max(max_pocet_veducich, pocet_veducich)

print(max_pocet_veducich)

BONUS: Riešenie s lineárnou časovou zložitosťou

• Pre každého vedúceho \(i\) si vyrátajme \(L_i\) – minimálny počet vedúcich, ktorí musia na chatu ísť, aby tam mohol ísť aj \(i\)-ty vedúci. Inak povedané, pre \(S = s_i\)¹ vyjadruje \(L_i\) minimálny počet vedúcich, ktorí sa po tejto sume musia skladať, aby zaplatili chatu²: \[L_i = \Big\lceil \frac{c}{s_i} \Big\rceil\]

• Vytvorme si pole \(X\), kde \(X_i\) bude reprezentovať počet vedúcich s \(L = i\). Inak, \(X_i\) hovorí o počte vedúcich, ktorí vyžadujú \(i\) vedúcich, aby išli na chatu. Toto vieme vytvoriť už za rátania hodnôt \(L\), ak vyrátame \(i\)-temu vedúcemu \(L_i\), zvýšime hodnotu \(X_{L_i}\) o jedna.

• Na tomto poli (\(X\)) si spočítame prefixové sumy. Hodnota \(X_i\) nám teraz bude hovoriť o počte vedúcich, ktorí vedia na chatu ísť, ak pôjde aspoň \(i\) vedúcich (rozmyslite si).

• Teraz nám už len stačí toto pole prejsť a ak \(i \leq X_i\), tak \(X_i\) vedúcich vie na chatu ísť. Nájdeme maximum.

Časová aj pamäťová zložitosť je už spomínané \(O(n)\), keďže len prechádzame pole a robíme na ňom aritmetické operácie.

Pozn.: Toto riešenie sme od vás nevyžadovali. Ak ste ho však vymysleli, môžete očakávať bonusové body za popis.

#include <vector>
#include <cstdio>

using namespace std;

vector<long long> s;
vector<long long> L;
vector<int> X;

int main() {

  long long n, c;

  scanf("%lld %lld", &n, &c);

  // okrajovy pripad, ked netreba platit, idu vsetci
  if (c == 0LL) {
    printf("%lld\n", n);
    return 0;
  }

  s.resize(n);
  for (int i=0; i<n; ++i)
    scanf("%lld", &s[i]);

  // ratame hodnoty L[i] a vytvarame X
  L.resize(n); X.resize(n+1, 0);
  for(int i=0; i<n; ++i) {
    
    // takyto veduci sa na chatu nedostane ...
    if (s[i] == 0LL)
      continue;

    // L[i] = horna cela cast (c / s[i])
    L[i] = (c / s[i]) + (c % s[i] > 0LL);

    // nezaujimaju nas hodnoty, ked niekto potrebuje viac veducich ako je k dispozicii
    if (L[i] <= n)
      ++X[ L[i] ];
  }

  // prefixove sumy
  for(int i=1; i<=n; ++i)
    X[i] += X[i-1];

  // a uz to len prejdeme a najdeme najvacsie
  int ret = 0;
  for(int i=0; i<=n; ++i)
    if (i <= X[i])
      ret = max(ret, X[i]);

  printf("%d\n", ret);
  return 0;

}