[PJWSTK] ASD – Projekt 1 – Rozwiązanie

Pierwszy projekt z ASD:

Rozważmy zbiór P={p(0), p(1), …, p(n-1)} składający się z n społeczności lokalnych, dla których ustalona jest relacja bezpośredniego sąsiedztwa. Ze zbioru P wybieramy k róznych elementów, które będą stanowiły punkty startowe kampanii wyborczych k kandydatów q(0), q(1), …, q(k-1). Dalej proces realizacji kampanii wyborczych przebiega w turach tak, że:

  • tura 0: każdy z kandydatów q(j) dla 0<=j<=k-1 zakłada w punkcie startowym swojej kampanii sztab wyborczy,
  • tura i, kork I: każdy z kandydatów z każdego sztabu wyborczego zlokalizowanego w dowolnej społecznosci p(j)dla 0<=j<=n-1, odwiedza wszystkie społeczności bezpośrednio sąsiednie z w/w elementem zbioru P, gdzie zakłada swoje komitety wyborcze, pod warunkiem, że nie ma w nich już własnych sztabów wyborczych, bądź sztabów wyborczych innych kandydatów,
  • tura i, krok II: w każdej społeczności p(j) dla 0<=j<=n-1, dla której założony jest komitet wyborczy co najmniej jednego kandydata odbywają się prawybory, w których zwycięża ten kandydat, którego liczba sztabów wyborczych w społecznościach bezpośrednio sąsiednich (stan z początku i-tej tury) ze społecznością p(j) jest:
    • wariant A: najmniejsza (w przypadku remisu wygrywa kandydat o większej wartości indeksu l dla q(l)),
    • wariant B: największa (w przypadku remisu wygrywa kandydat o mniejszej wartości indeksu l dla q(l)).
  • tura i, kork III: zwycięstow w prawyborach w danej społeczności uprawnia kandydata do założenia sztabu wyborczego w miejsce komitetu wyborczego,

i kończy się z chwilą, gdy wszystkie społeczności lokalne należące do zbioru P mają ustalone sztaby wyborcze kandydatów.

Ustal finansowanie kosztów kampanii wyborczej, w zależności od przyjętego wariantu rozstrzygania prawyborów (wariant A albo wariant B), dla każdego z k kandydatów, jeżeli koszty kampanii wyborczej mierzymy ostateczną liczbą założonych sztabów wyborczych w obrębie rozważanego zbioru społeczności lokalnych P.

Wejście

Kolejno:

  • liczba naturalna dodatnia definiujaca liczbę 1<=n<=10^4 społeczności lokalnych, znak nowego wiersza/linii (ASCII kod 10),
  • ciąg 0<=m<=10^6 wierszy postaci liczba naturalna x znak odstępu/spacjii (ASCII kod 32) liczba naturalna y znak nowego wiersza/linii (ASCII kod 10) zakończony wierszem specjalnym postaci -1 znak odstępu/spacjii (ASCII kod 32) -1 znak nowego wiersza/linii (ASCII kod 10), z których każdy właściwy wiersz reprezentuje bezpośrednie sąsiedztwo społeczności lokalnych indeksowanych kolejno liczbami x i y,
  • liczba naturalna dodatnia definiujaca liczbę 1<=k<=10^4 i k<=n kandydatów, znak nowego wiersza/linii (ASCII kod 10),
  • ciąg k wierszy postaci liczba naturalna z znak nowego wiersza/linii (ASCII kod 10), gdzie liczba z zawarta w i-tym wierszu reprezentuje indeks punktu startowego (społeczności lokalnej) każdego kolejnego kandydata począwszy od kandydata q(0).

Wyjście

Ciąg k wierszy postaci liczba naturalna a znak odstępu/spacjii (ASCII kod 32) liczba naturalna b znak nowego wiersza/linii (ASCII kod 10), z których każdy reprezentuje kolejno koszt kampanii wyborczej w wariancie A (wartość a) i w wariancie B (wartość b) każdego kolejnego kandydata począwszy od kandydata q(0).

Złożoności i limity

Złożoność czasowa O((n^2)k), złożoność pamięciowa O(n+m+k), gdzie n jest liczbą społeczności lokalnych, m jest rozmiarem relacji sąsiedztwa na zbiorze P, a k jest liczbą kandydatów. Fizyczny limit pamięci ograniczony przez 10 MB.

Przykład 1

Wejście:
3
0 1
1 2
0 2
-1 -1
2
0
1

Wyjście:
1 2
2 1

Przykład 2

Wejście:
6
1 0
2 1
3 0
3 1
3 2
4 2
4 3
5 0
5 2
-1 -1
3
0
1
5

Wyjście:
1 3
2 2
3 1

Rozwiązanie w C++:

#include<stdio.h>

class Town;
class Thief;

class ListElementTown
{
    public:
		Town* town;
		ListElementTown* next;

		ListElementTown(Town* m)
		{
			this->town = m;
			this->next = NULL;
		}

		ListElementTown(Town* m, ListElementTown* next)
		{
			this->town = m;
			this->next = next;
		}
};

class ListTowns
{
	public:
		ListElementTown* first;
		int elementsCounter;

		ListTowns()
		{
			first = NULL;
			elementsCounter = 0;
		}

		Town* get(int elementIterator)
		{
			ListElementTown* tmp = first;
			for(int i = 0; i < elementIterator; i++)
				tmp = tmp->next;

			return tmp->town;
		}

		void add(Town* m)
		{
			if(this->first == NULL)
				this->first = new ListElementTown(m);
			else
				first = new ListElementTown(m, first);

			elementsCounter++;
		}

		bool contains(Town* m)
		{
			ListElementTown* tmp = first;
			while(tmp)
			{
				if(m == tmp->town)
					return true;

				tmp = tmp->next;
			}
			return false;
		}

		void clear()
		{
			first = NULL;
			elementsCounter = 0;
		}
};

class ListElementThief
{
	public:
		Thief* thief;
		ListElementThief* next;

		ListElementThief(Thief* t)
		{
			this->thief = t;
			this->next = NULL;
		}

		ListElementThief(Thief* t, ListElementThief* next)
		{
			this->thief = t;
			this->next = next;
		}
};

class ListThiefs
{
	public:
		ListElementThief* first;
		int elementsCounter;

		ListThiefs()
		{
			first = NULL;
			elementsCounter = 0;
		}

		Thief* get(int elementIterator)
		{
			ListElementThief* tmp = first;
			for(int i = 0; i < elementIterator; i++)
				tmp = tmp->next;

			return tmp->thief;
		}

		void add(Thief* t)
		{
			if(this->first == NULL)
				this->first = new ListElementThief(t);
			else
			{
				first = new ListElementThief(t, first);
			}
			elementsCounter++;
		}

		bool contains(Thief* t)
		{
			ListElementThief* tmp = first;
			while(tmp)
			{
				if(t == tmp->thief)
					return true;

				tmp = tmp->next;
			}
			return false;
		}

		void clear()
		{
			first = NULL;
			elementsCounter = 0;
		}
};
class Town
{
	public:
		bool koniec;
		int id;
		Thief* electionStaffA;
		Thief* electionStaffB;
		Thief* tmpWinnerA;
		Thief* tmpWinnerB;
		ListThiefs* candidatesA;
		ListThiefs* candidatesB;
		ListTowns* neighbors;

		Town(int i)
		{
			koniec = false;
			id = i;
			electionStaffA = NULL;
			electionStaffB = NULL;
			tmpWinnerA = NULL;
			tmpWinnerB = NULL;
			candidatesA = new ListThiefs();
			candidatesB = new ListThiefs();
			neighbors = new ListTowns();
		}
};

class Thief
{
	public:
		int id;
		int tmpCounterA;
		int tmpCounterB;
		int campaignCostA;
		int campaignCostB;

		Thief(int indeks)
		{
			this->id = indeks;
			this->tmpCounterA = 0;
			this->tmpCounterB = 0;
			this->campaignCostA = 0;
			this->campaignCostB = 0;
		}
};

int main()
{ 
	int workingElectionStaffCounterA = 0;
	int workingElectionStaffCounterB = 0;
	int liczba_miast = 0;
	int liczba_kandydatow = 0;
	fscanf(stdin, "%d", &liczba_miast);
	Town* towns[liczba_miast];
	for(int i = 0; i < liczba_miast; i++)
	{
		towns[i] = new Town(i);
	}
	int towna;
	int townb;
	fscanf(stdin, "%d", &towna);
	fscanf(stdin, "%d", &townb);
	while(towna != -1 && townb != -1)
	{
		towns[towna]->neighbors->add(towns[townb]);
		towns[townb]->neighbors->add(towns[towna]);
		fscanf(stdin, "%d", &towna);
		fscanf(stdin, "%d", &townb);
	}
	fscanf(stdin, "%d", &liczba_kandydatow);
	Thief* candidates[liczba_kandydatow];
	for(int i = 0; i < liczba_kandydatow; i++)
	{
		candidates[i] = new Thief(i);
	}
	int sztab;
	for(int i = 0; i < liczba_kandydatow; i++)
	{
		fscanf(stdin, "%d", &sztab);
		towns[sztab]->electionStaffA = candidates[i];
		candidates[i]->campaignCostA++;
		workingElectionStaffCounterA++;
		towns[sztab]->electionStaffB = candidates[i];
		candidates[i]->campaignCostB++;
		workingElectionStaffCounterB++;
	}
	ListTowns* modifiedTowns = new ListTowns();
	while(workingElectionStaffCounterA != liczba_miast && workingElectionStaffCounterB != liczba_miast)
	{
		modifiedTowns->clear();
		for(int i = 0; i < liczba_miast; i++)
		{
			if(towns[i]->electionStaffA != NULL && towns[i]->electionStaffB != NULL)
			{
				for(int i2 = 0; i2 < towns[i]->neighbors->elementsCounter; i2++)
				{
					if(towns[i]->neighbors->get(i2)->electionStaffA == NULL && towns[i]->neighbors->get(i2)->electionStaffB == NULL)
					{
						if(!(towns[i]->neighbors->get(i2)->candidatesA->contains(towns[i]->electionStaffA)))
						{
							towns[i]->neighbors->get(i2)->candidatesA->add(towns[i]->electionStaffA);
						}
						if(!(towns[i]->neighbors->get(i2)->candidatesB->contains(towns[i]->electionStaffB)))
						{
							towns[i]->neighbors->get(i2)->candidatesB->add(towns[i]->electionStaffB);
						}
						if(!(modifiedTowns->contains(towns[i]->neighbors->get(i2))))
						{
							modifiedTowns->add(towns[i]->neighbors->get(i2));
						}
					}
				}
			}
		}
		ListElementTown* startElement = modifiedTowns->first;
		int loopsCounter = modifiedTowns->elementsCounter;
		for(int i = 0; i < loopsCounter; i++)
		{
			Town* currentTown = startElement->town;
			Thief* tmpCandidate = NULL;
			for(int x = 0; x < liczba_kandydatow; x++)
			{
				candidates[x]->tmpCounterA = 0;
				candidates[x]->tmpCounterB = 0;
			}
			int loopsCounter_2 = currentTown->neighbors->elementsCounter;
			ListElementTown* neighborsLoop = currentTown->neighbors->first;
			for(int ii = 0; ii < loopsCounter_2; ii++)
			{
				Town* tmpTown = neighborsLoop->town;
				if(tmpTown->electionStaffA != NULL)
				{
					tmpTown->electionStaffA->tmpCounterA++;
					tmpTown->electionStaffB->tmpCounterB++;
				}
				neighborsLoop = neighborsLoop->next;
			}
			Thief* winnerA = currentTown->candidatesA->get(0);
			Thief* winnerB = currentTown->candidatesB->get(0);

			loopsCounter_2 = currentTown->candidatesA->elementsCounter;
			for(int i2 = 1; i2 < loopsCounter_2; i2++)
			{
				tmpCandidate = currentTown->candidatesA->get(i2);
				if((winnerA->tmpCounterA > tmpCandidate->tmpCounterA) || (winnerA->tmpCounterA == tmpCandidate->tmpCounterA && winnerA->id < tmpCandidate->id))
					winnerA = tmpCandidate;
			}
			currentTown->tmpWinnerA = winnerA;
			currentTown->candidatesA->clear();
			loopsCounter_2 = currentTown->candidatesB->elementsCounter;
			for(int i2 = 1; i2 < loopsCounter_2; i2++)
			{
				tmpCandidate = currentTown->candidatesB->get(i2);
				if((winnerB->tmpCounterB < tmpCandidate->tmpCounterB) || (winnerB->tmpCounterB == tmpCandidate->tmpCounterB && winnerB->id > tmpCandidate->id))
					winnerB = tmpCandidate;
			}
			currentTown->tmpWinnerB = winnerB;
			currentTown->candidatesB->clear();
			startElement = startElement->next;
		}
		startElement = modifiedTowns->first;
		loopsCounter = modifiedTowns->elementsCounter;
		for(int i = 0; i < loopsCounter; i++)
		{
			Town* tmpTown = startElement->town;
			tmpTown->electionStaffA = tmpTown->tmpWinnerA;
			tmpTown->electionStaffB = tmpTown->tmpWinnerB;
			tmpTown->electionStaffA->campaignCostA++;
			tmpTown->electionStaffB->campaignCostB++;
			workingElectionStaffCounterA++;
			workingElectionStaffCounterB++;
			startElement = startElement->next;
		}
	}
	for(int i = 0; i < liczba_kandydatow; i++)
	{
		fprintf(stdout, "%d %d\n",candidates[i]->campaignCostA,candidates[i]->campaignCostB);
	}
	return 0;
}
Ten wpis został opublikowany w kategorii PJWSTK, PJWSTK - ASD. Dodaj zakładkę do bezpośredniego odnośnika.

7 odpowiedzi na „[PJWSTK] ASD – Projekt 1 – Rozwiązanie

  1. Mariusz pisze:

    Czy może Pan napisać w kilku słowach jaka jest idea tego rozwiązania?

  2. Jerzy Skalski pisze:

    Spróbuję to jutro rano opisać dokładniej w nowym poście. Kod też trochę przeczyszczę, bo aktualnie zostały fragmenty z wersji ‚anty-plagiatowej’ które nie mają sensu pod względem wydajności.

  3. Pingback: [PJWSTK] ASD – wiosna 2015 – Zadanie 5 – Rozwiązanie | Wszystko czego potrzebują studenci

  4. Hapi pisze:

    Witam. Jeśli wychodzi 25pkt/100 i połowa wyników to przekroczony limit czasu. Zamiast pętli for mam while, zrobiłem szybsze wczytywanie intów. Algorytm daje dobre wyniki. Gdzie może być błąd?

    • Jerzy Skalski pisze:

      Polecam sprawdzić czas poszczególnych części algorytmu. Wywalać jakąś, dać jakiś wynik w poprawnym formacie np. „1 2(nowa linia)2 1” (inaczej czas wykonania się nie pokaże). Odpalić na spox np. program który tylko wczyta dane i wyświetli błędny wynik. W ten sposób można dodawać po kolejnym elemencie algorytmu i zobaczyć na którym tak bardzo zwalnia. Jak chcesz to mogę Ci dzisiaj wieczorem sprawdzić kod. Mój skype: phoowned@wp.pl

      • Hapi pisze:

        Witam, w sumie kod sprawdzałem Pana, tylko zmieniłem wstawianie intów na szybsze 🙂 Dodawałem po kolei elementy algorytmu, zeby sprawdzić gdzie przekracza limit i tak mi się wydaje że w 2 pętli, coś tam się nie zgrywa chyba od 262 linijki. Ale ciężko to zidentyfikować, bo dość rozbudowane są te pętle

Dodaj komentarz

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *