Zadanie Promień

0

Mam takie zadanie:
Mamy daną tablicę n liczb całkowitych. Dla każdego elementu tej tablicy szukamy minimalnego promienia ri, takiego że suma wszystkich elementów oddalonych o maksymalnie ri od tego elementu jest równa lub większa od pewnej ustalonej wartości wi.
Wejście
Pierwszy wiersz wejścia zawiera jedną liczbę całkowitą n (1 <= n <= 500 000) oznaczającą liczbę elementów tablicy. W drugim wierszu wejścia jest n liczb całkowitych t0, t1, . . . , tn−1 (1 ¬<=ti <=1 000 000), gdzie ti oznacza wartość i-tego elementu tablicy, a w trzecim n liczb całkowitych w0, w1, . . . , wn−1 (1 <= wi <= 109 ), gdzie wi oznacza ustaloną wartość dla i-tego elementu tablicy.
Wyjście
Pierwszy i jedyny wiersz wyjścia powinien zawierać n liczb całkowitych r0, r1, . . . , rn−1, gdzie ri jest minimalnym promieniem dla i-tego elementu, lub wartość −1, gdy nie można znaleźć odpowiedniego promienia.

Próbowałem już różne warianty wyszukiwania binarnego, za każdym razem błędnie, nie mam pomysłu jak dobrze zaimplementować wyszukiwanie binarne w tym zadaniu, ostatni pomysł jaki zrobiłem to:

def binary(pref, index, key):
    l_index = index // 2
    r_index = (((len(pref) - 2) - index) // 2) + index
    za_duzo = True
    if pref[r_index+1] - pref[l_index] == key:
        return max(index - l_index, r_index - index)
    elif pref[r_index+1] - pref[l_index] < key: 
        za_duzo = False
    
    while index >= l_index > 0 or index <= r_index < len(pref) - 2:
        promien = pref[r_index+1] - pref[l_index]
        if promien <= key:
            if za_duzo is True:
                break
            if index >= l_index > 0:
                l_index -= 1
            if index < r_index <= len(pref) - 2:
                r_index += 1
        else:
            if za_duzo is False:
                break
            if index > l_index >= 0:
                l_index += 1
            if index <= r_index < len(pref) - 2:
                r_index -= 1
    if pref[r_index+1] - pref[l_index] >= key:
        return max(index - l_index, r_index - index)
    return -1

def main():
    n = int(input())
    t = list(map(int, input().split()))
    w = list(map(int, input().split()))
    pref = [0]
    for num in t:
        pref.append(num + pref[-1])
    for i in range(len(w)):
        print(binary(pref, i, w[i]))
main()

Próbowałem też 4 zmiennymi l_front, h_front, l_back, h_back niestety z miernym skutkiem, czy mógłby mi ktoś pomóc rozwiązać to zadanie?

1

Wyszukiwanie binarne jest na wikipedii, wystarczy przepisać.

def bin_search(xs, n, elem):
    left = 0;
    right = n - 1
    while left <= right:
        mid = (left + right) // 2
        if xs[mid] < elem:
            left += 1
        elif xs[mid] > elem:
            right -= 1
        else:
            return mid
    return -1

https://en.wikipedia.org/wiki/Binary_search_algorithm

Zastanawiam się po co to wyszukiwane w problemie.

1

Złożoność mojego algorytmu powinna być logarytmiczna, nie potrafię tak przekształcić algorytmu wyszukiwania binarnego aby dawał odpowiednie wyniki do mojego zadania, a jak ty byś je rozwiązał ?

Jeżeli dla każdego elementu trzeba coś znaleźc, to wydaje sie, że złożoność będzie co najmniej liniowa. Nie wiem jak bym rozwiązał, brute force jesyt kwadratowy, więc trza by coś pokombinować. Ponawiam pytanie, o co chodzi z tym wyszukiwaniem binarnym, chyba miałeś jakis pomysł?

0

Oczywiście mój błąd algorytm ma mieć złożoność O(n log n)
Może sam tekst zadania nie jest zbyt jasny więc dodam jeszcze przykład
Dla wejścia:
6
2 3 1 4 2 1
6 3 8 8 10 14
Poprawną odpowiedzią jest:
2 0 1 2 3 -1

szukamy binarnie używając tablicy prefiskowej czy suma elementów oddalonych o r jest większa czy mniejszą od w[i] no i robimy to wyszukiwaniem binarnym np dla t[3]
2 3** 1 4 2** 1 suma elementów w promieniu r = 1 wynosi 7 czyli mniej niż 8 więc zwiększamy promień
2 3 1 4 2 1 suma elementów w promieniu r = 2 wynosi 11 czyli więcej niż 8 i jest to minimalny promień dla jakiego suma elementów jest większa od 8 więc wynik dla t[3] to 2

1

Poprawny kod powinien wyglądać tak:

def binary(pref, index, key):
    l, r = 0, max(len(pref)-2-index, index)
    res = -1
     
    while l <= r:
        mid = (l+r)//2
        l_index, r_index = max(0, index-mid), min(len(pref)-2, index+mid)
         
        if pref[r_index+1]-pref[l_index] >= key:
            r = mid-1
            res = mid
        else:
            l = mid+1
             
    return res

def main():
    n = int(input())
    t = list(map(int, input().split()))
    w = list(map(int, input().split()))
    pref = [0]
    for num in t:
        pref.append(num + pref[-1])
    for i in range(len(w)):
        print(binary(pref, i, w[i]), end=" ")
main()
0

Jak się nie pamięta implementacji wyszukiwania binarnego, to można użyć gotowej z biblioteki. Nawet w tym wypadku dałoby radę tworząc odpowiedni "widok" na dane poddawane bisekcji.

from bisect import bisect_left

class PivotedRangeSum:
    def __init__(self, prefix_sums, pivot):
        self.prefix_sums = prefix_sums
        self.pivot = pivot
        self.n = len(prefix_sums)

    def __getitem__(self, radius):
        start, end = max(0, self.pivot - radius), min(self.n - 1, self.pivot + radius + 1)
        return self.prefix_sums[end] - self.prefix_sums[start]

    def __len__(self):
        return self.n

def main():
    n = int(input())
    t = list(map(int, input().split()))
    w = list(map(int, input().split()))
    pref = [0]
    for num in t:
        pref.append(num + pref[-1])

    for pivot, sum_treshold in enumerate(w):
        min_gte_treshold = bisect_left(PivotedRangeSum(pref, pivot), sum_treshold)
        print(min_gte_treshold if min_gte_treshold < len(pref) else -1 , end=" ")

main()

Pythonowiec pewnie napisałby to ładniej.

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