Wątek przeniesiony 2019-01-10 09:07 z C/C++ przez Shalom.

Istnienie kombinacji sumy ciągu podzielnej przez K

Odpowiedz Nowy wątek
2019-01-09 20:21
0

Witam. Dostaliśmy jedno zadanie, które wydaje mi się dosyć ciężkie. Sam napisałem kod, ale dla większych liczb nie wykonuje się w normalnym czasie. Znajomy też napisał, ale nie działa dla większych liczb. Zadanie brzmiało tak:
Rozpatrujemy ciąg maksymalnie 10000 liczb całkowitych o wartości od -1000 do 1000 . Wpisujemy ile ma zostać wprowadzonych liczb i dzielnik. Tworzymy z ich ciągu różne wyrażenia arytmetyczne, np. dla 3 liczb 5, 10, -30 to będzie:
5+10+(-30), 5+10-(-30), 5-10 -(-30), 5+10-(30). Sumując osobno każdy ciąg dostajemy różne wyniki. Potem dzielimy przez wcześniej wprowadzony dzielnik od 2 do 100 i sprawdzamy czy jakikolwiek z wyników jest podzielny przez dzielnik. Jeżeli jest to ma zostać wyświetlone TAK a jeżeli żaden nie odpowiadał temu to wyświetla NIE.
Problem mam w tym, że przy 10000 cyfr takich kombinacji jest 2^9999 co jest niemożliwą do sprawdzenia liczbą. Zauważyłem zależność, że przy takich dużych ilościach wyników bardzo rzadkie jest, żeby np. nie był żaden wynik podzielny np. przez 23 z prawdopodobieństwa. Czy można zrobić to takim podejściem, że zrobimy nieskończoną pętle tworzenia takich wyników i przy podzielności sprawdzania czy modulo jest równe zero czy jednak mogą istnieć jakieś wyjątki? Załączam całą treść zadania gdyby moje tłumaczenie było zbyt chaotyczne. Z góry dziekuje za odpowiedź.

  • gfgf.jpg (0,19 MB) - ściągnięć: 22
edytowany 3x, ostatnio: Shalom, 2019-01-09 21:19
każdy wątek na forum to jest "Problem z kodem", więc wysil się bardziej przy pisaniu tytułu. - MarekR22 2019-01-09 20:46
Zmień na "Istnienie kombinacji sumy ciągu podzielnej przez K", bo obecny tytuł nie jest lepszy od starego. - MarekR22 2019-01-09 21:16

Pozostało 580 znaków

2019-01-09 21:09
0

licz wszystko modulo K (do poczytania).

Zwróć uwagę, że

  • każdy element można uprościć a = a % K
  • jeśli zmieniasz znak na ujemny przed elementem, poprawka do sumy modulo K to 2 * (K - a) % K
  • wystarczy jak będziesz śledził wszystkie możliwe kornety sumy modulo K, więc potrzebujesz tablicę bool corrections[N] (przy czym element zerowy cię nie interesuje).
  • sprawdzasz czy suma wszystkiego modulo K pasuje do możliwej poprawki.

Wychodzi złożoność o(N * K) zamiast o(N * 2^(N-1)), czyli różnica jest dramatyczna.


Jeśli chcesz pomocy, NIE pisz na priva, ale zadaj dobre pytanie na forum.
edytowany 5x, ostatnio: MarekR22, 2019-01-09 21:27
Mam zrobione już dwa podpunkty i mam już nadpisaną tablice skróconymi liczbami bez zer, ale dalej nie rozumiem jak użyć kolejne podpunkty, żeby zmienić rodzaj złożoności. Nie rozumiem, ale czy dalej nie tworzymy różnych wariacji ciągów? - osek916 2019-01-09 22:20

Pozostało 580 znaków

2019-01-09 21:23
0

@MarekR22:

Z tym upraszczaniem to mam nadzieje że żartujesz. (2+2) mod 3 == 1 to nie jest to samo co 2 mod 3 + 2 mod 3 == 4.
A dobra, w drugą stronę to w sumie robimy ;]

Nie do końca jednak widzę tutaj to oszacowanie złożoności. Chyba jest trochę zbyt optymistyczne. Liczby są mocno ograniczone, więc chyba ok.
Znamy sumę wszystkich liczb mod K, stąd wiemy ile nam "brakuje" do 0, żeby się ładnie dzieliła.
Dla każdej z liczb możemy wyznaczyć sobie korektę którą powoduje (tzn odjęcie zamiast dodania tej liczby), bo jeśli np. aktualnie wynik to 23 to odjęcie dodanej wcześniej 4 da nam resztę 23 - 8 mod K, więc wiemy że korekta to -8
Ale teraz stoimy przed problemem sprowadzonym do subset sum na moje oko -> musimy z tablicy korekt wybrać podzbiór liczb który mod K będzie sumował sie do 0 (razem z tą początkową sumą modulo). Więc jakieś https://en.wikipedia.org/wiki[...]_dynamic_programming_solution


Na PW przyjmuje tylko (ciekawe!) zlecenia. Masz problem? Pisz na forum, nie do mnie.
edytowany 4x, ostatnio: Shalom, 2019-01-09 21:35
Pisałem sumy modulo K - MarekR22 2019-01-09 21:25
@MarekR22: patrz mój edytowany post, nie bardzo widzę jak ten subset sum liniowo tu rozwiązałeś - Shalom 2019-01-09 21:32
A dobra, mamy tu te liczby mocno ograniczone, to można ten subset sum rozwiązać dynamicznie. Trochę spory przeskok myślowy tu coś zrobiłeś :P - Shalom 2019-01-09 21:34

Pozostało 580 znaków

2019-01-09 21:42
0
Shalom napisał(a):

Nie do końca jednak widzę tutaj to oszacowanie złożoności. Chyba jest trochę zbyt optymistyczne.

std::vector<bool> corrections(K, false);
corrections[0] = true;
for(auto a : values) { // N iteracji
    auto newCorrections = corrections;
    for (int c = 0; c < K; ++c) { // K iteracji
       if (corrections[c]) {
            newCorrections[ (c + 2 *(K -a)) % K] = true;
       }
    }
    corrections = newCorrections;
    sum += a;
}
 
result = corrections[sum % K];

Jak nic wychodzi o(N * K).
Discalimer: celowo rozwiązanie nie pasujące idealnie do problemu, żeby pytajacy się troszkę pomęczył.


Jeśli chcesz pomocy, NIE pisz na priva, ale zadaj dobre pytanie na forum.
edytowany 4x, ostatnio: MarekR22, 2019-01-09 21:44
Tak tak, już się zreflektowałem ze liczby są małe więc można ten subset sum rozwiązać tu dynamicznym algorytmem ;) - Shalom 2019-01-09 22:09
"c + 2 *(K -a)) % K" skąd mogę taki wzór wyprowadzić? (albo przybliżony) już modula porobione i dzielę sumę przez K co daje mi pewną liczbę, ale nie wiem w jaki sposób ominąć tą podstawową wariancję i przejść na Twoją, bo jednak Ty powtarzasz to K razy tylko - osek916 2019-01-09 23:49
c to wcześniej wyliczona korekta (wcześniejsze iteracje), 2 *(K -a)) % K bieżąca korekta (bieżącą trzeba połączyć ze wszystkimi wcześniej wyliczonymi). (K -a) % K jest równoważne (-a)%K (patrz link wiki), a po zmianie znaku trzeba odjąć to dwa razy (raz za wcześniejsze dodanie, raz za właściwe odejmowanie). - MarekR22 2019-01-09 23:57

Pozostało 580 znaków

2019-01-09 22:08
0

Na pewno tak? Mi to wygląda na dynamic programming.


Pozostało 580 znaków

2019-01-11 15:49
0

A tutaj, tak żeby OP też się pomęczył, jest zaprogramowane poprawne rozwiązanie, które pasuje do problemu. Ma taką jedyną "wadę", że jest napisane w OCamlu:

let mod_ n k =
    let m = n mod k in
    if m < 0 then m + k else m
 
(* indices need to be sorted with increasing order *)
let true_list_on_indices indices size =
    let rec loop indices i result =
        if i >= size then result else
        match indices with
        | []   -> false::(loop indices (i+1) result)
        | j::t -> if i = j then loop t (i+1) (true::result) 
                           else loop (j::t) (i+1) (false::result)
    in List.rev (loop indices 0 [])
 
let sumy input k =
    match input with 
    | [] -> assert(false)
    | n::t ->
        let rec loop remainders input =
            match input with
            | []      -> List.hd remainders
            | n::tail ->
                let pos = List.mapi 
                    (fun i v -> if v then [mod_ (n+i) k; mod_ (-n+i) k] else [])
                    remainders
                in let pos = List.sort compare (List.flatten pos)
                in let remainders = true_list_on_indices pos k
                in loop remainders tail
        in loop (true_list_on_indices [mod_ n k] k) t
 
No og, spróbuję ;_; - osek916 2019-01-11 15:49
nawet nie próbował się męczyć, napisał na innym forum - m4sk1n 2019-01-11 19:29
Dalej próbuję, ale czasu mam coraz mniej. Trochę zestresowany jestem, że nie zdążę a to jedno z wielu zadań. - osek916 2019-01-11 20:38

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

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