Un-Merge a List

Question

Introduction

Most of you are familiar with the merge sort algorithm for sorting a list of numbers. As part of the algorithm, one writes a helper function called merge that combines two sorted lists into one sorted list. In Python-like pseudocode, the function usually looks something like this:

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

The idea is to keep popping the smaller of the first elements of A and B until both lists are empty, and collect the results into C. If A and B are both sorted, then so is C.

Conversely, if C is a sorted list, and we split it into any two subsequences A and B, then A and B are also sorted and merge(A, B) == C. Interestingly, this does not necessarily hold if C is not sorted, which brings us to this challenge.

Input

Your input is a permutation of the first 2*n nonnegative integers [0, 1, 2, ..., 2*n-1] for some n > 0, given as a list C.

Output

Your output shall be a truthy value if there exist two lists A and B of length n such that C == merge(A, B), and a falsy value otherwise. Since the input contains no duplicates, you don't have to worry about how ties are broken in the merge function.

Rules and Bonuses

You can write either a function or a full program. The lowest byte count wins, and standard loopholes are disallowed.

Note that you are not required to compute the lists A and B in the "yes" instances. However, if you actually output the lists, you receive a bonus of -20%. To claim this bonus, you must output only one pair of lists, not all possibilities. To make this bonus easier to claim in strongly typed languages, it is allowed to output a pair of empty lists in the "no" instances.

Brute forcing is not forbidden, but there is a bonus of -10% for computing all of the last four test cases in under 1 second total.

Test Cases

Only one possible output is given in the "yes" instances.

[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]

Answer 1

GolfScript (35 * 0.9 = 31.5)

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

The online demo is quite slow: on my computer, it runs all of the tests in under 0.04 seconds, so I claim the 10% reduction.

Explanation

The suffix of C which starts with the largest number in C must come from the same list. Then this reasoning can be applied to (C - suffix), so that the problem reduces to subset sum.

Answer 2

Pyth, 39 * 0.9 * 0.8 = 28.08

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

This program clams all two bonuses. It prints a pair of lists, if un-merging is possible, else an empty list, which is a falsy value in Pyth (and 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)

You can test it online, but it may be a bit slower than the offline version. The offline version solves each of the test cases in <0.15 seconds on my laptop.

Probably (one of) the first time, a Pyth solution uses actively Exceptions (it saved at least 1 char). It uses the same idea as Peter Taylor's solution.

                         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

I haven't really tried solving it without printing the resulting lists. But here's a quick solution based on the code above.

#aY->QxQeS-QsY&YsY)fqylsTlQtyY

I basically only removed the print statement. The output is quite ugly though.

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)

Try it online.

Answer 3

APL, 62 50 44 * 90% = 39.6

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

Try it here.

Answer 4

JavaScript (Node.js), 103 bytes * 0.9 * 0.8

f=(x,u,a=[],b=[],y=[...x],c=y.pop())=>b[0]<a[0]?0:1/c?f(y,~-u,[c,...a],b)||f(y,~u,[c,...b],a):u?0:[a,b]

Try it online!

JavaScript (Node.js), 105 bytes * 0.9 * 0.8

f=(x,u=0,a=[],b=[],y=[...x],c=y.pop())=>b[0]<a[0]?0:1/c?f(y,u-1,[c,...a],b)||f(y,~u,[c,...b],a):u?0:[a,b]

Try it online!

JavaScript (Node.js), 115 bytes * 0.9 * 0.8

f=(x,u=0,a=[],b=[],y=[...x],c=y.pop())=>1/c?!(b[0]<c)&&f(y,u-1,[c,...a],b)||!(a[0]<c)&&f(y,~u,[c,...b],a):u?0:[a,b]

Try it online!