Introducción

La mayoría de ustedes está familiarizado con el algoritmo de clasificación de fusión para ordenar una lista de números. Como parte del algoritmo, se escribe una función auxiliar llamada mergeque combina dos listas ordenadas en una lista ordenada. En el pseudocódigo similar a Python, la función generalmente se ve así:

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

La idea es seguir haciendo aparecer el primer elemento más pequeño de Ay Bhasta que ambas listas estén vacías, y recopilar los resultados C. Si Ay Bestán ambos ordenados, entonces también lo está C.

Por el contrario, si Ces una lista ordenada, y dividirlo en dos subsecuencias Ay B, a continuación, Ay Btambién se ordenan y merge(A, B) == C. Curiosamente, esto no se cumple necesariamente si Cno se clasifica, lo que nos lleva a este desafío.

Entrada

Su entrada es una permutación de los primeros 2*nenteros no negativos [0, 1, 2, ..., 2*n-1]para algunos n > 0, dada como una lista C.

Salida

Su salida será un valor verdadero si existen dos listas Ay Bde longitud ntal que C == merge(A, B), y un valor falso de lo contrario. Como la entrada no contiene duplicados, no tiene que preocuparse por cómo se rompen los lazos en la mergefunción.

Reglas y bonos

Puede escribir una función o un programa completo. El conteo de bytes más bajo gana, y las lagunas estándar no se permiten.

Tenga en cuenta que no es necesario que calcule las listas Ay Ben las instancias de "sí". Sin embargo, si realmente genera las listas, recibirá una bonificación de -20% . Para reclamar este bono, debe generar solo un par de listas, no todas las posibilidades. Para hacer que este bono sea más fácil de reclamar en idiomas fuertemente tipados, está permitido generar un par de listas vacías en las instancias "no".

El forzamiento bruto no está prohibido, pero hay una bonificación de -10% para calcular los últimos cuatro casos de prueba en menos de 1 segundo en total.

Casos de prueba

Solo se da una salida posible en las instancias "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]

Pyth, 39 * 0.9 * 0.8 = 28.08

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

Este programa reclama las dos bonificaciones. Imprime un par de listas, si es posible deshacer la fusión, de lo contrario, una lista vacía, que es un valor falso en Pyth (y 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)

Puede probarlo en línea , pero puede ser un poco más lento que la versión sin conexión. La versión sin conexión resuelve cada uno de los casos de prueba en <0,15 segundos en mi computadora portátil.

Probablemente (una de) la primera vez, una solución Pyth usa Excepciones activamente (ahorró al menos 1 carácter). Utiliza la misma idea que la solución 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)

Pyth, 30 * 0.9 = 27.0

Realmente no he intentado resolverlo sin imprimir las listas resultantes. Pero aquí hay una solución rápida basada en el código anterior.

#aY->QxQeS-QsY&YsY)fqylsTlQtyY

Básicamente, solo eliminé la declaración de impresión. Sin embargo, la salida es bastante fea.

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)

Pruébalo en línea .

GolfScript (35 * 0.9 = 31.5)

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

La demostración en línea es bastante lenta: en mi computadora, ejecuta todas las pruebas en menos de 0.04 segundos, por lo que reclamo la reducción del 10%.

Explicación

El sufijo de C que comienza con el mayor número en C debe provenir de la misma lista. Entonces este razonamiento puede aplicarse a (sufijo C), de modo que el problema se reduzca a la suma del subconjunto.

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

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

Pruébalo aquí.