+1

Potwierdzam

Potwierdzam

Potwierdzam

Potwierdzam

Potwierdzam

Potwierdzam

Potwierdzam

Około 0.6s na test

Ile czasu zajmuje wam przejście tej paczki?

Załóżmy, że mamy k dzieci, a w i-tym z nich mamy 4 wartości [zero_i, jeden_i, dwa_i, trzy_i] z dynamika. Na początku wybieramy dla każdego z dzieci tę z czterech wartości, która jest największa. Czyli np. dla i-tego dziecka wybierzemy dwa_i, bo akurat dwa_i >= max(zero_i, jeden_i, trzy_i). W ten sposób dostaniemy pewną konfigurację, w której jest sumarycznie Z zer, J jedynek, D dwójek i T trójek. Co więcej, to jest optymalny wynik i nie da się uzyskać lepszego dla takiej konfiguracji liczb zer, jedynek, dwójek i trójek. Załóżmy teraz, że chcielibyśmy uzyskać konfigurację (Z', J', D', T') != (Z, J, D, T). To trzeba w niektórych dzieciach powybierać inne wartości, żeby to zrobić. No to robimy tak, że tworzymy 4 wierzchołki: W0, W1, W2 i W3, każdy odpowiadający jednej z czterech wartości. Tworzymy też źródło Ź i ujście U. No i jeśli załóżmy J' > J, to znaczy, że aktualnie mamy niedomiar jedynek, więc chcielibyśmy ich więcej. Zatem tworzymy krawędź z W1 do U o przepustowości J'-J. I analogicznie krawędź z W0 do U ma przepustowość max(0, Z' - Z), krawędź z W2 do U ma przepustowość max(0, D' - D), itd. Z kolei, jeśli J > J', to znaczy, że mamy nadmiar jedynek i chcemy się ich pozbyć. Więc tworzymy krawędź z Ź do W1 o przepustowości J-J'. I analogicznie z Ź do W3 tworzymy krawędź o przepustowości max(0, T - T'), itd. Wagi tych wszystkich krawędzi pomiędzy źródłem/ujściem a czymś to 0. Pozostaje jeszcze potworzyć krawędzie pomiędzy wierzchołkami W0, W1, W2 i W3. No to jeśli mieliśmy czwórkę [zero_i, jeden_i, dwa_i, trzy_i], w której załóżmy, że optymalną wartością było dwa_i, to możemy stworzyć przejściowy wierzchołek P_i i następujące krawędzie o przepustowości 1: A) Z W2 do P_i o wadze 0, B) z P_i do W0 o wadze zero_i-dwa_i, C) Z P_i do W1 o wadze jeden_i-dwa_i, D) Z P_i do W3 o wadze trzy_i-dwa_i. No i w takim grafie, jeśli znajdziemy maksymalny przepływ o maksymalnym koszcie, to koszt tego przepływu to będzie różnicą w kosztach pomiędzy optymalną wagą początkowej konfiguracji a optymalną wagą w konfiguracji docelowej. Problemem jest jeszcze to, że ten graf jest duży - ma 6+k wierzchołków oraz 4+4k krawędzi. To sprawia, że szukanie pojedynczej ścieżki powiększającej przepływ jest O(k), a takich ścieżek będziemy szukać potencjalnie aż O(k). Natomiast to co można zrobić, to podczas szukania pojedynczej ścieżki powiększającej udawać, że nie ma wierzchołków P_i, i np. zamiast ścieżki W2->P_i->W1 możemy zrobić bezpośrednią krawędź W2->W1 o wadze jeden_i-dwa_i. Wiemy, że dopóki szukamy tylko jednej ścieżki powiększającej, to z W2 do W1 przejdziemy co najwyżej raz, więc zamiast mieć O(k) krawędzi pomiędzy W2 i W1, to tworzymy tylko jedną krawędź - tę o największej wartości jeden_i-dwa_i. W ten sposób dostajemy graf, który ma 6 wierzchołków i O(6^2) krawędzi. I ten graf wystarcza do znalezienia jednej ścieżki powiększającej. Gdy taką ścieżkę znajdziemy, to musimy teraz zaktualizować krawędzie pomiędzy W2 i W1, bo największa wartość jeden_i-dwa_i mogła się zmienić (to robimy w O(log(k)) trzymając możliwe wagi na setach). No i tak szukamy pojedynczych ścieżek dopóki nie dojdziemy do pożądanej konfiguracji. I to była ogólna metoda jak w O(x * log(k) * O(6)) dojść z jednej konfiguracji do drugiej, gdzie x = |Z - Z'| + |J - J'| + |D - D'| + |T - T'|. To jest chyba w zasadzie to samo co opisał Wojtek, ale zamiast ręcznie rozważać przypadki, to się szuka ścieżek w grafie przepływowym.

potwierdzam

potwierdzam

Potwierdzam

potwierdzam