Doszedłem do tego, żeby sprowadzić problem do ciągów o długości maksymalnie K! zamiast N, czyli 120x5 zamiast 100000x5, poprzez skonstruowanie ciągów B w których i-ty element jest sumą tych elementów ciągów A, na których elementy te są w porządku i-tej permutacji.
Wtedy jeżeli znajdę rozwiązanie w B, to mogę je przekształcić w rozwiązanie w A o takiej samej maksymalnej odległości - jeżeli na pozycji i-tej w ciągach B rozwiązanie jest pomiędzy ciągami x i y (x = perm[i][k], y = perm[i][k+1]) i powiedzmy Bsol[i] = B[i][x] + R[i], to w ciągach A rozwiązanie dla elementów z tej "permutacji" też przypadnie pomiędzy ciągami x i y i można je przydzielić dowolnie tak, żeby łącznie "zużyć" R[permclass[j]] na różnicę pomiędzy A[j][x] a Asol[j] (czyli Asol[j] = min(A[j][x] + R[permclass[j]], A[j][y]); R[i] -= (Asol[j] - A[j][x]).

Mimo takiego zmniejszenia rozmiaru problemu nie wymyśliłem co dalej i tego co miałem starczyło na 2 punkty :/.

Zacznijmy od ustawienia wszystkich liczb na medianę z 5 wartości w danej kolumnie. Liczymy odległości. Teraz zmiana wartości w danej kolumnie o 1 odpowiada zmniejszeniu dwóch z tych odległości i zwiększeniu pozostałych trzech, albo ewentualnie zmniejszeniu jednej i zwiększeniu pozostałych czterech.

No więc zadanie sprowadza się do tego: mamy 5 liczb (odległości), i dla każdej pary z nich możemy pewną liczbę razy wykonać operację zmniejszenia ich, i zwiększenia 3 pozostałych. Drugą możliwość (zmniejszenie jednej i zwiększenie pozostałych czterech) można dla ułatwienia reprezentować dodając 6-tą liczbę -∞.

Tak więc zadanie sprowadza się do zadania na grafie nieskierowanym o 6-ciu wierzchołkach z wagami na krawędziach, ale o dziwo to nie koniec. Tu dopiero zaczyna się zabawa...

Można zauważyć, że nigdy nie warto użyć dwóch krawędzi nie mających wspólnego wierzchołka. To pozostawia nam tylko dwa rodzaje podgrafów: gwiazdę (tylko krawędzie z jednego wierzchołka), i trójkąt.

Ale to dalej nietrywialne. Ja ostatecznie zrobiłem to zachłannie: jeśli chcemy pomniejszyć maksymalną odległość, to trzeba użyć jakiejś krawędzi z wierzchołka o największej odległości. Można też udowodnić, że najlepiej wybrać krawędź do wierzchołka o jak największej odległości po drugiej stronie.

Tak więc już wiemy, którą krawędź najlepiej użyć w każdym kroku, pozostaje to zrobić efektywnie, bo tych krawędzi jest dużo (wagi można potraktować jako wielokrotne krawędzie). Trzeba grupować te kroki w grupy symulowane na raz.

Mój kod ma kilka różnych przypadków, zależnie od tego jak układają się te odległości oraz które krawędzie są jeszcze dostępne. Każdy przypadek przekształca się w inny po użyciu odpowiednią liczbę razy cyklu krawędzi występującego w danym przypadku. Cała symulacja działa w czasie stałym.

Chyba można to zrobić prościej, bez rozważania przypadków. Wystarczy iść po jednym kroku i wykrywać automatycznie cykl w symulacji. A następnie sprawdzać, ile razy ten sam cykl się jeszcze powtórzy.

Przypadki k<5 sprowadzałem do k=5 (duplikując dane ciągi), bo ten jest najprostszy ;)

Warto jeszcze zauważyć, że dla k <= 3 odpowiedź to ceil((maksymalna odległość między dwoma ciągami)/2).

Dla k=2 startujemy z dowolnego ciągu i idziemy "w kierunku drugiego" (tzn. wykonujemy zmiany wartości w kolumnach, które nas oddalą o X od pierwszego, a przybliżą o X do drugiego). Oczywiście potrafimy oddalić się o tyle, ile chcemy. Mamy już jeden punkt.

Dla k=3 startujemy z ciągu najbardziej odległego od pozostałych i, podobnie jak poprzednio, idziemy "w kierunku" obu pozostałych (zmieniamy wartość w kolumnie o X, by oddalić się o X od tego najbardziej odległego, a przybliżyć o X do pozostałych). Nietrudno wykazać, że tak się da zrobić. No to mamy już trzy punkty. ;)

No, tylko że dla większych 'k' odpowiedź ta już nie musi być poprawna. :P

A czy ktoś robił tak, że sprowadzał problem do przypadku n <= k! (czy tam k!/2) wyżej opisaną metodą, a potem rozwiązywał go programowaniem liniowym z jakimś zaokrąglaniem wyniku (do liczb całkowitych)? Pytam, bo nie wiem, czy straciłem jakieś punkty na nienapisaniu tego ;)

Ja dokładnie tak robiłem :) I mam 6/10 przez TLE dla k=5.