Olympiads

Daje jest tablica liczb mająca $n$ wierszy i $k$ kolumn. Wybranie podzbioru $k$ wierszy z tej tablicy utworzy kwadratową tablicę $k\times k$. Jej koszt to suma największych liczb z każdej kolumny. Mamy znaleźć $C$-ty co do wielkości koszt podzbioru.

Przypadek $k\le 2$

Dla $k=1$ mamy dokładnie $n$ możliwych podzbiorów, każdy składa się z jednej liczby (bo $k=1$ oznacza też jedną kolumnę), która jest jego kosztem. Sortujemy więc wszystkie koszty i z posortowanej listy wybieramy $C$-ty.

Dla $k=2$ rozważamy wszystkie możliwe podzbiory, czyli pary wierszy. Obliczenie ich kosztów i sortowanie będzie działać w czasie $O(n^2\log n)$:

int main() {
  scanf("%d%d%d",&n,&k,&c);
  REP(i,n) {
    REP(j,k) scanf("%d",&a[i][j]);
  }

  if (k == 1) {
    REP(i,n) scores.push_back(a[i][0]);
  } else if (k == 2) {
    REP(i,n) REP(j,i) {
      scores.push_back(max(a[i][0], a[j][0]) + max(a[i][1], a[j][1]));
    }
  }
  sort(scores.begin(), scores.end(), greater<int>());
  printf("%d\n", scores[c-1]);
}

Rozwiązanie wzorcowe

Pomysł jest taki, że będziemy konstruować podzbiory w kolejności ich kosztów.

Łatwo jest znaleźć podzbiór o największym koszcie (czyli dla $C=1$). Ponieważ mamy zmaksymalizować sumę wartości z $k$ kolumn, a do podzbioru mamy wziąć $k$ wierszy, więc wystarczy dla każdej kolumny zaznaczyć wiersz, który ma największą wartość w tej kolumnie (w razie remisów zaznaczamy dowolny). Jeśli zaznaczyliśmy mniej niż $k$ wierszy (bo pewien wiersz miał maksima w więcej niż jednej kolumnie), to możemy dołożyć do podzbioru jakiekolwiek wiersze, byle w sumie ich było $k$ (nie zmieni to wyniku).

Mamy zatem wybrany najlepszy podzbiór $B=(b_1,b_2,\dots ,b_k)$. Teraz podzielimy przestrzeń wszystkich innych podzbiorów na $k$ rozłącznych części i w każdej niezależnie znajdziemy najlepszy podzbiór.

Do pierwszej części wrzucimy podzbiory niezawierające wiersza $b_1$. Do drugiej części wrzucimy podzbiory zawierające wiersz $b_1$, ale niezawierające wiersza $b_2$. W ogólności do $i$-tej części wrzucimy podzbiory zawierające wiersze $b_1,b_2,\dots ,b_{i-1}$, ale niezawierające wiersza $b_i$.

Łatwo zobaczyć, że wszystkie części są rozłączne ze sobą, oraz że pokrywają wszystkie podzbiory z wyjątkiem $B$.

Każda z tych części może być opisana dwoma ciągami wierszy: tymi, które muszą być w podzbiorze, i tymi, które nie mogą być w podzbiorze. W każdej części możemy wybrać podzbiór o największym koszcie, tak jak opisywaliśmy wcześniej (musimy tylko wziąć pod uwagę ograniczenia nakładane na wybór wierszy).

Tak więc dla $C=2$ szukany podzbiór to będzie ten o największym koszcie spośród wszystkich części. Jeśli będzie to podzbiór $B_2$ należący do części $P$, to możemy tę część też podzielić na kawałki, które pokrywają $P$ z wyłączeniem $B_2$.

Algorytm więc będzie następujący: na kolejce priorytetowej trzymamy wszystkie części (posortowane po koszcie najlepszego podzbioru), na które aktualnie podzielona jest przestrzeń wszystkich podzbiorów (na początku inicjujemy kolejkę częścią zawierającą wszystkie podzbiory, czyli nie mającą żadnych ograniczeń na wybór wierszy).

Potem $C$ razy wykonujemy: wyciągamy górny element kolejki, czyli część $P$, a następnie dzielimy ją i wkładamy części z podziału $P$ z powrotem do kolejki. Na końcu wypisujemy koszt ostatnio wyciągniętego elementu.

Podczas całego algorytmu na kolejkę wrzucimy co najwyżej $Ck$ części, więc koszt obsługi kolejki to $O(Ck\log (Ck))$. Podział elementu kolejki na mniejsze części (wraz z obliczeniem ich kosztów) to $O(k^{2}n+k^3)$. Zatem całkowita złożoność czasowa to $O(C(k\log (Ck)+k^{2}n+k^3))$.

struct part {
  int cost;
  vector<int> team, forced, banned;

  part(const vector<int>& forced, const vector<int>& banned)
      : forced(forced), banned(banned) {
    team = forced;
    vector<int> used(n);
    for (int i : forced) { used[i] = 2; }
    for (int i : banned) { used[i] = 1; }

    for (int i = forced.size(); i < k; ++i) {
      int idx = -1, best = 0;
      REP(j,n) if (used[j] != 1) {
        if (idx == -1 || a[j][i] > a[idx][i]) {
          best = a[j][i];
          if (!used[j]) { idx = j; }
        }
      }
      team.push_back(idx);
      used[idx] = 2;
    }

    cost = 0;
    REP(i,k) {
      int c = 0;
      REP(j,k) c = max(c, a[team[j]][i]);
      cost += c;
    }

  }

  void split();

  bool operator<(const part& other) const { return cost < other.cost; }
};

priority_queue<part> que;

void part::split() {
  for (int i = forced.size(); i < k; ++i) {
    banned.push_back(team[i]);

    if (banned.size() > n-k) break;
    que.push(part(forced, banned));

    banned.pop_back();
    forced.push_back(team[i]);
  }
};


int main() {
  scanf("%d%d%d",&n,&k,&c);
  REP(i,n) {
    REP(j,k) scanf("%d",&a[i][j]);
  }

  que.push(part(0, {}, {}));

  int cost;
  REP(i,c) {
    part p = que.top();
    cost = p.cost;
    que.pop();
    p.split();
  }

  printf("%d\n", cost);
}