Spędziłem kilka godzin nad zadaniem Simple Fun #119: Sub Sets Parity. Jeśli ktoś lubi zadania algorytmiczne i chciałby zrobić to ciekawe zadanie, to ostrzegam, że ten post jest spojlerem.
Wzór na liczbę kombinacji:
Pomysły zmieniały mi się od mało wydajnych do maksymalnie (według mnie) zoptymalizowanych:
- obliczanie liczby kombinacji za pomocą wzoru,
- ograniczenie dwóch wyrażeń z silnią z mianownika do jednego i skracanie liczb za pomocą wyszukiwania największych wspólnych wielokrotności,
- iteracja przez wszystkie możliwości za pomocą rekurencji i negowanie bitu parzystości bez zapamiętywania ilości kombinacji,
- rezygnacja z kolekcji, wykluczenie liczb nieparzystych i wyszukiwanie ilości możliwości podzielenia przez 2 liczb z licznika i z mianownika, a na końcu porównanie tych ilości.
Mój ostateczny poprawny, ale niezaakceptowany kod (z powodu "Execution Timed Out"):
public string SubsetsParity(int n, int k)
{
var subsetLength = n - k;
if (k == 1 || subsetLength == 1)
{
return (n & 1) == 0 ? "EVEN" : "ODD";
}
var twoFactorsCount = 0;
var subsetValue = 2;
while (subsetValue <= subsetLength)
{
var parityMask = 1;
while ((subsetValue & parityMask) == 0)
{
parityMask <<= 1;
twoFactorsCount++;
}
subsetValue += 2;
}
subsetValue = ((k + 1) & 1) == 0 ? k + 1 : k + 2;
while (subsetValue <= n)
{
var parityMask = 1;
while ((subsetValue & parityMask) == 0)
{
if (twoFactorsCount == 0)
{
return "EVEN";
}
parityMask <<= 1;
twoFactorsCount--;
}
subsetValue += 2;
}
return "ODD";
}
Po kilku godzinach otrzymywania "Out Of Memory" lub "Execution Timed Out" poddałem się i sprawdziłem rozwiązania. Nie zdarza mi się rezygnować w przypadku tego typu zadań, ale tym razem nie miałem już nadziei na jeszcze lepszy pomysł. Wydawało mi się, że jeśli wzór jest skomplikowany, to nie istnieje rozwiązanie o złożoności obliczeniowej O(1). Największe zdziwienie, że takie rozwiązanie jest możliwe:
public string SubsetsParity(int n, int k){
return (k & (n-k)) != 0 ? "EVEN" : "ODD";
}
Czy ktoś z was wie, dlaczego to rozwiązanie działa? Robiliście to zadanie i macie swoje rozwiązania, które zostały zaakceptowane?