Problem z zadaniem z wyszukiwaniem binarnym po wyniku.

0

Witam bardzo serdecznie, mam problem z zadaniem wykorzystującym wyszukiwanie binarne. Napisany przeze mnie kod daje błędne wyniki w test case'ie. Proszę o wskazanie błędów, które popełniłem. Sam zamysł wyszukiwania binarnego po wyniku myślę, że rozumiem i potknąłem się w implementacji, ale nie potrafię sam zobaczyć, co zrobiłem źle.

Mamy daną tablicę n liczb całkowitych. Dla każdego elementu tej tablicy szukamy minimalnego promienia r, takiego że suma wszystkich elementów oddalonych o maksymalnie r od tego elementu jest równa lub większa od pewnej ustalonej wartości w.
Wejście: Pierwszy wiersz wejścia zawiera liczbę n(1<= n <= 500 000) ozn. liczbę elem. tablicy. W drugim wierszu wejścia jest n liczb całkowitych t0,t1,t2,...t(n-1)(1<= t <= 1 000 000), gdzie t(i) ozn. wartość i-tego elementu tablicy, a w trzecim wierszu n licz całk w0, w1, w2,... w(n-1) (1<= w<= 10^9), gdzie w ozn. ustaloną wartość dla i-tego elementu tablicy.
Wyjście: Pierwszy i jedyny wiersz wyjścia powinien zawierać n liczb całkowitych r1,r2,r3...r(n-1), gdzie r(i) jest minimalnym promieniem dla i-tego elementu, lub wartość -1, gdy nie można znaleźć odpowiedniego promienia.
Przykład:
6
2 3 1 4 2 1
6 3 8 8 10 14
Poprawna odpowiedź:
2 0 1 2 3 -1


#include<cstdio>
#include<algorithm>
using namespace std;
/* test case
6
2 3 1 4 2 1
6 3 8 8 10 14
 
answer:
2 0 1 2 3 -1
*/
int t[1000006]; // wejscie
int w[1000006]; // wejscie
 
int sum[500001]; // tablica sum prefiksowych sum elementów
bool check(int x,int r,int n)
{
    if(sum[min(x+r,n)]-sum[max(x-r,0)]>=w[x])
   // if(sum[x+r]-sum[x-r]-t[x]>=w[x])
        return true;
    return false;
}
int bin(int a,int b)
{
    int r=0;
    int wynik=-1;
    int x=a;
    int n=b;
 
    while(b-a>1)
    {
        r=(a+b)/2;
        //printf("wynik:%d   a:%d   b:%d   \n",wynik,a,b);
 
        if(check(x,r,n))
            {
                wynik=r;
                b=r;
            }
        else
            a=r;
    }
    return wynik;
 
}
int main()
{
    int n;
    scanf("%d",&n);
 
    for(int i=0;i<n;++i)
        scanf("%d",&t[i]);
 
    sum[0]=t[0];
 
    for(int i=1;i<n;++i)
        sum[i]=sum[i-1]+t[i];
 
    for(int i=0;i<n;++i)
        scanf("%d",&w[i]);
 
    for(int i=0;i<n;++i)
       printf("%d\n",bin(i,n-1));
 
    return 0;
}

0

Wyszukiwanie binarne robi się na tablicy posortowanej. Dodatkowo w tym konkretnym zadaniu raczej ci się nie przyda.

0
sig napisał(a):

Wyszukiwanie binarne robi się na tablicy posortowanej. Dodatkowo w tym konkretnym zadaniu raczej ci się nie przyda.

Akurat z tego co się orientuję, używam przedziały liczb naturalnych, który sam z siebie jest posortowany. Dzięki wyszukiwaniu binarnemu mogę znaleźć odpowiednią liczbę spełniającą warunki zadania, kiedy umiem tylko sprawdzić czy jakaś liczba spełnia warunek postawiony w zadaniu, czyli sama idea wyszukiwania binarnego po wyniku. Wątpię, żeby dało się rozwiązać te zadanie bez binary search'a, a nawet jeśli to w nieoptymalnym czasie.
Zadanie samo w sobie jest zadaniem po temacie z wyszukiwania binarnego z pewniej książki, ale nie mam się zbytnio do kogo zwrócić po pomoc, a wskazówki w książce mówią tylko o użyciu sum prefiksowych oraz wyszukiwania binarnego.

Dlatego proszę o pomoc osoby z większym stażem w rozwiązywaniu tego typu problemów o wskazanie błędów logicznych w moim kodzie.

0

Napisałem bruta w O(n^2), ale nie wiem jak to zrobić z wyszukiwanem binarym

#include <bits/stdc++.h>
using namespace std;

int main() {
  int n;
  scanf("%d", &n);
  vector<int> t(n);
  vector<int> w(n);
  for(int i = 0; i < n; ++i) scanf("%d", &t[i]);
  for(int i = 0; i < n; ++i) scanf("%d", &w[i]);
  vector<int> sumy(n + 1);
  sumy[0] = 0;
  for(int i = 0; i < n; ++i) sumy[i + 1] = sumy[i] + t[i];
  for(int i = 0; i < n; ++i) {
    int r = 0;
    while(true) {
      int a = max(i - r, 0);
      int b = min(i + r + 1, n);
      int suma = sumy[b] - sumy[a];
      if (suma >= w[i]) {
        printf("%d ", r);
        break;
      }
      ++r;
      if (r >= n) {
        printf("%d ", -1);
        break;
      }
    }
  }
  printf("\n");
  return 0;
}

0

A Nie prościej było by dodawać do jakiejś tymczasowej zmiennej kolejnych liczb z lewej i prawej strony badanej? Moim zdaniem zdrowo przekombinowałeś. Dodatkowo przy wczytywaniu pierwszej tabeli warto sumować liczby, wszystko z drugiej co tą sumę przekroczy ma wynik -1 bez liczenia czegokolwiek.

0

Wyszukiwanie binarne zadziała.
Zmieniłem trochę funkcję check i wyszukiwanie binarne, ale idea została ta sama.

#include<cstdio>
#include<algorithm>
using namespace std;
/* test case
6
2 3 1 4 2 1
6 3 8 8 10 14

answer:
2 0 1 2 3 -1
*/
int t[1000006]; // wejscie
int w[1000006]; // wejscie

int sum[500001]; // tablica sum prefiksowych sum elementów
int n;

bool check(int position, int r)
{
    if(position - r - 1 >= 0)
    {
        if(sum[min(position + r, n - 1)] - sum[position - r - 1] >= w[position]) return true;
    }
    else
    {
        if(sum[min(position + r, n - 1)] >= w[position]) return true;
    }
    return false;
}

int bin(int position)
{
    int b = n;
    int a = 0;
    int r;
    int result = -1;
    while(b - a >1)
    {
        r = (a + b)/2;
        if(check(position, r))
        {
            b = r;
        }
        else
        {
            a = r;
        }
        if(check(position, r) && !check(position, r-1))
        {
            result = r;
        }
    }
    if(check(position, 0)) result = 0;
    return result;
}

int main()
{
    scanf("%d",&n);

    for(int i=0;i<n;++i)
        scanf("%d",&t[i]);

    sum[0]=t[0];

    for(int i=1;i<n;++i)
        sum[i]=sum[i-1]+t[i];

    for(int i=0;i<n;++i)
        scanf("%d",&w[i]);

    for(int i=0;i<n;++i)
       printf("%d\n",bin(i));

    return 0;
}

0

Nie chce mi się rozkminiać Twojego kodu, bo jest napisany kompletnie nieczytelnie. Za nazywanie zmiennych pojedynczymi literkami mogliby ucinać łapki…
1 - if(sum[min(x+r,n)]-sum[max(x-r,0)]>=w[x]) — tutaj sum[0] jest równe t[0], czyli w przypadku dużego promienia zawsze odejmiesz ten jeden element z początku, a tak chyba być nie powinno. W szczególności dla zerowego promienia masz if(sum[x] - sum[x]>=w[x]), czyli if(0>=w[x]) a to niemal na pewno babol.
2 - while(b-a>1)— ile ludzi, tyle implementacji wyszukiwania binarnego, więc nie wiem, czy ten warunek jest spójny z resztą pętli i nie wpadniesz w pętlę nieskończoną, ale zachęcam do upewnienia się
3 - napisz bruta, wygeneruj trochę losowych przypadków testowych i porównaj dwie implementacje

A jak chodzi o ideę algorytmu, to jest poprawna i powinna wystarczyć do rozwiązania zadania.

0

To jeszcze może ja wrzucę. Udało mi się przerobić tego bruta w O(n * log n)

#include <bits/stdc++.h>
using namespace std;

int main() {
  int n;
  scanf("%d", &n);
  vector<int> t(n);
  vector<int> w(n);
  for(int i = 0; i < n; ++i) scanf("%d", &t[i]);
  for(int i = 0; i < n; ++i) scanf("%d", &w[i]);
  vector<int> sumy(n + 1);
  sumy[0] = 0;
  for(int i = 0; i < n; ++i) sumy[i + 1] = sumy[i] + t[i];
  for(int i = 0; i < n; ++i) {
    int x = 0;
    int y = n;
    int wynik = -1;
    while(y - x > 1) {
      int r = (x + y) / 2;
      int a = max(i - r, 0);
      int b = min(i + r + 1, n);
      int suma = sumy[b] - sumy[a];
      if (suma >= w[i]) {
        y = r;
        wynik = r;
      } else {
        x = r;
      }
    }
    if (t[i] >= w[i]) wynik = 0;
    printf("%d ", wynik);
  }
  printf("\n");
  return 0;
}

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