Dzisiejszy konkurs z programowania C++ - Zadanie jakie dostaliśmy

Question

Witam. Brałem dzisiaj udział w konkursie z programowania w języku C++. Chciałem się z Wami podzielić zadaniami, może kogoś interesuje co dostaje przeciętny uczeń technikum/liceum. 

Wyłożyłem się na zadaniu pierwszym za 25 punktów. Napisałem tylko wczytywanie danych z klawiatury do tablicy char opartej na wektorach (tak, musiałem się popisać ich znajomością, zawsze coś na plus ). Zadanie drugie, oraz trzecie były dla mnie dosyć dobrze zrozumiałe i poradziłem sobie bez większych problemów. Jeżeli ktoś z was, znalazłby kilka minut w ciągu dnia i zrobił zadanie pierwsze, którego nijak nie rozumiem, to byłbym wdzięczny. Pozdrawiam serdecznie :) 

Answer 1

Całkiem inteligentne zadanie. Uprościłem nieco wczytując typ string, ale można to łatwo zmienić, liczy się sposób działania funkcji.

using namespace std;

void maxSequence(string a, string b)
{
	string max = "";
	string curr = "";
	for (int i = 0; i < a.size(); i++)
	{
		for (int j = 0; j < b.size(); j++)
		{
			if (a[i] == b[j]) 
			{
				curr += a[i];
				if (i + 1 < a.size())
					i++;
				else
					break;
			}
		}
		if (curr.size() > max.size())
		{
			max = curr;
			curr = "";
		}
	}
	cout << max.size() << endl << max << endl;
}

 

Comments

To nie jest prawidłowy algorytm. Zaimplementuj to do przykładu który podałem na spoju i się przekonasz.

Wczytaj słowa "deskorolka" oraz "stokrotka" i sprawdź co dostaniesz na wyjściu. Twój algorytm daje podciąg 3 znaków "oko" A powinno być 
deskorolka 
--sk-ro-ka 

stokrotka 
s--kro-ka

 

Answer 2

Ogólnie to dość znany problem w informatyce, który nosi nazwę LCS (Longest Common Subsequence) i możesz o nim sporo poczytać / pooglądać jeśli będziesz szukał pod tą nazwą. Oczekiwane, najefektywniejsze rozwiązanie stosuje programowanie dynamiczne, które daje całkiem niezłą złożoność O(n * m). Gdzie n i m to długości wczytanych ciągów.

 

Pozdrawiam,

Comments

O dzięki, z pewnością coś o tym poczytam :)

Answer 3

Niedawno to robiłem na SPOJu niemal identyczne http://pl.spoj.com/problems/LENLCS/

Powiem tak. Na sucho bez znajomości algorytmu LCS nikt tego nie rozwiąże w ciągu godziny.

Tutaj jest ładnie wyjaśnione na przykładzie jak to się liczy. http://informatyka.wroc.pl/node/627?page=0,5

Inna sprawa że startując w konkursach programistycznych trzeba być przygotowanym na różne takie algorytmy.

Answer 4

Zadanie dość skomplikowane, ale sądzę, że niezłym sposobem jest ciągłe wyznaczanie podciągów jednego ciągu (zaczynając od największego) i równoczesne sprawdzanie, czy istnieje takowy w drugim ciągu.

Czyli usuwasz najpierw jedną literę i sprawdzasz, potem drugą i sprawdzasz, trzecią i sprawdzasz... później dwie naraz i sprawdzasz... aż nie dojdziemy do momentu, gdy znajdziemy wspólny podciąg lub aż zlikwidujemy wszystkie znaki w ciągu.

Oczywiście podciągi będą mogły się powtarzać, ale nie jest to ważne w odniesieniu do tego zadania.

A tak z ciekawości - ile trwał ten konkurs?

Comments

Na wszystko mieliśmy 1,5 godziny, lub dwie. Sam nie wiem, w ogniu walki z kodem całkiem wyleciało mi to z głowy :)

Answer 5

Zadania nie są wcale jakieś tragiczne, wystarczy trochę pomyśleć, ale nie wątpię że w "ogniu walki" można nie wpaść na coś takiego :)

Polecam natomiasto obejrzeć zadania z olimpiady informatycznej, właśnie dla szkół średnich:

http://www.oi.edu.pl/static/attachment/20160524/blue_1.pdf

Tam to jest masakra czasami

Comments

Oczywiście, nigdzie nie pisałem że są tragiczne. Niemniej jednak nigdy w szkole nie miałem najmniejszej styczności z C++, a jedyna co potrafię to to z filmów Pana Mirosława, oraz z tego co wyczytam tutaj - czytając komentarze :)

 

EDIT: No, jeszcze przerobiłem kawałek książki, ale wiele nowego z tego nie wyniosłem.

---

Przerabianie niebieskiej książeczki bez dobrej znajomości C++ i algorytmiki to masochizm, który na dodatek nie przynosi zbyt wielu korzyści. Znacznie lepiej jest próbować robić zadanie ze SPOJa/MAINa, a dopiero potem zabrać się za zadania z OIa itp.

Answer 6

bardzo podobne do tego pierwszego zadania widziałem na spoju.

Comments

#Złote #Galoty #Za #Odkop

---

dzięki, tyle, że to nie ja odkopałem, przewiń wyżej ;p