14
\$\begingroup\$

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]
\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ You may find that rather than printing (K[0], Q-K[0]) you can print (K[0], K[-1]). I don't know whether that would give a saving, though. \$\endgroup\$ – Peter Taylor Mar 12 '15 at 10:17
  • \$\begingroup\$ @PeterTaylor thanks, saved 2 chars. \$\endgroup\$ – Jakube Mar 12 '15 at 10:32
  • \$\begingroup\$ @PeterTaylor and even 2 more chars, if I print K[::len(K)-1]. \$\endgroup\$ – Jakube Mar 12 '15 at 10:38
4
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

APL, 62 50 44 * 90% = 39.6

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

Try it here.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.