Panel użytkownika
Nazwa użytkownika:
Hasło:
Nie masz jeszcze konta?

Statyczne drzewo binarne i najdłuższy nieprzerwany ciąg

Ostatnio zmodyfikowano 2018-03-07 12:39
Autor Wiadomość
pekfos
» 2018-03-06 21:42:31
Niczego nie wniosłeś tym zdaniem. Pytanie było inne.
P-169819
DejaVu
» 2018-03-06 22:04:59
Kombinuj samodzielnie nad rozwiązaniem. Sporo podpowiedzi otrzymałeś.
P-169820
darko202
» 2018-03-07 12:39:47
1.

naiwne sprawdzanie ciągu przekroczy limity czasu w sprawdzarce bo wtedy tak naprawdę jest to O(n*k)
nie podałeś linijki kodu, dlatego trudno się do tego odnieść
opublikuj Twój kod - daj szansę wskazać błędy w myśleniu

2.
przeczytałem jeszcze raz założenia :
1 wiersz dwie liczby (n k)
n (5 <= n <= 500 000) długość ciągu zerojedynkowego
k (1 <= k <= 200 000) liczbę zmian
2 wiersz ciąg zerojedynkowy
kolejne linie pozycja zmiany w ciągu z wiersza 2
Dostępna pamięć: 64MB.

Podpowiedź: dla określonego przedziału w ciągu zerojedynkowym zapamiętuj jaki jest najdłuższy nieprzerwany
ciąg zer od lewej i od prawej strony.


czy istnieje algorytm o mniejszej złożoności od algorytmu :
* wprowadzasz zmianę do kontenera przechowującej ciąg
  tego nie da się zmienić - krok konieczny
* wywołujesz ww. funkcję
  ilość kroków zależy od tego jak napiszemy tą funkcję :)
  (tu widzę, że zmieniłbym zaproponowaną funkcję  DlugoscCiagu()  - wejście i wyjście 

jeśli skorzystajmy z podpowiedzi:
* wiem jaki jest "największy ciąg 0" 
* zmieniamy np 17 pozycję :
   jeśli na 0 - to sprawdzamy
        jeśli ( (ile 0 z lewej) + 1 +  (ile 0 z lewej))  > ( "największy ciąg 0")
           to zmieniamy "największy ciąg 0"
   jeśli na 1 to przedział w którym było 0 podzielił się na dwa mniejsze
      problemem może być tylko wtedy jeśli zmieni się ten najdłuższy przedział
      tu coś dodatkowego muszę o nim wiedzieć tzn. gdzie leży ten ciąg
      i jeśli tak to trzeba brutalnie znowu znaleźć taki ciąg
     
    "chyba że ... ? ... chyba że ... ?"  (jak to mówił król Julian)
  będziemy mieli np. drzewo z takimi informacjami
  (bo drzewa mają takie zalety, że z algorytmu O(N) czasami robią algorytm O(Log(N)) )
:)
który zbudujemy w trakcie czytania ciągu i będziemy modyfikować po każdej zmianie.
? czy wydatek jednak opłaca się - statystycznie  

jest to na pewno mniej kroków,

co do złożoności ?
postawiłbym na O(N log(N)),
ale nie założyłbym się o to :)
                
3.
czy kontenerem przechowującym dane o ciągu może być drzewo ?
tak, można sobie cos takiego stworzyć.
gałęzie zawierają informacje na temat ilości 0

problemem jest jednak dostęp (nie wiemy w jednym kroku gdzie znajduje się dany element ciągu)
ale po Log(N) krokach możemy się do niego dostać

czyli to raczej zwiększa ilość kroków algorytmu.
nie jest też łatwiej znaleźć najdłuższy ciąg 0.

4.
we wskazanym linku do problemu jest "konkurs-podstaw-algorytmiki",
https://main2.edu.pl/c​/konkurs-podstaw-algorytmiki/p​/zer3/

byłoby co najmniej nieelegancko wobec innych uczestników,
gdybyśmy rozwiązywali wszystkie problemy za Ciebie.
P-169824
1 « 2 »
Poprzednia strona Strona 2 z 2