Tablica haszująca i powtarzające się wartości

Witam,
mam takie zadanie:

Dany jest wielomian W(x). Należy obliczyć wszystkie wartości wielomianu W dla argumentów 0, 1, 2, ..., 9998, 9999 i stwierdzić, które wartości się powtarzają. Wartości wielomianu należy obliczać modulo 229.

No i oto moja próba rozwiązania tego, ale niezbyt skuteczna...

 
#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int hash_me(int polynomial_value);
 
int main()
{
        int polynomial_grade = 0;
 
        cin >> polynomial_grade;
        polynomial_grade++;
        int grade = polynomial_grade;
 
        int *coefficients = new int [polynomial_grade];
        while(polynomial_grade--)
        {
                cin >> coefficients[polynomial_grade];
        }
 
        vector<int>poly_values[953];
        vector<int>poly_repeats;
        int total_value;
        int repeats = 0;
 
        for(int x = 0; x < 10000; x++)
        {
                total_value = coefficients[0];
 
                for(int i = 1 ; i < grade ; i++)
                        total_value += coefficients[i] * x; //obliczanie wartosci wielomianu
 
                total_value = total_value % 536870912; //modulo 2^(29)
                int hash_key = hash_me(total_value); //biore hash
                poly_values[hash_key].push_back(total_value); //pod tym hashem zapisuje wartosc
 
        }
 
        for(int i = 0; i < 953; i++) //sprawdzam wszystkie vectory
        {
                sort(poly_values[i].begin() , poly_values[i].end()); //sortuje
                for(int y = 0; y < poly_values[i].size() - 1; y++) //sprawdzam pokolei
                {
                        if(poly_values[i][y] == poly_values[i][y + 1]) //jezeli znalazlem dwa takei same elementy
                        {
                                poly_repeats.push_back(poly_values[i][y]); //wrzuc do vectora powtorek
                                repeats++; //dodaj powtorke
                        }
                }
        }
 
        cout << repeats << endl;
        for(int i = 0; i < poly_repeats.size(); i++)
        {
                cout << poly_repeats[i] << endl;
        }
        return 0;
}
 
int hash_me(int polynomial_value)
{
        return (polynomial_value % 13469) % 953;
}

Ogólnie to czuję, że to słaby pomysł... (nie działa) Może ktoś mnie pokierować w dobrą stronę?

1. Po co ci tablica hashująca? To jest przydatne tyko, gdy chcesz porównać tylko duże obiekty, których standardowe porównanie jest kosztowne (np napisy), a ty masz prosty obiekt liczbowy, którego porównanie prawie nic nie kosztuje.
2. wpakowałeś wszystko w main! To się źle czyta, źle analizuje i poprawia. Podziel to na funkcje: wczytanieWielomianu, obliczWielomian.
3. WTF: vector<int>poly_values[953];
   Pomieszałeś wektor STL ze zwykłą tablicą C! Wątpię by było to zamierzone! Skąd ta wartość 953?

2^{29 bitów to 2}26 bajtów = 64 MiB. Zrób sobie tablicę na 2^29 flag zwykłą, nie wektor.

Już sobie poradziłem...

1. Po co ci tablica hashująca? To jest przydatne tyko, gdy chcesz porównać tylko duże obiekty, których standardowe porównanie jest kosztowne (np napisy), a ty masz prosty obiekt liczbowy, którego porównanie prawie nic nie kosztuje.
2. wpakowałeś wszystko w main! To się źle czyta, źle analizuje i poprawia. Podziel to na funkcje: wczytanieWielomianu, obliczWielomian.
3. WTF: vector<int>poly_values[953];
   Pomieszałeś wektor STL ze zwykłą tablicą C! Wątpię by było to zamierzone! Skąd ta wartość 953?

1. Ćwiczenie dotyczy tablicy haszującej.
2. Tak wiem, że to źle, na SPOJu chodzi raczej o rezultat niż o czytelność ;)
3. Nie, to nie pomyłka. Moja funkcja haszująca może zwrócić 953 różne adresy, stąd ta liczba, dlaczego wektor i taki zapis? Gdyż chciałem mieć tablicę wektorów. Chodzi o to, że dla różnych total_value (ilość kombinacji 2^29) zapewne nieraz trafi mi się, że f. haszująca wskaże ten sam index. Wtedy po prostu dodaję do indexu o tym numerze kolejne elementy. I tak pod pod indexem 123 mogę trzymać ile chcę value.

1. złe to ćwiczenie, które uczy na złym przykładzie, który nie dowodzi przydatności rozwiązania.
2. masz błąd i ja się upieram przy tym, że wynika on nie z tego, że brakuje ci zdolności lub wiedzy, ale dlatego, że w takim maglu łatwo się pogubić. Czy tak nie jest prościej i czytelniej? (wiem, że nie tak masz to zrobić, ale po co sobie komplikować życie)

class IntPolymial
{
    vector<int> a;
public:
     int operator()(int x) const
     {
          int result = 0;
          for(int i=0; i<a.count(); ++i)
               result += result*x+a.at(i);
          return result;
     }

     std::istream& read(istream &in)
     {
          int size = 0;
          if (in >> size)
          {
               a.resize(size+1, 0);
               for(int i=0; i<a.count(); ++i)
                    in >> a[i];
          }
          return in;
     }
};

vector<int> mainProblem(const IntPolymial &poly, int modulo, int maxArg)
{
    vector<int> repeats(modulo, 0);
    for(int i=0; i<=maxArg; ++i)
          repeats[poly(i)%modulo]++;

    return result;
}

ostream& printResult(const vector<int>& result, ostream& out)
{
    for(int i=0; i<result.count(); ++i)
          if (result[i]>1)
                 out<< i << ' ' ;
     return out;
}

void main(int, const char *[])
{
    IntPolymial poly;
    poly.read(cin);
    vector<int> result = mainProblem(poly, 229, 9999);
    printResult(result, cout);
}

PS. Źle liczysz wielomian.
Moje rozwiązanie najprawdopodobniej nie zadziała na SPOJ, bo to jest rozwiązaniem najprostszym, a czytając między liniami domyślam się, że są tam pewne dodatkowe wymagania, których mój kod nie spełni (dlatego dałem kod :P).

Tak wiem, że źle liczę wielomian ;) Właśnie w tym był problem, no ale już jest OK, co prawda przechodzi 4/5 testów, ale zawsze to coś, chyba, że ktoś potrafi powiedzieć co tu jest nie tak i dlaczego w jednym teście jest zła odpowiedź?
PS. Nie bijcie, nie chciało mi się "upiękaszać" kodu ;). A i dodatkowych zażożen nie ma, jest tylko treść, którą podałem (ah modulo to 2^29).

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int hash_me(int polynomial_value);


long long poly_value(int grade, int *coefficients, int arg)
{
	long long total_value = coefficients[grade - 1];
	for (int i=2 ; i <= grade ; i++)
    {
		total_value = (((total_value * arg) + coefficients[grade - i]) % 536870912);
    }
    return total_value;
}

int main()
{
	int polynomial_grade = 0;

	cin >> polynomial_grade;
	polynomial_grade++;
	int grade = polynomial_grade;

	int *coefficients = new int [polynomial_grade];
	while(polynomial_grade--)
	{
		cin >> coefficients[polynomial_grade];
	}

	vector<int>hashes;
	vector<int>poly_values[953];
	vector<int>poly_repeats;
	long long total_value;
	int repeats = 0;

	for(int x = 0; x < 10000; x++)
	{
		total_value = poly_value(grade, coefficients, x);

		int hash_key = hash_me(total_value); //getting hash
		hashes.push_back(hash_key);


		
		sort(poly_values[hash_key].begin() , poly_values[hash_key].end()); //sorting
		for(int y = 0; y < poly_values[hash_key].size(); y++) //checking single indexes
		{
				if(poly_values[hash_key][y] == total_value) //if found two same values, send it to the repeats vector
				{
					poly_repeats.push_back(poly_values[hash_key][y]); 
					repeats++;
					break; //if found repeat stop searching 
				} //if nothing found add that number
				 //writing to vector with that hash a value
		}
		poly_values[hash_key].push_back(total_value);
		
	}

	cout << repeats << endl;
	sort(poly_repeats.begin() , poly_repeats.end()); //sorting
	for(int i = 0; i < poly_repeats.size(); i++)
	{
		cout << poly_repeats[i] << endl;
	}
	return 0;
}

int hash_me(int polynomial_value)
{
	return (polynomial_value % 13469) % 953;
}

Daj link do zadania, żeby wszystko było jasne. Ja zakładam, że teraz twój kod (tak samo jak mój) nie przechodzi tych testów, w których do gry wchodzą duże wartości.
Wystarczy, że masz wielomian: 14*x^5 a twój i mój kod przekroczy zakres int-a. Tu trzeba zastosować pewien trick by nie przekroczyć zakresu int-a (nie zdradzę ci jaki by nie psuć ci zabawy ;) ).

PS. Masz straszną słabość do magicznych liczb. Wystarczy, że odłożysz ten problem na parę tygodni, a nie będziesz stanie stwierdzić skąd się wzięły: 953, 13469, 536870912. Teraz ci się wydaję, że zrzędzę, ale jak będziesz pisał dłuższy kod będziesz musiał zmienić zdanie (zwłaszcza w grupie ludzi).

To zadanie z "prywatnego" contestu na SPOJu (uczelnia) więc nie mogę :(. Mój kod przechodzi 4/5 testów, w jednym pisze że jest zła odpowiedź. Twojego kodu nie sprawdzałem, bo jak już mówiłem chodzi mi o funkcjonalność, nie wygląd. Magicznie liczby to liczby pierwsze, wzięte pierwsze z brzegu w zasadzie, więc nie ma wielkiej tajemnicy, inne też będa pasować, chodzi raczej o równomierne rozmieszczenie elementów w tej tablicy. To jak teraz?

Zapomniałem, przykład:
Wejście:

5
13 23 99 100 2 1

Wyjście:

2
20116718
63241178

Panie MarekR22:
W treści zadania jest modulo 2^{29, a nie 229. Ile razy mam to napisać i ile razy ma być przedstawiony kod źródłowy? Proponuję nauczyć się uważnie czytać. Skoro jest to modulo 2}29 to znaczy, że wystarcza 29 najniższych bitów wartości. Przepełnienia można tutaj z powodzeniem olać.

autor:
Czy tablica haszująca jest wymogiem? Jak już napisałem, zadanie można spokojnie zrobić bez żadnego haszowania, drzew i innych pierdół. Wystarczy niewielka (64 MiB) tablica flag.

Tak, jest.

W twoich przykładowych danych widzę błąd, albo ty źle zrozumiałeś zadanie.

Jeśli w pierwszej linii jest liczba n to potem wczytujesz n liczb, natomiast w przykładzie n = 5, a w drugiej linii jest 6 liczb.

Mój program:

#include <algorithm>
#include <cstring>
#include <iostream>
#include <vector>

int computeHash(int value) {
    return value % 735235;
}

int main(int argc, char** argv) {

    int degree;
    std::cin >> degree;
    int coefficients[degree + 1];
    for (int i = degree; i >= 0; i--) {
        std::cin >> coefficients[i];
    }
    int hashTable[1 << 20];
    memset(hashTable, -1, sizeof (hashTable));
    std::vector<int> repetitions;
    for (int x = 0; x < 10000; x++) {
        int fx = coefficients[0];
        int xpower = x;
        for (int i = 1; i <= degree; i++) {
            fx += coefficients[i] * xpower;
            xpower *= x;
        }
        fx = fx & ((1 << 29) - 1);
        int hash = computeHash(fx);
        while ((hashTable[hash] != -1) && ((hashTable[hash] & ((1 << 30) - 1)) != fx)) {
            hash = (hash + 34523) & ((1 << 20) - 1);
        }
        if (hashTable[hash] == -1) {
            hashTable[hash] = fx;
        } else if (hashTable[hash] == fx) {
            repetitions.push_back(fx);
            hashTable[hash] |= (1 << 30);
        }
    }
    std::sort(repetitions.begin(), repetitions.end());
    std::cout << repetitions.size() << std::endl;
    for (std::vector<int>::const_iterator it = repetitions.begin(); it != repetitions.end(); ++it) {
        std::cout << *it << std::endl;
    }
    return EXIT_SUCCESS;
}

Wykorzystuje adresowanie otwarte - najprostsze do zaimplementowania.

Znaczenia wartości w tablicy hashTable:
-1 = pusta komórka
x < (1 << 30) = wartość, która jeszcze się nie powtórzyła
x | (1 << 30) = wartość, która już się powtórzyła

Dla twoich danych przykładowych wypisuje 0 powtórzeń. Nie wiem czy w moim algorytmie jest błąd, czy może bardziej w twoich danych testowych.

Edit:
Pozmieniałem kod.

Hm, dane testowe raczej są dobre, nie słyszałem skarg od innych, że są złe a są osoby, które zaliczyły 5/5, więc to raczej problem u Ciebie. Aha i ta 5 to stopień wielomianu, a jak wiadomo stopień n-tego wielomianu ma n+1 składowych :).

Hmmm, zasugerowałem się twoim błędnym kawałkiem kodu. Gdy pierwsza liczba to n, to alokujesz n-element-ową (chory słownik podkreślał mi tu słowo) tablice, a zgodnie z twoim ostatnim postem powinieneś alokować n + 1 elementów. W każdym razie teraz działa OK dla tych danych testowych.

Twój kod chodzi na 5, ale nie o to chodzi. Po pierwsze,

cin >> polynomial_grade;
polynomial_grade++;

a więc alokuję n + 1, więc tu jest dobrze, po drugie chodzi mi o to, co u mnie nie gra i sprawia, że gdzieś jest błąd, nikt nie widzi?

Jeśli jakaś wartość powtarza się 10 razy to wypisujesz to jako 9 powtarzających się wartości, a to przecież 1 powtarzające się wartość. Przeczytaj jeszcze raz treść zadania bo widocznie nie zrozumiałeś. Masz obliczyć ile wartości się powtarza, a nie ile jest w sumie powtórzeń.

I kolejny błąd w rozumowaniu :) Ale znaleziony i działa, dzięki wielkie.