Introdução

Muitos de vocês estão familiarizados com o algoritmo de classificação por mesclagem para classificar uma lista de números. Como parte do algoritmo, escreve-se uma função auxiliar chamada mergeque combina duas listas classificadas em uma lista classificada. No pseudocódigo do tipo Python, a função geralmente se parece com isso:

function merge(A, B):
  C = []
  while A is not empty or B is not empty:
    if A is empty:
      C.append(B.pop())
    else if B is empty or A[0] ≤ B[0]:
      C.append(A.pop())
    else:
      C.append(B.pop())
  return C

A idéia é continuar aparecendo o menor dos primeiros elementos de Ae Baté que ambas as listas estejam vazias e coletar os resultados C. Se Ae Bsão ambos classificados, então o é C.

Por outro lado, se Cé uma lista ordenada, e dividi-lo em quaisquer duas subseqüências Ae B, em seguida, Ae Btambém são ordenadas e merge(A, B) == C. Curiosamente, isso não é necessariamente válido se Cnão for classificado, o que nos leva a esse desafio.

Entrada

Sua entrada é uma permutação dos primeiros 2*nnúmeros inteiros não negativos [0, 1, 2, ..., 2*n-1]para alguns n > 0, fornecidos como uma lista C.

Resultado

Sua saída será um valor verdadeiro, se houver duas listas Ae Bde comprimento ntal que C == merge(A, B), e um valor falso, caso contrário. Como a entrada não contém duplicatas, você não precisa se preocupar com a quebra de vínculos na mergefunção.

Regras e Bônus

Você pode escrever uma função ou um programa completo. A contagem de bytes mais baixa vence e as brechas padrão não são permitidas.

Observe que você não precisa calcular as listas Ae Bnas instâncias "yes". No entanto, se você realmente produzir as listas, receberá um bônus de -20% . Para reivindicar esse bônus, você deve gerar apenas um par de listas, nem todas as possibilidades. Para tornar esse bônus mais fácil de reivindicar em idiomas fortemente tipados, é permitido gerar um par de listas vazias nas instâncias "no".

A força bruta não é proibida, mas há um bônus de -10% para o cálculo de todos os quatro últimos casos de teste em menos de 1 segundo no total.

Casos de teste

Somente uma saída possível é fornecida nas instâncias "yes".

[1,0] -> False
[0,1] -> [0] [1]
[3,2,1,0] -> False
[0,3,2,1] -> False
[0,1,2,3] -> [0,1] [2,3]
[1,4,0,3,2,5] -> False
[4,2,0,5,1,3] -> [4,2,0] [5,1,3]
[3,4,1,2,5,0] -> [4,1,2] [3,5,0]
[6,2,9,3,0,7,5,1,8,4] -> False
[5,7,2,9,6,8,3,4,1,0] -> False
[5,6,0,7,8,1,3,9,2,4] -> [6,0,8,1,3] [5,7,9,2,4]
[5,3,7,0,2,9,1,6,4,8] -> [5,3,7,0,2] [9,1,6,4,8]
[0,6,4,8,7,5,2,3,9,1] -> [8,7,5,2,3] [0,6,4,9,1]
[9,6,10,15,12,13,1,3,8,19,0,16,5,7,17,2,4,11,18,14] -> False
[14,8,12,0,5,4,16,9,17,7,11,1,2,10,18,19,13,15,6,3] -> False
[4,11,5,6,9,14,17,1,3,15,10,12,7,8,0,18,19,2,13,16] -> [4,17,1,3,15,10,12,7,8,0] [11,5,6,9,14,18,19,2,13,16]
[9,4,2,14,7,13,1,16,12,11,3,8,6,15,17,19,0,10,18,5] -> [9,4,2,16,12,11,3,8,6,15] [14,7,13,1,17,19,0,10,18,5]

Pitão, 39 * 0,9 * 0,8 = 28,08

#aY->QxQeS-QsY&YsY)KfqylTlQmsdty_Y%tlKK

Este programa contém todos os dois bônus. Ele imprime um par de listas, se for possível a mesclagem, ou uma lista vazia, que é um valor falso no Pyth (e Python).

Input:  [5,3,7,0,2,9,1,6,4,8]
Output: ([9, 1, 6, 4, 8], [5, 3, 7, 0, 2])
Input:  [5,7,2,9,6,8,3,4,1,0]
Output: [] (falsy value)

Você pode testá-lo online , mas pode ser um pouco mais lento que a versão offline. A versão offline resolve cada um dos casos de teste em <0,15 segundo no meu laptop.

Provavelmente (uma das) pela primeira vez, uma solução Pyth usa ativamente exceções (salvou pelo menos 1 caractere). Ele usa a mesma idéia que a solução de Peter Taylor.

                         preinitialisations: Q = input(), Y = []
#                 )     while 1: (infinite loop)
        eS-QsY             finds the biggest, not previous used, number
      xQ                   finds the index
    >Q                     all elements from ... to end
   -          &YsY         but remove all used elements
 aY                        append the resulting list to Y

When all numbers are used, finding the biggest number fails, 
throws an exception and the while loop ends.  
This converts [5,3,7,0,2,9,1,6,4,8] to [[9, 1, 6, 4, 8], [7, 0, 2], [5, 3]]

        msdty_Y  combine the lists each for every possible subset of Y (except the empty subset)
 fqylTlQ         and filter them for lists T with 2*len(T) == len(Q)
K                and store them in K

%tlKK        print K[::len(K)-1] (prints first and last if K, else empty list)

Pitão, 30 * 0,9 = 27,0

Eu realmente não tentei resolvê-lo sem imprimir as listas resultantes. Mas aqui está uma solução rápida com base no código acima.

#aY->QxQeS-QsY&YsY)fqylsTlQtyY

Basicamente, apenas removi a declaração de impressão. A saída é bastante feia.

Input:  [0,1,2,3]
Output: [[[3], [2]], [[3], [1]], [[2], [1]], [[3], [0]], [[2], [0]], [[1], [0]]] (truthy value)
Input:  [5,7,2,9,6,8,3,4,1,0]
Output: [] (falsy value)

Experimente online .

GolfScript (35 * 0,9 = 31,5)

{.$-1>/~,)\.}do;]1,\{{1$+}+%}/)2/&,

A demonstração on-line é bastante lenta: no meu computador, ele executa todos os testes em menos de 0,04 segundos, então reivindico a redução de 10%.

Explicação

O sufixo de C, que começa com o maior número em C, deve vir da mesma lista. Em seguida, esse raciocínio pode ser aplicado a (sufixo C), para que o problema se reduz à soma do subconjunto.

APL, 62 50 44 * 90% = 39,6

{(l÷2)⌷↑(⊢∨⌽)/(2-/(1,⍨⍵≥⌈\⍵)/⍳l+1),⊂l=⍳l←⍴⍵}

Experimente aqui.