Најмањи број који није збир елемената скупа

Чињеница да су елементи сортирани олакшава решење задатка. Обрађиваћемо елемент по елемент и одржаваћемо границу до које смо сигурни да се сваки број може представити као збир неког подскупа. Можда мало изненађујуће, та граница је у сваком кораку једнака збиру свих тренутно учитаних елемената. Ако је нови учитани елемент строго већи од збира свих претходних елемената увећаног за један, онда се тај увећани збир не може добити као подскуп. У супротном можемо бити сигурни да се сви бројеви од 0 па до збира свих елемената (у који је укључен и нови елемент) могу добити као збир неког подскупа. Наиме, пошто је у претходном кораку било могуће добити све бројеве од 1 до збира свих елемената без тог новог, када у све те подскупове укључимо нови елемент добићемо све бројеве од тог новог елемента, па до збира свих елемената са тим новим елементом.

Пример. На пример, нека је дат низ \(1, 2, 3, 5, 14, 20, 27\).

0 можемо добити као збир празног скупа \(\{\}\).
1 можемо добити као збир скупа \(\{1\}\).
Када у претходне скупове укључимо и \(2\), можемо добити све бројеве закључно са \(3\) (\(2\) као \(\{2\}\) и \(3\) као \(\{1, 2\}\)).
Када у претходне скупове укључимо и \(3\), можемо добити све бројеве закључно са \(6\) (\(4\) као \(\{1, 3\}\), \(5\) као \(\{2, 3\}\) и \(6\) као \(\{1, 2, 3\}\)).
Када у претходне скупове укључимо \(5\) можемо добити све бројеве закључно са \(11\) (\(7\) као \(\{2, 5\}\), \(8\) као \(\{1, 2, 5\}\) и \(9\) као \(\{1, 3, 5\}\), \(10\) kao \(\{2, 3, 5\}\) и \(11\) као \(\{1, 2, 3, 5\}\)).
Пошто је наредни број \(14\), јасно је да се број \(12\) не може никако добити.

#include <iostream>

using namespace std;

int main() {
  int n;
  cin >> n;
  // sabiranjem elemenata trenutnog skupa mogu se dobiti svi elementi
  // iz intervala [0, mozeDo]
  int mozeDo = 0; 
  for (int i = 0; i < n; i++) {
    int x; cin >> x;
    if (x > mozeDo + 1)
      break;
    mozeDo += x;
  }
  cout << mozeDo + 1 << endl;
  return 0;
}

Сложеност. Програм се решава једним проласком кроз низ бројева и сложеност је прилично очигледно \(O(n)\).

Доказ коректности. Докажимо и формално коректност, овог алгоритма тј. програма датог у прилогу.

Лема: Нека је \(m\) вредност променљиве mozeDo. Инваријанта петље је да је \(0 \leq i \leq n\), да је \(m\) збир првих \(i\) елемената низа и да се сваки број из интервала \([0, m]\) може добити као збир неког подскупа првих \(i\) елемената низа.

Доказ: Пре уласка у петљу је \(i=0\) и \(m=0\). Збир првих \(i=0\) елемената низа је по дефиницији нула (тј. \(m\)). Број \(0\) је једини елемент интервала \([0, m] = [0, 0]\) и он се може добити као збир празног подскупа (тј. 0 елемената полазног низа).

Претпоставимо да тврђење важи пре уласка у петљу.

Ако је \(a_i > m+1\), тврдимо да је \(m+1\) тражени најмањи број. На основу инваријанте знамо да су сви бројеви из интервала \([0, m]\) покривени, тако да мањи број од \(m+1\) не може бити решење. Докажимо да број \(m+1\) не може бити збир подскупа. Пошто је низ сортиран, сви елементи од \(a_i\) до \(a_{n-1}\) су строго већи од \(m+1\). Дакле, ни један од тих елемената не сме бити укључен у подскуп јер би њиховим укључивањем збир већ премашио \(m+1\). Подскуп се мора састојати само од елемената \(a_0\) до \(a_{i-1}\), међутим, пошто је \(m\) њихов збир, збир сваког њиховог подскупа је мањи или једнак \(m\). Дакле, \(m+1\) се не може постићи и он је тражено решење.
Ако је \(a_i \leq m+1\), тада је \(m' = m + a_i\), \(i' = i + 1\) и тврдимо да је \(m'\) збир свих елемената \(a_0\), …, \(a_i\) и да се сваки број из интервала \([0, m']\) може представити као збир неког подскупа првих \(i' = i+1\) елемената низа. Прва тврдња је прилично очигледна, јер је по претпоставци \(m\) збир свих елемената \(a_0\), …, \(a_{i-1}\), а \(m' = m+a_i\). На основу претпоставке знамо да сви бројеви из \([0, m]\) могу бити збирови подскупова првих \(i\) елемената низа. Слично и сви бројеви из интервала \([a_i, a_i + m]\) се могу добити као збир неког подскупа првих \(i' = i+1\) елемента низа. Наиме, тај подскуп ће бити унија елемента \(a_i\) и оног подскупа првих \(i\) елемената низа чији је збир једнак разлици између тог броја и броја \(a_i\) – он је из \([0, m]\), па на основу претпоставке такав подскуп постоји. Пошто је \(a_i \leq m + 1\) унија интервала \([0, m]\) и \([a_i, a_i+m]\) је \([0, a_i+m] = [0, m']\). Зато је сваки елемент из \([0, m']\) једнак збиру неког подскупа првих \(i'\) елемената низа, па инваријанта остаје очувана.

Теорема: Када се програм заврши, вредност \(m+1\) је најмањи природни број који се не може представити као збир унетих бројева.

Доказ: Случај када се петља заврши прекидом, јер је \(a_i > m+1\) је већ размотрен. Када се петља заврши, важи да је \(i = n\). На основу инваријанте \(m\) је збир свих елемената низа, и сваки број из \([0, m]\) јесте збир неког подскупа првих \(i=n\) елемената низа, тј. целог низа. Зато је \(m+1\) најмањи елемент који није могуће добити (јер се укључивањем свих елемената добија највише \(m\)) и исписано решење је исправно.

У наредном аплету можете видети како овај алгоритам функционише.

✖

Најмањи број који није збир елемената скупа - Решење