Delta mi!

Po przeczytaniu artykułu Marcina Pilipczuka trudno nie odnieść wrażenia, że nasz zasób wiedzy o zachowaniu ciągu EKG opiera się przede wszystkim na wynikach eksperymentów komputerowych, natomiast dowody otrzymanych w ten sposób hipotez pojawiają się z pewnym opóźnieniem.

Tym razem przyjrzymy się zadaniu Training z Międzynarodowej Olimpiady Informatycznej 2007.

W  Delcie 7/2009 Marek Cygan opisał pewien sposób radzenia sobie z tym, że dla niektórych trudnych problemów nie potrafimy znaleźć szybkiego algorytmu. Autor rozważał klasę problemów NP-trudnych – czyli takich, których prawdopodobnie nie można rozwiązać w czasie wielomianowym – i pokazywał, że dla wielu z nich można w efektywny sposób skonstruować nie dokładne, lecz przybliżone rozwiązanie.

W tym kąciku spróbujemy rozwiązać zadanie Electric needs pochodzące z drużynowych zawodów studenckich z serii ACM ICPC, a konkretnie z mistrzostw Ameryki Łacińskiej 2010.

W naszym zespole badawczym analizujemy wiele różnych zagadnień, które występują w różnych aspektach. Nic w tym dziwnego, wszak algorytmika jest bardzo szeroką dziedziną. Zdarza się i tak, że to samo zagadnienie pojawia się w wielu kontekstach. Taka sytuacja ma miejsce w przypadku problemu drzewa Steinera.

W sporcie stosowane są różne systemy prowadzenia rozgrywek. Jednym z nich jest tzw.  system pucharowy, w którym zwycięzca meczu kwalifikuje się do dalszych gier, przegrany zaś odpada z turnieju. Aby system był bardziej sprawiedliwy, dokonuje się początkowego rozstawienia przeciwników, tak by teoretycznie najsilniejsi spotkali się jak najpóźniej.

Tym razem zajmiemy się trochę innymi kwadratami niż zazwyczaj. Chodzi mianowicie o napisy postaci czyli sklejenie jakiegoś słowa (ciągu liter) z nim samym. Przykładowymi kwadratami występującymi w języku polskim są słowa mama, kankan, rowerowe, wałowało, esemesem.