2006 code jam algorithm 题分享

tensaix2j

大家来做做看。。。。


这题我用了两个钟以上才code出来。。结果，来不及交就出局了。。

注意:你的程序必须两秒钟内算出答案。。。
所以，用recursion者，得要想想怎么去cache你的result 了。。

尤其是16x16的matrix..

P/s: programming language 不拘

Problem Statement
   
The permanent of a nxn matrix A is equal to the sum of A[1][p[1]] * A[2][p[2]] * ... * A[n][p[n]] over all permutations p of the set {1, 2, ... , n}.
You will be given a String[] matrix, where each element contains a single space delimited list of integers. The jth integer in the ith element represents the value of A[j]. Return the int represented by the last four digits of the permanent of the given matrix.
Definition
   
Class:
PermanentComputation
Method:
compute
Parameters:
String[]
Returns:
int
Method signature:
int compute(String[] matrix)
(be sure your method is public)
   

Constraints
-
matrix will contain between 1 and 16 elements, inclusive.
-
Each element of matrix will contain a list of integers, each separated by exactly one space.
-
Each element of matrix will contain exactly n integers, where n is the number of elements in matrix.
-
Each element will have length between 1 and 50 characters, inclusive.
-
Each element of matrix will contain no leading or trailing spaces.
-
Each integer in matrix will be between 0 and 10000, inclusive, and contain no leading zeroes.
Examples
0)

   
{
"1 1",
"1 1"}
Returns: 2
The permanent is equal to 1*1 + 1*1 = 2.
1)

   
{
"1 2 3",
"4 5 6",
"7 8 9"}
Returns: 450
The permanent is equal to 1*5*9 + 1*6*8 + 2*4*9 + 2*6*7 + 3*4*8 + 3*5*7 = 450.
2)

   
{
"1 2 3 4",
"2 3 4 5",
"3 4 5 6",
"4 5 6 7"}
Returns: 4276

3)

   
{
"1 1 1",
"2 2 2",
"3 3 3"}
Returns: 36

4)

   
{
"1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1",
"1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1",
"1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1",
"1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1",
"1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1",
"1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1",
"1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1",
"1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1",
"1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1",
"1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1",
"1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1",
"1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1",
"1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1",
"1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1",
"1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1",
"1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1"}
Returns: 8000


Set 3 Qualification Round
Google code jam

[ 本帖最后由 tensaix2j 于 9-9-2006 02:48 AM 编辑 ]

tensaix2j

我不知我的code出了什么问题，test 第四个example仍然慢到。。。


Public Class Permanent

    Dim mat(,), n As Short
    Dim cache() As Integer

    Public Function compute(ByVal matrix As String()) as integer
        n = matrix.Length
        ReDim mat(n - 1, n - 1)
        ReDim cache(1 << 16)

        For i As Short = 0 To n - 1
            Dim f As String() = matrix(i).Split(" ")
            For j As Short = 0 To f.Length - 1
                mat(i, j) = Val(f(j))
            Next j
        Next i
        Return recur(n, (1 << n) - 1)

    End Function

    Public Function recur(ByVal submatrixsize As Short, ByVal mask As Integer) as integer

        If submatrixsize = 1 Then
            Return mat(Math.Log(mask, 2), n - 1)
        Else
            Dim sum As Integer = 0
            For i As Integer = 0 To n - 1
                If mask >> i And 1 Then
                    If Not cache(mask >> i) Then
                        cache(mask >> i) = mat(i, n - submatrixsize) * recur(submatrixsize - 1, mask Xor (1 << i))
                    End If
                    sum += cache(mask >> i)
                End If
            Next i
            Return sum mod 10000
        End If
    End Function

End Class

[ 本帖最后由 tensaix2j 于 11-9-2006 05:05 PM 编辑 ]

tensaix2j

这题是practice room里抽出来的。。

也用了我好几个小时。。。
哇捞。。那些人居然5分钟就code出来了。。


试试看吧。。

Problem Statement
   
There are three stacks of crates - two of them outside of the warehouse, and one inside

the warehouse. We have a crane that can move one crate at a time, and we would like to

move all of the crates to the stack inside the warehouse. A heavier crate can never be

stacked on top of a lighter crate, and all three initial stacks obey that rule.
Create a class CraneWork that contains a method moves that is given vector <int>s stack1,

stack2, and warehouse containing the initial three stacks, and returns the minimum number

of moves required to move all the crates into the warehouse stack. The elements of stack1,

stack2, and warehouse represent the weights of the crates and are given from top to bottom

(and thus in non-decreasing order of weight).
Definition
   
Class:
CraneWork
Method:
moves
Parameters:
vector <int>, vector <int>, vector <int>
Returns:
int
Method signature:
int moves(vector <int> stack1, vector <int> stack2, vector <int> warehouse)
(be sure your method is public)
   

Constraints
-
stack1, stack2, and warehouse will each contain between 0 and 20 elements, inclusive.
-
The total number of elements in the three stacks will be between 1 and 20, inclusive.
-
Each element in the three stacks will be between 1 and 200, inclusive.
-
stack1, stack2, and warehouse will each be in non-decreasing order.
Examples
0)

   
{3,50}
{}
{1,2,50,50,50}
Returns: 12
Move 3 to stack2, 1 to stack1, 2 to stack2, 1 to stack2, 50 to warehouse, 1 to warehouse,

2 to stack1, 1 to stack1, 3 to warehouse, 1 to stack2, 2 to warehouse, 1 to warehouse.
1)

   
{50}
{50}
{10,20,30}
Returns: 17
Start by moving 50 from stack2 to stack1. It then takes 7 moves to transfer the 10,20,30

to stack 2, 2 moves to transfer the 2 50's to the warehouse, and 7 more to transfer the

10,20,30 to the warehouse.
2)

   
{}
{}
{2,5,6,7}
Returns: 0
All the crates are already in the warehouse.
3)

   
{1,2,3}
{}
{}
Returns: 7
Move 1 from stack1 to warehouse, 2 from stack1 to stack2, 1 from warehouse to stack2, 3

from stack1 to warehouse, 1 from stack2 to stack1, 2 from stack2 to warehouse, 1 from

stack1 to warehouse.



Practice Set (1000 points)

Quote from codejam 2006
(c)Google Codejam Inc Topcoders.com

[ 本帖最后由 tensaix2j 于 9-9-2006 02:47 AM 编辑 ]

bontakun

关于Permenent calculation 的那题，我想应该不能直接套用直观的algorithm吧，因为如果set p 的元素全部不同的话， P(16)=16!=20922789888000   。。。只是looping就要跑几秒钟。不懂我的理解对不对。嗯好玩好玩。

tensaix2j

loop到完自然吃力。。。

可是仔细想想
用5x5 来做例子。。
当你在第一排选第一个element,你有５个选择。。
那

x 0 0 0 0
0 s s s s
0 s s s s
0 s s s s
0 s s s s

0 x 0 0 0
s 0 s s s
s 0 s s s
s 0 s s s
s 0 s s s

...

.看起来总共有 5! 个可能性。。。

可是仔细想想。。
他的submatrix 虽然没从复，可是。。他们的sub sub matrix却未必。。

x 0 0 0 0
0 s s s s
0 s m m m
0 s m m m
0 s m m m

0 x 0 0  0
s 0 s  s  s
s 0 m m m
s 0 m m m
s 0 m m m

那个sub sub matrix m， 有3! 个可能性。。
本来可以两次省一次来算。。。那就省了3! 个运算。。.当然还有其他从复的sub sub matrix 可以再更further省下不少运算。。

[ 本帖最后由 tensaix2j 于 9-9-2006 10:05 PM 编辑 ]