Google Code Jam Qualification Round Africa 2010, Revisited

March 26, 2013

We begin with the O(n2) time and O(1) space solution, stated somewhat differently than the previous solution, just for variety. The call-with-current-continuation is the Scheme idiom that permits an early return from a function; the function returns #f if there is no solution:

(define (soln1 target vec)
  (let ((len (vector-length vec)))
    (call-with-current-continuation
      (lambda (return)
        (do ((i 0 (+ i 1))) ((= i len) #f)
          (do ((j (+ i 1) (+ j 1))) ((= j len))
            (when (= target (+ (vector-ref vec i) (vector-ref vec j)))
              (return (list (+ i 1) (+ j 1))))))))))

Our second solution uses the avl trees from the Standard Prelude. We have to be careful not to take the same item twice if two items have the same value. Note that we add 1 to the position on input instead of output:

(define (soln2 target xs)
  (let ((items (make-dict <)))
    (do ((i 0 (+ i 1)) (xs xs (cdr xs))) ((null? xs))
      (set! items (items 'insert (car xs) (+ i 1))))
    (let loop ((xs xs) (i 1))
      (cond ((null? xs) #f)
            ((items 'lookup (- target (car xs))) =>
              (lambda (item)
                (if (= i (cdr item))
                    (loop (cdr xs) (+ i 1))
                    (sort < (list i (cdr item))))))
            (else (loop (cdr xs) (+ i 1)))))))

The third solution is similar to the second, but uses the hash tables of the Standard Prelude instead of avl trees:

(define (soln3 target xs)
  (let ((items (make-hash identity = #f 97)))
    (do ((i 0 (+ i 1)) (xs xs (cdr xs))) ((null? xs))
      (items 'insert (car xs) (+ i 1)))
    (let loop ((xs xs) (i 1))
      (cond ((null? xs) #f)
            ((items 'lookup (- target (car xs))) =>
              (lambda (item)
                (if (= i item)
                    (loop (cdr xs) (+ i 1))
                    (sort < (list i item)))))
            (else (loop (cdr xs) (+ i 1)))))))

The fourth solution requires a little bit more work. First a vector of value/position pairs is build, then i iterates through the vector, performing a binary search on the portion of the vector from i+1 to the end for a value of the target less the value portion of i. There is no need to check for duplicate positions, because the search vector starts at position i+1; for the same reason, it is necessary to add 2 to i and 1 to the position found in the vector.

(define (soln4 target xs)
  (define (comp a b)
    (if (< (car a) (car b)) -1
    (if (< (car b) (car a)) 1 0)))
  (define (bsearch target vec lo hi)
    (if (< hi lo) #f
      (let ((mid (quotient (+ lo hi) 2)))
        (cond ((< (car (vector-ref vec mid)) target)
                (bsearch target vec (+ mid 1) hi))
              ((< target (car (vector-ref vec mid)))
                (bsearch target vec lo (- mid 1)))
              (else (vector-ref vec mid))))))
  (let loop ((xs xs) (i 0) (vs (list)))
    (if (pair? xs)
        (loop (cdr xs) (+ i 1) (cons (cons (car xs) i) vs))
        (let ((vec (list->vector vs)))
          (vector-sort! vec comp)
          (let ((len (vector-length vec)))
            (let loop ((i 0))
              (cond ((= i len) #f)
                    ((bsearch (- target (car (vector-ref vec i)))
                              vec (+ i 1) (- len 1)) =>
                      (lambda (item)
                        (sort < (list (+ i 2) (+ (cdr item) 1)))))
                    (else (loop (+ i 1))))))))))

I really like this solution. Though it looks complicated, there is an underlying elegance that I find appealing. And there isn’t much difference between O(n) and O(n log n) unless n gets really large, and the space requirement of the O(n) solution effectively prevents n from getting really large.

You can run the program at http://programmingpraxis.codepad.org/hfZCy20U.

About these ads

Pages: 1 2

One Response to “Google Code Jam Qualification Round Africa 2010, Revisited”

  1. Anonymous said

    I tried solving the problem with a binary search tree and checking for the conjugate. I realized that there is a problem though when there are items of the same price.

    The key value pair for a tree would be the item price and the item position. If there are two items with the same price then we have duplicate keys!

    From the provided example we have L={2,1,9,4,4,56,90,3} which would cause a problem when turned into a tree. A solution to this problem could be to have key value pairs of item price and a list of positions. Extra work would be required to keep a complexity of O(nlogn) when building this new tree.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 576 other followers

%d bloggers like this: