Omówienie zadania Bagaż podręczny (I etap XXXIII OI, tura szkolna)

Rozwiązanie

Zacznijmy od uporządkowania ograniczeń bagażu podręcznego tak, aby liczby w ramach ograniczenia były uporządkowane niemalejąco. Jeśli \((A_i,B_i,C_i)\) jest takim ograniczeniem, to przez \((a_i,b_i,c_i)\) oznaczmy ograniczenie takie, że \(a_i \le b_i \le c_i\) i multizbiory \(\{A_i,B_i,C_i\}\) i \(\{a_i,b_i,c_i\}\) są takie same. Ograniczenia można przekształcić, używając dowolnego algorytmu sortowania.

Przyjmijmy, że bagaż ma wymiary \(X \times Y \times Z\) takie że \(X \le Y \le Z\). Jeśli \(X \le a_i\), \(Y \le b_i\) i \(Z \le c_i\), to spełnia on ograniczenie \((a_i,b_i,c_i)\). Na koniec uzasadnimy, że zachodzi tu równoważność, tj. że zawsze wystarczy porównywać posortowane wymiary bagażu z ograniczeniem z posortowanymi wymiarami.

Teraz już możemy zauważyć, że największy możliwy bagaż przy podanych ograniczeniach ma wymiary \(X \times Y \times Z\) takie że \(X=\min_i a_i\), \(Y=\min_i b_i\), \(Z=\min_i c_i\). Wynik wyznaczamy w czasie \(O(n)\).

Dlaczego to działa?

Warto rozważyć bardziej ogólny problem, w którym mamy dwa ciągi liczb \(x_1,x_2,\ldots,x_m\) i \(y_1,y_2,\ldots,y_m\) i pytamy, czy możemy poprzestawiać liczby w każdym z ciągów, otrzymując ciągi \(x_{i_1},x_{i_2},\ldots,x_{i_m}\) i \(y_{j_1},y_{j_2},\ldots,y_{j_m}\) (przy czym \(\{i_1,\ldots,i_m\}=\{j_1,\ldots,j_m\}=\{1,\ldots,m\}\)) takie że \(x_{i_k} \le y_{i_k}\) dla każdego \(k=1,\ldots,m\). W tym zadaniu mamy ten problem w prostym przypadku \(m=3\).

Załóżmy bez straty ogólności, że wyjściowe ciągi są posortowane, tj. \(x_1\le x_2\le \ldots\le x_m\) i \(y_1\le y_2\le \ldots\le y_m\). Zamiast przestawiać elementy w obu ciągach, wystarczy przestawiać elementy w ciągu \(x\). Załóżmy, że istnieje sposób poprzestawiania \(x_{i_1},x_{i_2},\ldots,x_{i_m}\) elementów ciągu \(x\) taki że \(x_{i_k} \le y_k\) dla każdego \(k=1,\ldots,m\). Wykażemy, że wówczas mamy \(x_k \le y_k\) dla każdego \(k=1,\ldots,m\).

Jeśli \(i_1=1\), to nasz problem redukuje się do tego samego problemu dla ciągów długości \(m-1\). W przeciwnym razie, niech \(t\) będzie indeksem takim że \(i_t=1\). Jako że zachodzi \(x_{i_1} \le y_1\) i \(x_1=x_{i_t} \le y_t\) oraz \(x_1 \le x_t\) i \(y_1 \le y_t\), to zachodzi \(x_1 \le x_{i_1} \le y_1\) i \(x_{i_1} \le y_1 \le y_t\), więc możemy zamienić miejscami elementy \(x_{i_1}\) i \(x_{i_t}=x_1\), co sprowadza nas do poprzedniego przypadku. To właściwie kończy dowód (formalnie, używamy tu argumentu indukcyjnego).