Potyczki Algorytmiczne 2011: Zadanie próbne „Tulipany”.

Przeglądając różne informacje w Internecie trafiłem na stronę skierowanego w stronę programistów konkursu „Potyczki Algorytmiczne”, edycja 2011. Jednym z organizatorów jest wydział Matematyki, Informatyki i Mechaniki Uniwersytetu Warszawskiego [MIMUW], co gwarantuje dobry poziom zawodów.  Jako, że lubię czasem sprawdzić swoje umiejętności programistyczne, zarejestrowałem się w serwisie. Zapraszam do lektury krótkiego komentarza i analizy rozwiązania pierwszego, testowego zadania. Uwaga – zawiera spoiler! ;]

Zadanie próbne „Tulipany”.

Uwaga: Czytelników Planety PHP proszę o wybaczenie – nie jest on w żaden sposób związany z tematyką tworzenia stron internetowych, aczkolwiek pozwoliłem sobie otagować go jako „internet”, żeby zainteresowani także mogli się z nim zapoznać. Kolejne wpisy o tym konkursie nie będą zawierały już problematycznych tagów – chyba, że będzie duży odzew poparcia, wtedy rozważę taką możliwość. ;]

Pierwsze zadanie w konkursie nosi tytuł „Tulipany”. Jego treść można ściągnąć jako plik PDF tutaj. Ze względu na to, że nie jest długa, pozwolę sobie ją przytoczyć:

Na świecie znanych jest 15 tysięcy odmian tulipanów (tak naprawdę ta liczba jest pewnym przybliżeniem, ale dla uproszczenia założymy, że jest ich dokładnie tyle). Bajtazar przez wiele lat tworzył swój prywatny spis tulipanów, w którym każdej z odmian tych wspaniałych kwiatów przyporządkował numer katalogowy między 1 a 15 000.

Niedawno katalogiem Bajtazara zainteresowała się dyrekcja bajtockiego ogrodu botanicznego. W ogrodzie tym rośnie mnóstwo przeróżnych tulipanów. Kierownictwo uznało jednak, że gdyby udało im się zebrać wszystkie znane odmiany tulipanów, to na pewno stanowiłoby to świetną reklamę ich placówki. Dlatego poproszono Bajtazara o sprawdzenie, ilu odmian tulipanów brakuje w ogrodzie.

Bajtazar zidentyfikował już odmiany tulipanów rosnących w kolejnych grządkach ogrodu, jednak wyznaczenie liczby brakujących odmian sprawiło mu pewien problem. Czy pomógłbyś mu w tym?

Dane wejściowe:

W pierwszy wierszu standardowego wejścia znajduje się jedna liczba całkowita n (1 <= n <= 20 000), oznaczająca liczbę grządek tulipanów w ogrodzie. Wdrugim wierszu znajduje się n liczb całkowitych z przedziału [1, 15 000], oznaczających odmiany tulipanów rosnących w poszczególnych grządkach ogrodu.

Wyjście:

Twój program powinien wypisać na standardowe wyjście jeden wiersz zawierający jedną liczbę całkowitą,
oznaczającą liczbę odmian tulipanów, które ogród musi jeszcze dokupić, aby móc się poszczycić kolekcją
wszystkich znanych odmian tulipanów.

Przykład:

Dla danych wejściowych:
8
3 6 2 2 4 6 3 7
poprawnym wynikiem jest:
14995

Rozwiązanie:

Zadanie sprowadza się do wyznaczenia ilości unikalnych gatunków tulipanów zasadzonych we wszystkich podanych w danych wejściowych grządkach. W PHP moglibyśmy sobie pomóc funkcją array_unique(), tutaj trzeba było chwilę pogłówkować.

Mój trywialny algorytm polegał na tym, żeby kolejne liczby konwertować na typ int [można było zastosować unsigned int - założenia zadania], a następnie sprawdzać wszystkie już wczytane wartości w poszukiwaniu duplikatu. Na początku zgodnie z treścią zakładałem że maksymalna ilość unikatów jest równa 15000. Każdy kolejny znaleziony unikat zmniejszał tą wartość.

Ze względu na to, że informację o konkursie znalazłem nieco po godzinie 17, a termin oddania zadania był ustawiony sztywno na godzinę 18, szybko włączyłem Eclipse i nie zważając na to, że piszę kod C++ w IDE do PHP naskrobałem coś takiego [main.cpp]:

#include <cstdlib>
#include <cstdio>

int main(int argc, char **argv)
	{
	int rows = 0;
	scanf("%i", &rows);
	int result = 15000;
	bool unique = false;
	int *nums = (int *)calloc(rows, sizeof(int));
	for(int i = 0; i < rows; i++)
		{
		scanf("%i", &nums[i]);
		unique = true;
		for(int j = 0; j < i; j++)
			{
			if(nums[j] == nums[i])
				{
				unique = false;
				}
			}
		if(true == unique)
			{
			result--;
			}
		}
	printf("%i", result);
	return 0;
	}

Plik z danymi testowymi wyglądał następująco [data.txt]:

8
3 6 2 2 4 6 3 7

Polecenie kompilujące i uruchamiające program z danymi testowymi:

g++ -O2 -static main.cpp -lm | ./a.exe < data.txt

Na początku źle zrozumiałem sformułowanie mówiące, że dane pojawią się na standardowym wejściu i zacząłem je czytać z parametrów wywołania [tablica argv]. Nie muszę mówić, że szybki segfault w automatycznym sprawdzeniu naprawił mój błąd myślowy i pozwolił na oddanie powyższego listingu.

W tym momencie widzę już jeden „karygodny” błąd – nie umieściłem w kodzie instrukcji break po znalezieniu duplikatu [linia 19] – myślę, że zmniejszyłoby to istotnie ilość porównań. Z drugiej strony najbardziej wymagające testy wykonały się na maszynie konkursowej w <0,1s dla limitu 1s, i <0,4s dla limitu 4s, także nie jest tragicznie. Dawno już nic nie robiłem w językach C / C++, także dobrze będzie odświeżyć sobie trochę informacji z tej dziedziny.

Oczywiście rzeczony program, nawet z powyższą poprawką nie jest optymalny – na pewno możnaby było w nim wiele rzeczy usprawnić, np. zamiast sprawdzać całą tablicę do indeksu zrobić mapę istniejących wartości i z nich odczytywać odpowiednią pozycję. Można to osiągnąć prosto stosując kontener STL std::map, który gwarantuje odczyt w O(log n). Oszczędzilibyśmy wtedy też nieco pamięci, ponieważ w najgorszym przypadku program zaalokuje 20.000 4 bajtowych intów, a więc 80kB pamięci.

Zachęcam do rejestracji w konkursie i rozwiązywania kolejnych zadań. Pierwsze, „prawdziwe” zadanie pojawi się już jutro. Oczywiście proszę także o komentarze do mojego rozwiązania, oraz przesyłania własnych. W końcu i tak celem jest to, żebyśmy byli coraz lepszymi programistami, prawda?

Warto przeczytać.