Wprowadzenie

W tym wyzwaniu Twoim zadaniem jest zdecydować, czy daną sekwencję liczb można podzielić na dwie podsekwencje, z których jedna rośnie, a druga maleje. Jako przykład rozważ sekwencję 8 3 5 5 4 12 3. Można go podzielić na dwa podsekwencje w następujący sposób:

  3 5 5   12
8       4    3

Podsekwencja w pierwszym rzędzie rośnie, a ta w drugim rzędzie maleje. Ponadto powinieneś wykonywać to zadanie skutecznie.

Wejście

Wprowadzono niepustą listę Lliczb całkowitych z zakresu od 0 do 99999 włącznie. Jest podawany w natywnym formacie Twojego języka lub po prostu rozdzielany spacjami.

Wynik

Twój wynik jest prawdziwą wartością, jeśli Lmożna go podzielić na rosnącą i malejącą podsekwencję, a fałszem w przeciwnym razie. Podsekwencje nie muszą być ściśle zwiększane lub zmniejszane, a każda z nich może być pusta.

Zasady i bonusy

Możesz napisać pełny program lub funkcję. Wygrywa najniższa liczba bajtów, a standardowe luki są niedozwolone. Ponadto brutalne wymuszanie jest zabronione w tym wyzwaniu: twój program musi działać w czasie wielomianowym na długości danych wejściowych .

Nie musisz faktycznie zwracać dwóch podsekwencji, ale jest za to premia w wysokości -20% . Aby ułatwić ubieganie się o bonus w językach o typie statycznym, dopuszczalne jest zwrócenie pary pustych list dla instancji fałszywych.

Przypadki testowe

Podany w formacie input -> Nonedla danych wejściowych fałszerstwa i input -> inc decdanych autentycznych. Podana jest tylko jedna możliwa para podsekwencji; może być więcej.

[4,9,2,8,3,7,4,6,5] -> None
[0,99999,23423,5252,27658,8671,43245,53900,22339] -> None
[10,20,30,20,32,40,31,40,50] -> None
[49,844,177,974,654,203,65,493,844,767,304,353,415,425,857,207,871,823,768,110,400,710,35,37,88,587,254,680,454,240,316,47,964,953,345,644,582,704,373,36,114,224,45,354,172,671,977,85,127,341,268,506,455,6,677,438,690,309,270,567,11,16,725,38,700,611,194,246,34,677,50,660,135,233,462,777,48,709,799,929,600,297,98,39,750,606,859,46,839,51,601,499,176,610,388,358,790,948,583,39] -> None
[0,1,2,3,4] -> [0,1,2,3,4] []
[4,3,2,1,0] -> [] [4,3,2,1,0]
[1,9,2,8,3,7,4,6,5] -> [1,2,3,4,6] [9,8,7,5]
[71414,19876,23423,54252,27658,48671,43245,53900,22339] -> [19876,23423,27658,48671,53900] [71414,54252,43245,22339]
[10,20,30,20,30,40,30,40,50] -> [10,20,20,30,40,40,50] [30,30]
[0,3,7,13,65,87,112,43,22,1] -> [0,3,7,13,65,87,112] [43,22,1]
[7,4,4,7,4,7,7,4,7,4,4,4,7,7] -> [7,7,7,7,7,7,7] [4,4,4,4,4,4,4]
[7,997,991,957,956,952,7,8,21,924,21,923,22,38,42,44,920,49,58,67,71,83,84,85,917,89,907,896,878,878,90,861,115,860,125,128,140,148,858,155,160,836,164,182,826,191,824,805,195,792,205,782,206,210,769,213,756,748,214,745,724,701,234,241,693,268,685,293,679,297,334,671,336,669,341,652,356,648,362,364,370,375,386,630,622,388,389,618,398,408,468,615,470,533,611,539,544,609,586,582,572,565,547,602,536,619,624,528,512,631,640,649,669,671,677,505,678,723,743,489,489,473,454,757,446,445,758,759,764,445,431,770,429,426,418,409,790,383,379,366,363,791,358,795,809,827,835,356,353,841,844,333,867,323,317,879,311,881,309,896,282,281,897,263,904,237,236,226,202,195,914,186,177,917,920,157,926,936,154,138,943,131,945,100,98,947,957,964,95,973,989,57,43,32,21,16,13,11,8,0] -> [7,7,8,21,21,22,38,42,44,49,58,67,71,83,84,85,89,90,115,125,128,140,148,155,160,164,182,191,195,205,206,210,213,214,234,241,268,293,297,334,336,341,356,362,364,370,375,386,388,389,398,408,468,470,533,539,544,586,602,619,624,631,640,649,669,671,677,678,723,743,757,758,759,764,770,790,791,795,809,827,835,841,844,867,879,881,896,897,904,914,917,920,926,936,943,945,947,957,964,973,989] [997,991,957,956,952,924,923,920,917,907,896,878,878,861,860,858,836,826,824,805,792,782,769,756,748,745,724,701,693,685,679,671,669,652,648,630,622,618,615,611,609,582,572,565,547,536,528,512,505,489,489,473,454,446,445,445,431,429,426,418,409,383,379,366,363,358,356,353,333,323,317,311,309,282,281,263,237,236,226,202,195,186,177,157,154,138,131,100,98,95,57,43,32,21,16,13,11,8,0] 

Pyth, 34 bajty

.N|!N|&ghNT:tNhNY&gYhN:tNThN:QZ^T5

Pakiet testowy

Używa zapamiętanej rekurencji, aby utrzymać czas działania w dół. Definiuje funkcję 3 wejściową :, która pobiera sufiks listy wejść, koniec sekwencji wzrastającej, koniec sekwencji malejącej.

Brachylog , 16 bajtów - 20% = 12,8 (ale prawie na pewno nie jest wielomianowy)

⊇≥₁X&⊇≤₁Y;X.cp?∧

Wypróbuj online!

Nie powiedzie się, jeśli nie ma pary zgodnych podsekwencji i wyprowadza je przez zmienną wyjściową, jeśli istnieje (ale po prostu wypisze, true.jeśli zostanie uruchomiona jako program). Mówię, że prawie na pewno nie jest wielomianem, ponieważ piękno Brachylog polega na tym, że ponieważ jest to język deklaratywny, nie robisz tak wiele w implementacji algorytmu, jak po prostu opisując relacje między zmiennymi i prosząc komputer o wyodrębnienie wyników . Są więc szanse, że to hardcorowa brutalna siła, ale spędziłem wystarczająco dużo czasu na wklejaniu przypadków testowych (z których dwa właśnie się skończyły), że czuję, że powinienem to mimo wszystko przesłać, jeśli nie z innego powodu niż przeciągnięcie tego wyzwania w górę z tyłu listy „Najmłodszych” problemów decyzyjnych .

   X                X is a
 ≥₁                 non-increasing
⊇                   sublist of the input
    &               and
        Y           Y is a
      ≤₁            non-decreasing
     ⊇              sublist of the input
         ;X         which paired with X
           .        is the output variable
            c       which when its elements are concatenated
             p      is a permutation of
              ?     the input
               ∧    which is not unified with the output.

Haskell , 65 bajtów

(>[]).foldl(%)[(0,9^6)]
p%x=do(u,d)<-p;[(x,d)|x>=u]++[(u,x)|x<=d]

Wypróbuj online!

Iteruje po liście, śledząc możliwe pary (u,d)maks. Sekwencji rosnącej i min sekwencji malejącej. Każdy nowy element xzastępuje jeden ulub d, co odpowiada dołączeniu do tego podsekwencji. Możliwe, że obie opcje lub żadna z nich nie jest poprawna. Na koniec sprawdzamy, czy lista możliwości nie jest pusta.

Początkowe granice (0,9^6)wykorzystywać że problem określa numery się w zakresie 0 - 99999. bardziej ogólne rozwiązanie może zrobić (1/0,-1/0)do marek (-inf,inf).