Google Code Jam 2016 Round 1A Problem B in J language

When Sergeant Argus's army assembles for drilling, they stand in the shape of an N by square grid, with exactly one soldier in each cell. Each soldier has a certain height.

Argus believes that it is important to keep an eye on all of his soldiers at all times. Since he likes to look at the grid from the upper left, he requires that:

  • Within every row of the grid, the soldiers' heights must be in strictly increasing order, from left to right.
  • Within every column of the grid, the soldiers' heights must be in strictly increasing order, from top to bottom.

Although no two soldiers in the same row or column may have the same height, it is possible for multiple soldiers in the grid to have the same height.

Since soldiers sometimes train separately with their row or their column, Argus has asked you to make a report consisting of 2*N lists of the soldiers' heights: one representing each row (in left-to-right order) and column (in top-to-bottom order). As you surveyed the soldiers, you only had small pieces of paper to write on, so you wrote each list on a separate piece of paper. However, on your way back to your office, you were startled by a loud bugle blast and you dropped all of the pieces of paper, and the wind blew one away before you could recover it! The other pieces of paper are now in no particular order, and you can't even remember which lists represent rows and which represent columns, since you didn't write that down.

You know that Argus will make you do hundreds of push-ups if you give him an incomplete report. Can you figure out what the missing list is?


The first line of the input gives the number of test cases, T. T test cases follow. Each consists of one line with an integer N, followed by 2*N-1 lines of N integers each, representing the lists you have, as described in the statement. It is guaranteed that these lists represent all but one of the rows and columns from a valid grid, as described in the statement.


For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is a list of N integers in strictly increasing order, representing the missing list.


1 ≤ T ≤ 50.
1 ≤ all heights ≤ 2500.
The integers on each line will be in strictly increasing order.
It is guaranteed that a unique valid answer exists.

Small dataset

2 ≤ N ≤ 10.

Large dataset

2 ≤ N ≤ 50.


Input Output
1 2 3
2 3 5
3 5 6
2 3 4
1 2 3
Case #1: 3 4 6

In the sample case, the arrangement must be either this:

1 2 3
2 3 4
3 5 6

or this:

1 2 3
2 3 5
3 4 6

In either case, the missing list is 3 4 6.

Solution in J lang:

#!/usr/bin/env jconsole

NB. convert string to decimal
atoi=: 10"_#. '0123456789'"_ i. ]

NB. quicksort
qsort=: (($:@(<#[), (=#[), $:@(>#[)) ({~ [email protected]#)) ^: (1<#)

NB. Handle case
case=: 3 : 0
    NB. convert the number of cases into decimal
    count=: atoi > 0 { y
    current=: 0
    line=: 0
    while. current ~: count do.
        NB. take input, compute and print
        current=: >: current
        line=: >: line
        n=: atoi > line { y
        i=: 0
        data=: ''
        while. i ~: (2*n)-1 do.
            line=: >: line
            i=: >: i
            data=: data , ' ' , > line { y
        NB. sort numbers and find those number with odd times
        numbers=: qsort atoi ;._1 ' ', }. data
        echo ; ":&.> 'Case #' ; current ; ': ' ; (2 | +/ " 1 =numbers) # ~. numbers

NB. get data and handle them
] input=: <;._1 LF , stdin ''
case input
exit 0
声明: 本文为 Cocoa 原创, 转载注明出处喵~

Leave a Reply

Your email address will not be published. Required fields are marked *