W dniu sobota, 11 maja 2013 12:28:04 UTC+2 użytkownik bartekltg napisał:

> W skrócie, parzysta liczba 'kliknięć' w pole jest redukowana
> do zera.
Bym to ujął trochę inaczej. Parzysta ilość kliknięć w dane pole
powoduje, że pola na które kliknięcie ma wpływ, przyjmują wartości takie
jak w stanie początkowym.


> Kolejność klikania też nie ma znaczenie.
Jasne, takie ma właściwości xor.


> Możesz więc klikną raz lub w ogole. Stąd też wiadomo,
> że kliknięć nie będzie więcej niż pol szachownicy.
Jasne.


> Zapisz kliknięcia jako wektor v.
Rozumiem, że mamy wektor zero-jedynkowy o rozmiarze
n*m. Jak wektor ma jedynkę, to było kliknięcie, a jak zero to
kliknięcia nie było. Wektor v jest rozwiązaniem.


> Wtedy stan danego pola możesz opisać jakio w = A*v
> gdzie A to niezbyt gęsta macierz (mniej niż 5*n*m elementów).
> Oba wektory mają długość m*n, maciesrz siłą rzeczy (m*n)x(m*n).
> Wszytko dzieje się modulo 2.
Nie wiem co to za macierz A. Na razie widzę tak:
v[n*m] - kolumnowy zero-jedynkowy wektor kliknięć
x[n*m] - wierszowy zero-jedynkowy wektor wpływu kliknięcia
b[n*m] - kolumnowy zero-jedynkowy stan początkowy
i - wektor jedynkowy
b = (v*x*i) .modulo 2
Szukamy wektora zero-jedynkowego v. Siłowe sprawdzenie ma
złożoność (n*m)^2. Szybsze zaproponowałem kilka postów
wyżej z rekurencją i zapamiętywaniem ile razy było zapamiętane
dane pole i w którym wywołaniu rekurencyjnym - nie jestem
pewny na 100% czy zadziała.


> Konfiguracja zapalająca czy konfiguracja gasząca to to samo,
> więc szykamy v, takiego, że w to nasz stan początkowy i
> w = A*v
Jasne, poza macierzą A.


> Po pierwsze, da się rozwiązać, kiedy w siedzi w przestrzeni rozpiętej
> przez kolumny A (jest a obrazie A, dość trywialny wniosek).
> Ponieważ obraz A będzie duży, łatwiej do algorytmu wyznaczyć kojądro*)
> i sprawdzać, czy aby nasza oczekiwana konfiguracja sie z nim nie
> przecina (iloczynem skalarnym).
Jak to sie rozwiązuje i co to za macierz A?

Pozdrawiam