problem znalezienia wzorca (XOR)

0

mam problem z zadaniem z hackerrank
https://www.hackerrank.com/challenges/xor-se

w sekcji discussion są podane rozwiązania O(1)

long long calc(long long a)
{
   long long res[] = {a, a, 2, 2, a+2, a+2, 0, 0};    
   return res[a%8];
}

cout << (calc(R)^calc(L-1)) << endl;

lub

long long G(long long x){
    long long a = x % 8;
    if(a == 0 || a == 1) return x;
    if(a == 2 || a == 3) return 2;
    if(a == 4 || a == 5) return x+2;
    if(a == 6 || a == 7) return 0;
    return 0;
}

ale - po prostu - za głupi jestem aby zrozumieć, czemu tak?

z góry dziękuję z pomoc i podpowiedź, lub wskazówkę - czemu tak, skąd ta 8?

0
  1. Tablica xorów wygląda tak:
    0 1 3 0
    4 1 7 0
    8 1 11 0
    12 1 15 0
    16 1 19 0
    Po podzieleniu modulo przez 8 tak:
    0 1 3 0
    4 1 7 0
    0 1 3 0
    4 1 7 0
    0 1 3 0
    Zapewne ta ósemka bierze się z tej cykliczności.

  2. x^x = 0;
    x^0 = x;
    x^1 = x-1 (jeżeli x%2 != 0) lub x+1 (jeżeli x%2 == 0);

  3. Dalej sam jestem ciekaw... trzeba porozpisywać jakie wartości dają różne kombinacje ilości xorów z tabeli;
    np:
    od 1 do 4 da 2; od 5 do 8 da 2, od 9 do 12 da 2;
    od 1 do 8 da 0, od 0 do 12 da 0;
    od 1 do 5 da 2; od 6 do 9 da 14;

1

Nie patrzyłem na inne rozwiązania, więc moje:

TL;DR:
- A^A = 0, więc można redukować czynniki występujące parzystą ilośc razy
- istnieje prosty wzór na xor liczb 0..n

Tablica A wygląda tak:

0
0^1
0^1^2
0^1^2^3
0^1^2^3^4
0^1^2^3^4^5
...

Teraz jeśli pytamy o wynik xora wszystkich elementów od A[X] do [Y], to wyjdzie coś takiego:

xor all:
5^6^7^8^9^10^11^12^13
5^6^7^8^9^10^11^12^13^14
5^6^7^8^9^10^11^12^13^14^15
5^6^7^8^9^10^11^12^13^14^15^16
5^6^7^8^9^10^11^12^13^14^15^16^17
5^6^7^8^9^10^11^12^13^14^15^16^17^18
5^6^7^8^9^10^11^12^13^14^15^16^17^18^19
5^6^7^8^9^10^11^12^13^14^15^16^17^18^19^20

Najpierw sprawdzamy czy Y-X jest parzyste - w tym przypadku jest, więc redukuje się cały czynnik A[X]:

xor all:
14
14^15
14^15^16
14^15^16^17
14^15^16^17^18
14^15^16^17^18^19
14^15^16^17^18^19^20

(gdyby było nieparzyste to różniłoby się tylko zxorowaniem z tym fragmentem).

Co dalej? Teraz co drugi czynnik występuje parzystą ilość razy. Więc skracamy sobie je wszystkie:

xor all
14
14
14^16
14^16
14^16^18
14^16^18
14^16^18^20

Teraz nie trzeba mieć mensy żeby zauważyć że to sie dalej skraca:

14^16^18^20

Xorujemy teraz kilka liczb parzystych. Jako że wszystkie są parzyste, możemy sobie podzielić je przez dwa, zxorować i pomnożyć przez dwa (bo wiemy że ostatni bit to zawsze zero) (dla nieparzystych algorytm taki sam, z poprawką na to że wiemy że ostatni bit to zawsze 1)

2*(7^8^9^10)

Już wygląda całkiem nieźle. Jedyne co zostało to policzenie xorów 7^8^9^10 (tzn. xorów N konsekturywnych liczb naturalnych). Xor liczb 0..n można policzyć w czasie O(1) np. tak:

if n % 2 == 1 {
    result = (n % 4 == 1) ? 1 : 0;
} else {
    result = (n % 4 == 0) ? n : n + 1;
}

A xor(A..B) to ofc xor(0..A) ^ xor(0..B).


No i to rozwiązanie generalnie wygląda na wzorcówkę którą wkleiłeś (tylko kody które dałeś są bardziej "clever" zapisane, bo algorytmicy lubią takie sztuczki).

0

bardzo dziękuję za pomoc i wytłumaczenie

1 użytkowników online, w tym zalogowanych: 0, gości: 1