Omówienie zadania Skarbiec (eliminacje do IOI 2020, dzień 2)

Wstęp

W zadaniu mamy dane \(n\) stosików, \(i\)-ty z nich zawiera \(a_i\) elementów. Mamy powiedziane, że element w normalnym stosiku ma wagę \(100,\) oraz że istnieje specjalny stosik, którego elementy mają wagę \(101\). Naszym zadaniem jest stwierdzić, który stosik jest specjalny, za pomocą minimalnej liczby ważeń, które polegają na wybraniu pewnej ilości elementów z każdego stosiku.

Znany problem

Zacznijmy od znalezienia odpowiedzi, gdy wszystkie stosiki mają rozmiar \(1\). Wtedy w ważeniu możemy po prostu albo uwzględnić jakiś stosik całkowicie, albo wcale. Możemy więc użyć w tym przypadku metody „dziel i zwyciężaj”, pytając się najpierw o lewą połowę elementów i na podstawie tego zadać kolejne zapytanie - aż do znalezienia specjalnego stosiku. Wykorzystamy przy tym \(\lceil \log_2 n \rceil\) zapytań, co, jak niedługo się dowiemy, jest optymalną ilością.

Co się dzieje, gdy wiemy, że mamy tylko jedno zapytanie do dyspozycji?

W podzadaniu drugim skorzystamy z faktu, że z góry wiemy, że musimy wykonać tylko jedno zapytanie. Jeżeli chcemy dowiedzieć się po jednym ważeniu, w którym dokładnie stosiku są specjalne elementy, to do ważenia musimy przeznaczyć inną ilość elementów z każdego stosu. Jaki jest więc najprostszy sposób, by tego dokonać? Co, gdy ciąg jest posortowany?

Gdy posortujemy ciąg, możemy po prostu przypisywać kolejne liczby całkowite, począwszy od \(0\). Mamy zagwarantowane, że jedno zapytanie wystarczy, więc nie będzie sytuacji, w której liczba, którą chcemy przypisać, przekracza liczbę elementów w stosiku.

Rozwiązanie wzorcowe

Rozwiązaliśmy już dwa podzadania i pora wyciągnąć z nich wnioski. Zauważmy, że do każdego stosiku możemy przypisać ciąg o długości \(W\), symbolizujący, ile elementów z danego stosu wzięliśmy do ważenia w danym zapytaniu. Zauważmy, żeby unikalnie wydobyć odpowiedź, ciągi te muszą być różne. Interesuje nas również najkrótsza możliwa długość ciągu, ponieważ to bezpośrednio minimalizuje ilość ważeń.

Jak więc przypisać ciągi do danych stosików? Najpierw zajmijmy się wyznaczeniem ich długości. Strategia będzie podobna jak przy drugim podzadaniu - posortujemy ciąg i będziemy chcieli patrzeć na minimalną wartość \(W\) na kolejnych prefiksach. Wiadomo, że ciągów o długości \(W\), o wartościach całkowitych nieujemnych, z maksymalną wartością równą \(M\), jest \((M+1)^W - M^W\). Możemy więc od prefiksu sprawdzać, czy obecne \(W\) jest wystarczające, a jeśli nie, to zwiększać je o \(1\).

Po wyznaczeniu wartości \(W\) możemy przypisywać kolejnym wartościom ciągi o jak najmniejszym maksimum, które nie zostały jeszcze użyte.

Sumarycznie uzyskujemy złożoność czasową \(O(nW + n\log n)\).