English
Temat: jak sie robilo te macierze
jak sie robilo te macierze
Postaram się wrzucić omówienie przed 3. edit: chwilę po 3 ale jest.
No mi zajęło 13h ponad (i ponad 900 linii) i no liczę na 10, ale to straszliwa przeprawa była.
Powiedzmy, że mogliby się umówić "będzie dokładnie jeden rząd z dokładnie czterema jedynkami" - dzięki temu teraz rozróżnialne byłoby pierwsze sześć kolumn od ostatnich czterech kolumn (bo Bajtek znalazłby jedyny rząd z czterema jedynkami, wyciągnął go na górę i dał jedynki na prawo). No i uprzedzając nie może być aż tak dobrze, że zawsze będzie taki rząd, trzeba korzystać i z sytuacji gdy jest i z sytuacji gdy nie ma.
No więc jaki jest framework (powiedzmy do budowania macierzy, żeby dało się ją jednoznacznie odzyskiwać, myślimy z tej strony). No to na początku Algosia ma dostępne wiersze jedenastu typów (od 0 do 10 jedynek). No to wspólnie się umawiają który z typów jest "pierwszym" typem, tzn. tym, po którym rozbijemy się na przypadki. No to powiedzmy, że się umawiają, że głównym typem jest ten typ wiersza, który ma cztery jedynki (potem ustalimy jak powinni się umawiać). No to są dwa przypadki: albo Algosia da taki wiersz albo nie (da się zostać z założeniem, że góra jeden).
No to brancz: Jeśli takiego typu wiersza nie używamy, to taki typ wiersza odpada i jedziemy dalej - mało się zmienia. Jeśli damy taki typ wiersza (powtarzam, wystarczy jeden) to teraz części kolumn stają się rozróżnialne dla Bajtka - czyli no kolumny się dzielą na pierwsze 6 i ostatnie 4 np. To, co dodatkowo się dzieje, to "rozdrabniają" się dostępne typy wierszy - np. typ "wiersz z pięcioma jedynkami" rozbija się na typy "w pierwszej części jedna, w drugiej cztery", "w pierwszej części dwie, w drugiej trzy", "w pierwszej części trzy, w drugiej dwie", "w pierwszej części cztery, w drugiej jedna" i "w pierwszej części cztery, w drugiej zero". No i moglibyśmy się tak branczować i liczyć ile różnych opcji umiemy przekazać i da się dostrzec powtarzający się stan: mianowicie liczy się podział zbioru kolumn, ile wierszy już użyliśmy oraz jakie mamy dostępne typy wierszy.
No i się da mocno zbijać ten stan - podziałów nie musi być 2^9 tylko 42, a dla każdego typu wiersza możemy zauważyć, że jeśli np. dla podziału na cztery i sześć kolumn, to nie ma znaczenia czy w pierwszej części daje on jedną jedynkę, a w drugiej cztery, czy w pierwszej trzy, a w drugiej dwie - liczy się tylko min(ile jedynek, długość bloku - ile jedynek) - dzięki temu typy wierszy bardzo się powtarzają i interesuje nas tylko liczność każdego.
W tym co ostatecznie robię (ponieważ to była najprostsza opcja, która wybijała te 3e16 i jednocześnie działała wystarczająco szybko) pozwalam sobie na użycie każdego wiersza tylko raz, chyba, że zostanę w sytuacji, że żaden z typów nie da mi żadnej dodatkowej informacji o podziale zbioru kolumn - wtedy już muszę pzowolić na powtarzanie wierszy (żeby większe liczby móc przekazać).
No to trzeba wybrać jakąś heurystykę do umawiania się na to który typ wiersza jest tym po którym się branczujemy - jest istotna, bo wpływa i na liczbę którą możemy przesłać i na czas działania backtracka. No to wystarczyła mi taka, że jeśli nic jeszcze nie jest podzielone, to najbardziej chcę używać wierszy kolejno z jedną, dwiema, trzema, czterema, pięcioma jedynkami (przypominam, że 4 jedynki to taki sam typ wiersza co 6 jedynek) (wiersze bez jedynek nie dają informacji, więc zawsze zostawiam je na koniec), a w pozostałych przypadkach maksmalizuję zyskaną informację, czyli jeśli w grupie x nierozróżnialnych kolumn jakiś typ wiersza ma y jedynek, to wagą takiego typu wiersza jest iloczyn po (x choose y) - czyli w sumie odwrotnie niż na samym początku, bo tam minimalizowałem uzyskaną informację, a w całej reszcie maksymalizuję.
No liczenie tego backtracka dostatecznie szybko było mordęgą, a i użycie go do komunikacji też nie było proste - Algosia i Bajtek nie mogą "tak po prostu" sobie zakładać, że danie gdzieś x i liczba_kolumn-x jedynek to to samo, bo muszą rozróżniać takie typy wierszy, a z drugiej strony muszą utrzymywać rzeczy w dokładnie takiej samej kolejności co ten backtrack - tzn. muszą zawsze dokonać dokładnie tej samej decyzji co do tego po którym typie wiersza się zbranczować - w przeciwnym wypadku możliwe do przekazania przedziały liczb by się nie zgadzały.
Powiedzmy, że mogliby się umówić "będzie dokładnie jeden rząd z dokładnie czterema jedynkami" - dzięki temu teraz rozróżnialne byłoby pierwsze sześć kolumn od ostatnich czterech kolumn (bo Bajtek znalazłby jedyny rząd z czterema jedynkami, wyciągnął go na górę i dał jedynki na prawo). No i uprzedzając nie może być aż tak dobrze, że zawsze będzie taki rząd, trzeba korzystać i z sytuacji gdy jest i z sytuacji gdy nie ma.
No więc jaki jest framework (powiedzmy do budowania macierzy, żeby dało się ją jednoznacznie odzyskiwać, myślimy z tej strony). No to na początku Algosia ma dostępne wiersze jedenastu typów (od 0 do 10 jedynek). No to wspólnie się umawiają który z typów jest "pierwszym" typem, tzn. tym, po którym rozbijemy się na przypadki. No to powiedzmy, że się umawiają, że głównym typem jest ten typ wiersza, który ma cztery jedynki (potem ustalimy jak powinni się umawiać). No to są dwa przypadki: albo Algosia da taki wiersz albo nie (da się zostać z założeniem, że góra jeden).
No to brancz: Jeśli takiego typu wiersza nie używamy, to taki typ wiersza odpada i jedziemy dalej - mało się zmienia. Jeśli damy taki typ wiersza (powtarzam, wystarczy jeden) to teraz części kolumn stają się rozróżnialne dla Bajtka - czyli no kolumny się dzielą na pierwsze 6 i ostatnie 4 np. To, co dodatkowo się dzieje, to "rozdrabniają" się dostępne typy wierszy - np. typ "wiersz z pięcioma jedynkami" rozbija się na typy "w pierwszej części jedna, w drugiej cztery", "w pierwszej części dwie, w drugiej trzy", "w pierwszej części trzy, w drugiej dwie", "w pierwszej części cztery, w drugiej jedna" i "w pierwszej części cztery, w drugiej zero". No i moglibyśmy się tak branczować i liczyć ile różnych opcji umiemy przekazać i da się dostrzec powtarzający się stan: mianowicie liczy się podział zbioru kolumn, ile wierszy już użyliśmy oraz jakie mamy dostępne typy wierszy.
No i się da mocno zbijać ten stan - podziałów nie musi być 2^9 tylko 42, a dla każdego typu wiersza możemy zauważyć, że jeśli np. dla podziału na cztery i sześć kolumn, to nie ma znaczenia czy w pierwszej części daje on jedną jedynkę, a w drugiej cztery, czy w pierwszej trzy, a w drugiej dwie - liczy się tylko min(ile jedynek, długość bloku - ile jedynek) - dzięki temu typy wierszy bardzo się powtarzają i interesuje nas tylko liczność każdego.
W tym co ostatecznie robię (ponieważ to była najprostsza opcja, która wybijała te 3e16 i jednocześnie działała wystarczająco szybko) pozwalam sobie na użycie każdego wiersza tylko raz, chyba, że zostanę w sytuacji, że żaden z typów nie da mi żadnej dodatkowej informacji o podziale zbioru kolumn - wtedy już muszę pzowolić na powtarzanie wierszy (żeby większe liczby móc przekazać).
No to trzeba wybrać jakąś heurystykę do umawiania się na to który typ wiersza jest tym po którym się branczujemy - jest istotna, bo wpływa i na liczbę którą możemy przesłać i na czas działania backtracka. No to wystarczyła mi taka, że jeśli nic jeszcze nie jest podzielone, to najbardziej chcę używać wierszy kolejno z jedną, dwiema, trzema, czterema, pięcioma jedynkami (przypominam, że 4 jedynki to taki sam typ wiersza co 6 jedynek) (wiersze bez jedynek nie dają informacji, więc zawsze zostawiam je na koniec), a w pozostałych przypadkach maksmalizuję zyskaną informację, czyli jeśli w grupie x nierozróżnialnych kolumn jakiś typ wiersza ma y jedynek, to wagą takiego typu wiersza jest iloczyn po (x choose y) - czyli w sumie odwrotnie niż na samym początku, bo tam minimalizowałem uzyskaną informację, a w całej reszcie maksymalizuję.
No liczenie tego backtracka dostatecznie szybko było mordęgą, a i użycie go do komunikacji też nie było proste - Algosia i Bajtek nie mogą "tak po prostu" sobie zakładać, że danie gdzieś x i liczba_kolumn-x jedynek to to samo, bo muszą rozróżniać takie typy wierszy, a z drugiej strony muszą utrzymywać rzeczy w dokładnie takiej samej kolejności co ten backtrack - tzn. muszą zawsze dokonać dokładnie tej samej decyzji co do tego po którym typie wiersza się zbranczować - w przeciwnym wypadku możliwe do przekazania przedziały liczb by się nie zgadzały.
No ale to tragedia jakaś, jak ktoś ma jakoś prościej, to ja też chętnie się dowiem xd
dzieki za wytlumaczenie