Potyczki algorytmiczne

Na początku informacja, o co chodzi: http://www.konkurs.adb.pl

Wziąłem udział, zarejestrowałem się.
Na początku rozgrzewka, wybór języka i poznanie niuansów automatycznego testowania.
W naturalny sposób wybór padł na javę. Znam, używam na co dzień w pracy, co prawda w wersji 1.4, ale zawsze coś, pomyślałem, że nie będę miał większych problemów.
Runda próbna została rozwiązana metodą "brute force" - wynik i tak się nie liczył, chodziło głównie o sprawdzenie wydajności maszyny testującej - na co można sobie pozwolić.
Zadanie dosyć łatwe - o ile zastosowało się rozwiązanie najprostsze o poziomie komplikacji O(n^4).

Nadeszła runda pierwsza.
Dwa zadania, na początku wydawało się, że zadanie dla grupy B jest trudniejsze niż dla grupy A - co w zasadzie nie powinno nastąpić. Okazało się, że jednak zadanie dla grupy A było trudniejsze, ze względu na ilość danych.
Java poległa - ze względu na obowiązki zawodowo/domowe nie miałem czasu na testowanie różnych rozwiązań - zakodowałem to co wymyśliłem w pierwszym podejściu.
Metoda rekurencyjna... Dla małych ilości danych spisywała się "śpiewająco", ale dla średnich i dużych porażka. Pierwszy raz w życiu udało mi się zobaczyć komunikat "Heap overflow error". Zadanie B - podobnie rozwiązane "na kolanie", dzięki dobrym duszyczkom z forum miałem wystarczającą ilość danych do testowania.

Później zaczęły się schody...

Drugi etap zaskoczył mnie - miałem małe problemy ze zrozumieniem treści zadania dla grupy A, a zadanie dla grupy B przerosło mnie. Na dobrą sprawę nie były zbyt trudne - problemem okazał się poraz kolejny język i jego ograniczenia. Samo wczytanie danych do zadania A w wersji "maksymalnej" zabierało 50% limitu czasu...

Stwierdziłem, że spróbuję w przyszłym roku, uzbrojony w C/C++, kilka przeczytanych książek o algorytmach dotyczących grafów (Dijkstra, Bellman-Ford, itp.).