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

Istnienie kombinacji sumy ciągu podzielnej przez K

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ź.

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.

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/Subset_sum_problem#Pseudo-polynomial_time_dynamic_programming_solution

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ł.

0

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

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

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