spoj - konkurs pseudo matematyczny (uwaga, kod zadania)

Question

Witam, ostatnio jestem dość przybity bo nic mi nie wychodzi ze spoj'a ;( Uwierzcie, też mi nie jest przyjemnie zadawać to pytanie...

Oto link do zadania: http://pl.spoj.com/problems/MWPZ06H/

A to mój kod:

#include <iostream>
#include <vector>

auto sortedPoints(const std::vector<int> &points) {
	std::vector<int> toReturn;

	// ------------------------------------------- znalezienie jednego lub kilka maksymalnych wyników
	int maxCount{1}; 
	int max = points[0];

	for (int i = 1; i < points.size(); i++) { //wyznaczanie maksimum i jego ilości ( bo może być kilka maksymalnych wartości )
		if (points[i] > max) {
			max = points[i];
			maxCount = { 1 };
		}
		else if (points[i] == max) {
			++maxCount;
		}
	}

	for (int i = 0; i < maxCount; i++) { //zapisanie maksymalnych punktów na początek wektora 
		toReturn.push_back(max);
	}
	// ---------------------------------------- posortowanie rosnąco pozostałych wyników 

	std::vector<int> ntb; //ntb od "not_the_biggest"

	for (int i = 0; i < points.size(); i++) { //dodawanie do wektora pomocniczego elementów niebędących maksimum 
		if (points[i] != max)
			ntb.push_back(points[i]);
	}

	for (int i = 1; i < ntb.size(); i++) { //sortujemy je od najmniejszego do największego
		for (int j = 1; j < ntb.size(); j++) {
			if (ntb[i] < ntb[i - 1]) {
				int t = ntb[i];
				ntb[i] = ntb[i - 1];
				ntb[i - 1] = t;
			}
		}
	}

	for (int i = 0; i < ntb.size(); i++) { //dopisujemy do częściowo zapełnionego wektora z odpowiednią kolejności wyników 
		toReturn.push_back(ntb[i]);
	}

	// ----------------------------------------

	return toReturn;
}

int main(){
	int D;
	std::cin >> D;

	for (int i = 0; i < D; i++) {
		int N;
		std::cin >> N;

		std::vector<int> points(N);
		for (auto& i : points) {
			std::cin >> i;
		}
			
		auto res = sortedPoints(points);

		for (auto i : res) { //wypis wyników 
			std::cout << i << " ";
		}
		std::cout << "\n";
	}
}

Myślę że dość dokładnie opisałem tok mojego myślenia...

Dla wszystkich danych jakie były podane wydaje mi się że program udziela poprawnej odpowiedzi. Sprawdziłem to nawet na kompilatorze z jakiego spoj korzysta: https://ideone.com/bhHA6y

Jednak sędzia daje mi komunikat że błędna odpowiedź (wielka szkoda że nie podaje dla jakich danych wejściowych).

Testowałem to na różne sposoby i kilka razy czytałem od nowa treść zadania. Jednak dalej nic nie znalazłem.

Co pominąłem/nie dopilnowałem rozwiązując zadanie?

Będę bardzo wdzięczny za naprowadzenie mnie.

 

Comments

Do zadań ze SPOJa mamy specjalną kategorię - proszę tam umieszczać pytania. 

---

Jakoś zawsze to robię, teraz wyjątkowo zapomniałem ;) Dzięki za zwrócenie uwagi.

---

@Jakub 0,

Dzisiaj mam małe urwanie głowy, a w ręku tylko tablet. Jutro spróbuję się przyjrzeć. Na razie próbuj sam. Rób to etapami, sprawdzając kolejne moduły i funkcje. Przyczynę "awarii" trzeba bezwzględnie wyjaśnić!

Answer 1

Zadanie jest dość proste (odwrotnie do treści). Niepotrzebnie tak bardzo rozbudowałeś kod (wtedy trudniej go kontrolować, łatwiej o błędy).

Kiedy są już wczytane dane do kontenera, wystarczyło użyć standardowej funkcji sortowania: sort(vec.begin(), vec.end()), i we właściwej kolejności wypisać zawartość tablicy. (Do tego się to zadanie sprowadzało).

Comments

No nie do końca, bo trzeba znaleźć największe liczby, ustawić je na pierwsze miejsca i dopiero reszte posortować, można odrazu w odwrotnej kolejności a można normalnie a potem wypisać od tyłu

---

No nie do końca!

Przecież po operacji sortowania te największe liczby punktów znalazłyby się na końcu tablicy. Przy wypisywaniu wyników trzeba je było wyświetlić na początku - jako pierwsze, a następnie pozostałą zawartość tablicy. Ot i wszystko!

---

@Beginer

Dziękuje, to rzeczywiście pomogło. Tyle że nie mam zielonego pojęcia co źle było w moim algorytmie :/ , to mnie trochę martwi bo interesuje mnie nie tylko poprawnie działający program ale też sposób w jaki rozwiązywałem problem, masz jakiś pomysł co napisałem tam źle ?

Answer 2

Twój kod źle wypisuje wynik. Po każdej wczytanej partii danych on odrazu wypluwa wynik. Spróbowałbym najpierw wczytać wszystko a na koniec wypisywać wyniki. Można to zrobić np w ten sposób:
 

int main() {
	int D;
	std::cin >> D;
	std::vector<std::vector<int>> results;
	for (int i = 0; i < D; i++) {
		int N;
		std::cin >> N;

		std::vector<int> points(N);
		for (auto& i : points) {
			std::cin >> i;
		}
		results.push_back(sortedPoints(points));
	}
	for (std::vector<int> vector : results)
	{
		for (int number : vector)
			std::cout << number << " ";
		std::cout << std::endl;
	}
}

 

Comments

Dodatkowo ograniczyłbym stosowanie auto. Zaciemnia to troche kod. Czytam i nie wiem jakiego typu jest zmienna albo co funkcja zwraca. Ja akurat przykleiłem sobie to do Visuala to mi podpowiadał po najechaniu, ale mimo wszystko za dużo auto. Szczególnie w miejscach gdzie jest to totalnie ale to totalnie zbędne, np

for (auto i : res)

gdzie i to int. Taka sugestia - int jest krótsze niż auto :D. Rozumiem stosowanie auto jak przyjdzie napisać jakiś skomplikowany typ z zagnieżdzonymi template'ami np z STL'a, ale int? Szanujmy się :P

---

Dziękuje za odpowiedź, co do końcowego pokazywania ciągu wyników to nie w tym była rzecz (już wcześniej to próbowałem). Zwłaszcza że w treści zadania nic nie pisze że trzeba w odpowiedniej kolejności na strumieniu wyjścia wypisać wyniki... itd...

Pisało tylko o tym że rozwiązanie należy napisać w osobnej linii ;)

Jednak skorzystam z rady by nie używać tak dużo słowa auto. Jednak co do stosowania go w pętli zakresowej to robię to z przyzwyczajenia, tak jak czasami w for int i=0...  Jakoś w pętlach zakresowych nigdy nie zastanawiam się nad typem danych i czy jest to kontener czy zmienna int to jakoś daje zawsze auto. Ale to fakt że może być to nieczytelne...

---

Ok w pętlach, bardzo nie ok w deklaracjach funkcji.

---

tzn. to że funkcja zwraca auto? Jeśli tak to przez lenistwo ;) Ale fakt że po czasie bym sam nie widział co ta funkcja w końcu zwraca.

---

Tak. Chodzi o czytelność kodu. Może Cię to na razie nie obchodzić, ale jak będziesz kiedyś musiał przeczytać czyjś brzydki kod to zrozumiesz, że to bardzo ważne. Nawet jeśli za rok przeczytasz swój własny brzydki kod i go nie zrozumiesz. Jedną z takich podstawowych zasad czytelnego kodu są deskryptywne nazwy i sensowne sygnatury funkcji. Chodzi o to, żebyś po zobaczeniu sygnatury funkcji i jej nazwy nie musiał patrzeć do środka, żeby wiedzieć co ona robi. Jest to tzw samodokumentujący się kod, czyli taki, który nie potrzebuje komentarzy bo wszystko jest jasne z samych nazw. I w tym kontekscie auto jest strasznym złem. Porównaj sobie takie dwie funkcje:
bool doesHeaderMatchesPattern(Header header, Pattern pattern);
auto fun(int x, String s, String s2);
W pierwszym przypadku nie musisz patrzyć do środka, bo widzisz, że funkcja zwraca bool i po typach i nazwach argumentow odrazu widać co ona robi.
Za to druga funkcja wymaga prześledzenia całego ciała: znalezienia użyć argumentów, żeby domyślić się czym one są i wytropienia returna, żeby sprawdzić co ona zwraca. A jak kod ma miliony linijek i czyta go dużo osób to jest to straszne marnotrawstwo czasu.

---

kod ma miliony linijek

Bez przesady ;)

---

Ja tam słyszałem o kilkunastu milionach linijek kodu do przetestowania w branży telekomunikacyjnej po jakichś poważnych awariach :P

Ale racja przesadziłem. Wystarczy kilkaset moze tysiąc linijek, żeby dostać raka od analizowania brzydkiego kodu :P

---

Chyba w Nokii.

Answer 3

Pomyliłeś się tylko w funkcji sortowania. Napisałem nową - linijki: 33 - 42. Teraz powinno być wszystko dobrze.

#include <iostream>
#include <vector>

auto sortedPoints(const std::vector<int> &points) {
    std::vector<int> toReturn;

    // ------------------------------------------- znalezienie jednego lub kilka maksymalnych wyników
    int maxCount{1};
    int max = points[0];

    for (int i = 1; i < points.size(); i++) { //wyznaczanie maksimum i jego ilości ( bo może być kilka maksymalnych wartości )
        if (points[i] > max) {
            max = points[i];
            maxCount = { 1 };
        }
        else if (points[i] == max) {
            ++maxCount;
        }
    }

    for (int i = 0; i < maxCount; i++) { //zapisanie maksymalnych punktów na początek wektora
        toReturn.push_back(max);
    }
    // ---------------------------------------- posortowanie rosnąco pozostałych wyników

    std::vector<int> ntb; //ntb od "not_the_biggest"

    for (int i = 0; i < points.size(); i++) { //dodawanie do wektora pomocniczego elementów niebędących maksimum
        if (points[i] != max)
            ntb.push_back(points[i]);
    }

    int t;
    for (int i = 0; i < ntb.size(); i++) {  //sortujemy je od najmniejszego do największego
        for (int j = 1 + i; j < ntb.size(); j++) {
            if (ntb[j] < ntb[i]) {
                t = ntb[j];
                ntb[j] = ntb[i];
                ntb[i] = t;
            }
        }
    }

    for (int i = 0; i < ntb.size(); i++) { //dopisujemy do częściowo zapełnionego wektora z odpowiednią kolejności wyników
        toReturn.push_back(ntb[i]);
    }

    // ----------------------------------------

    return toReturn;
}

int main(){
    int D;
    std::cin >> D;

    for (int i = 0; i < D; i++) {
        int N;
        std::cin >> N;

        std::vector<int> points(N);
        for (auto& i : points) {
            std::cin >> i;
        }

        auto res = sortedPoints(points);

        for (auto i : res) { //wypis wyników
            std::cout << i << " ";
        }
        std::cout << "\n";
    }
}

 

Comments

Dziękuje, ta wersja bubble sort:

int t;
    for (int i = 0; i < ntb.size(); i++) {  //sortujemy je od najmniejszego do największego
        for (int j = 1 + i; j < ntb.size(); j++) {
            if (ntb[j] < ntb[i]) {
                t = ntb[j];
                ntb[j] = ntb[i];
                ntb[i] = t;
            }
        }
    }

jest z pewnością dużo lepiej pomyślana i bardziej wydajna od mojej. Gdzie jednak ja konkretnie zrobiłem błąd? Raczej dla wszystkich wypadków poprzednia wersja też działała ok.

---

Nie, Jakubie. To nie o to chodzi, że poprawiona funkcja sortowania jest lepiej pomyślana. Twoja była napisana źle.

1. Zauważ, że funkcja sortowania wymaga podwójnej pętli for, i tym samym dwóch iteratorów. W Twojej wersji, w ciele funkcji używasz tylko jednego iteratora ( i ). A gdzie drugi ( j ) ?   Po co więc podwójna pętla, skoro zmienia się tylko jeden iterator?  Bez sensu!

2. Tylko przypadek sprawił (korzystny zestaw liczb), że przy złej funkcji sortowania program wyświetlił dobre wyniki dla przykładowych danych podanych w zadaniu. Ale wykonaj liczenie np. dla takiego zestawu:

7    // liczba uczestników

1  2  7  4  4  7  1    //punktacja

Zobacz, czy przy złej funkcji sortowania program wyświetli dobry rezultat.