2016-05-30 10 views
15

oryginalny problem:

Słowo było K-dobre, jeśli dla każdych dwóch liter w słowie, gdy po raz pierwszy pojawia x razy, a druga pojawia y razy, następnie |x - y| ≤ K.

Minimalna znaków, który musiał być usunięty

Podane słowo w, ile liter musi usunąć, aby K-dobre?
Problem Link.

Mam rozwiązać powyższy problem i nie pytając rozwiązanie dla powyższego problemu

Właśnie misread oświadczenie po raz pierwszy i tylko myśli, jak możemy rozwiązać ten problem w liniowym czasie linia, który właśnie doprowadzić do nowego problemu



modyfikacja problemu

słowo było K-dobry jeśli dla każdych dwoma kolejnymi literami w słowie, gdy po raz pierwszy pojawia x razy, a druga pojawia y razy, potem |x - y| ≤ K.

Biorąc pod uwagę pewne słowa w, ile liter nie musiał usunąć, aby go K -dobry?

Czy ten problem jest rozwiązywany w czasie liniowym, myślałem o tym, ale nie mogłem znaleźć żadnego prawidłowego rozwiązania.

Rozwiązanie

moje podejście: nie mogłem podejść mój zgniatać ale jej jest moje podejście do tego problemu, spróbować wszystkiego (od filmowego Zooptopia)

tj

for i range(0,1<<n): // n length of string 
    for j in range(0,n): 
      if(i&(1<<j) is not zero): delete the character 
    Now check if String is K good 

Dla N w zakresie 10^5. Złożoność czasu: czas nie istnieje w tym wymiarze.

Czy istnieje liniowe rozwiązanie tego problemu, proste i słodkie, jak ludzie o stackoverflow.

For Ex: 
String S = AABCBBCB and K=1 


    If we delete 'B' at index 5 so String S = AABCBCB which is good string 
    F[A]-F[A]=0 
    F[B]-F[A]=1 
    F[C]-F[B]=1 
    and so on 

to chyba prosty przykład nie może mi bardziej złożony przykład jako usunięcie elementu I makens (i-1) i (i + 1), a z kolei

+0

Czy możesz podać przykład zmodyfikowanego problemu? –

+2

Czy możesz żyć z rozwiązaniem o złożoności = O (n^2)? – AnotherGeek

Odpowiedz

2

jest jakiś liniowe rozwiązanie tego problemu?

Rozważ słowo DDDAAABBDC. To słowo jest 3-dobre, ponieważ D i C są następujące po sobie i card(D)-card(C)=3, a usunięcie ostatniego D czyni je 1-dobrym, powodując, że D i nie są kolejne.

Odwrotnie, jeśli wziąć pod uwagę DABABABBDC, którym jest 2-dobre usuwanie ostatni D sprawia C i B rzędu i zwiększa wartość K słowa do 3.

Oznacza to, że w zmodyfikowanej problemu K - wartość słowa określają zarówno kardynałowie każdej litery, jak i kardynałowie każdej pary kolejnych liter.

Usuwając list, redukuję jego kardynała, jak również kardynałów z par, do których on należy, ale także zwiększam liczbę kardynalną innych par (potencjalnie tworząc nowe).

Należy również zauważyć, że w oryginalnym problemie wszystkie litery są równoważne (mogę je usunąć obojętnie), podczas gdy nie ma to już miejsca w zmodyfikowanym problemie.

Podsumowując, uważam, że możemy bezpiecznie założyć, że ograniczenie "kolejnych liter" sprawia, że ​​problem nie jest rozwiązywany w liniowym czasie dla dowolnego alfabetu/słowa.

+0

Chociaż to nie jest odpowiedź, myślę, że masz rację. Zastanawiam się nad tym pytaniem, a poza algorytmem brutalnej siły z niewielkim przycinaniem, nie widzę eleganckiej ani wydajnej odpowiedzi na ten problem. – m69

+0

Muszę przyznać, że nie szukałem najlepszego sposobu rozwiązania problemu, ale starałem się odpowiedzieć na pytanie "Czy istnieje jakieś rozwiązanie liniowe tego problemu". Nawet wtedy moja odpowiedź nie jest formalnym dowodem (ponieważ prawdopodobnie musiałbym wprowadzić pewne definicje), ale myślę, że nadal działa, ponieważ można pokazać, że nie można iterować "części" swojego algorytmu za pomocą taki sam stopień złożoności, jak w pierwotnym problemie (zazwyczaj dlatego, że są splecione ze względu na kolejne ograniczenie). – OB1

1

Zamiast znalezienia rozwiązania liniowego czasu, co moim zdaniem nie istnieje (między innymi dlatego, że wydają się być mnóstwo alternatywnych rozwiązań dla każdego żądania K), chciałbym aby zaprogramować całkowicie geeky rozwiązanie.

Mianowicie, podejmują równoległego przetwarzania języka tablica Dyalog APL i utworzyć te dwie małe funkcje dynamiczne:

good←{1≥⍴⍵:¯1 ⋄ b←(⌈/a←(∪⍵)⍳⍵)⍴0 ⋄ b[a]+←1 ⋄ ⌈/|2-/b[a]} 

make←{⍵,(good ⍵),a,⍺,(l-⍴a←⊃b),⍴b←(⍺=good¨b/¨⊂⍵)⌿(b←↓⍉~(l⍴2)⊤0,⍳2⊥(l←⍴⍵)⍴1)/¨⊂⍵} 

dobry mówi nam K-dobroć sznurku. Kilka przykładów poniżej:

// fn" means the fn executes on each of the right args 
good" 'AABCBBCB' 'DDDAAABBDC' 'DDDAAABBC' 'DABABABBDC' 'DABABABBC' 'STACKOVERFLOW' 
2 3 1 2 3 1 

aby której argumentami

[desired K] make [any string] 

i zwraca
- pierwotny łańcuch
- K za oryginalnym łańcuchem znaków
- zmniejszone łańcuch o wymaganej K
- ile znaków zostało usuniętych, aby osiągnąć pożądane K
- ile to możliwe Roztwory le są w celu uzyskania żądanej K

Na przykład

3 make 'DABABABBDC' 
┌──────────┬─┬─────────┬─┬─┬──┐ 
│DABABABBDC│2│DABABABBC│3│1│46│ 
└──────────┴─┴─────────┴─┴─┴──┘ 

Jeszcze trochę wyrażenie:

1 make 'ABCACDAAFABBC' 
┌─────────────┬─┬────────┬─┬─┬────┐ 
│ABCACDAAFABBC│4│ABCACDFB│1│5│3031│ 
└─────────────┴─┴────────┴─┴─┴────┘ 

możliwe jest zarówno zwiększenie jak i zmniejszenie K dobroci.

Niestety, to jest brutalna siła.Generujemy 2-podstawy wszystkich liczb od 2^[długość łańcucha] i 1, na przykład:

0 1 0 1 1 

Następnie test dobroć fragmentu, na przykład:

0 1 0 1 1/'STACK' // Substring is now 'TCK' 

Wybieramy tylko te wyniki (podłańcuchy), które pasują do pożądanego K-dobra. Wreszcie, spośród mnóstwa możliwych wyników wybieramy pierwszą, która zawiera większość znaków.

Przynajmniej było fajnie kodować :-).

+0

Nie spoczniesz, dopóki cały świat nie zostanie przetworzony równolegle, dobrze? :-P – m69

+0

Heheh. Nie widzisz, że po prostu gromadzę siły na następną wielką fazę deweloperską ... i mam problemy z rozpoczęciem :-). Ale wkrótce skrócę sobie :-). – Stormwind