Grid Challenge 2006: final

決勝詳細

決勝ルール：

チームに与えられたスロット内にプログラムを実行してください．他チームに割り当てられたスロット中にプログラムを実行することは禁止します．即ち，与えられたスロット中は，GCF上のクラスタを占有利用できます．スロットの割り当てについてはこちらを参照してください．

空き時間に予選問題やお試し版の問題を使って練習を行なうことは許可します．空き時間の定義については，こちらを参照してください．ただし，決勝問題を使ってプログラムを実行することは禁止します．

決勝問題として5題の問題データが用意されます．全ての問題データは，決勝開始時にGCF上の各クラスタ上に置かれます（クラスタ上の任意のノード上から参照可能です）．参加者は，クラスタの任意のノード上で問題取得用API GetProblem()を1回だけ実行して，問題ファイルの保存場所を取得してください．

問題1題を計算するためのプログラムの実行時間（＝AnswerProblem() またはGetElapsedTime()が出力する経過時間）には10分間の制限が設けられます．10分以内に解を求め，結果を提出してください（下記の「提出方法」参照）．出題APIでは，プログラムの実行時間が10分間を超えたかどうかをチェックする機能は特に設けませんので，各自のプログラムでAnswerProblem() またはGetElapsedTime()を呼び出してチェックしてください．

また，解答とともに決勝で用いたプログラムのソース一式も提出してください（下記の「提出方法」参照）．

決勝問題：

決勝問題は，5題の問題（問題番号21～25）からなります．各問題を解く場合は，問題取得用API GetProblem() の引数（problem_number）に問題番号（21～25）を指定してください．問題サイズは，最も大きな問題でグラフ中のノード数が40,000個です．

プログラムのコンパイルとリンク：

決勝の出題APIは，決勝開始時に各クラスタのコンパイルノードに以下の通り置かれます．（予選用出題APIに上書きされます．）参加者はこれらのファイルをリンクして用いてください．

出題API

/home/aida/grch/include/grid_challenge_api.h (ヘッダ) /home/aida/grch/lib/libgrch.a (ライブラリ) /home/aida/grch/lib/libcrypto.a (暗号化ライブラリ)

決勝の空き時間（空き時間の定義はこちら）に，予選問題を使ってプログラムのテストを行なう際には，この決勝用ライブラリを用いて構いません．ただし決勝用の問題での実行は禁止します．

C言語版におけるlibcrypto.aはOpenSSLに付属のものであるため，標準的なパス(/usr/libや/usr/local/ssl/libなど)にもすでにインストールされている可能性があります．その場合はどちらを利用しても構いません．

提出方法：

解答用API AnswerProblem() の出力する解答チェック用文字列（check_string）を5題全ての問題について集めて記述したテキストファイルを作成し（以下の例参照），grid-challenge-sec [at] alab.ip.titech.ac.jp （" [at] "を"@"に置き換えてください．）まで送付してください．提出するテキストファイルは，問題1題分の解答チェック用文字列（61文字）を1行に収め，かつ余分な改行や空白は入らないように注意し，メールの添付ファイルとして提出してください．また送信するメールには，必ずアカウント名，チーム名と代表者名を記入してください．

提出するテキストファイルの例

01000000070000001000903837205lndlkebfehhdelbehkckcjldliidmlgp  #これが1題分
02000000280000001001103839959efmdnmgcpccaabjkbkldmhpbonnikjef
03000001780000001001703839980dppodknkpmiebppfefcfjnihjfokokpo
           :

問題1題を解く際に，プログラム中でAnswerProblem()を何回呼び出しても構いません．その場合は，最も良いと思われる結果（Edge Cntが最小の結果）を1つ選んで提出してください．この場合，提出された解の計算に要した時間（AnswerProblem()により算出された経過時間）をプログラムの実行時間とします．

決勝で用いたプログラムのソース一式も，上記メールの添付ファイルとして提出してください．標準のGCF環境にない，一般に公開されているライブラリ等を各自でインストールして用いている場合は，そのライブラリまで提出する必要はなありませんが，委員会が後ほど問い合わせを行なった時に解答に用いたバージョンが確実に手に入るようにライブラリは各自で保管しておいてください．

結果提出はなるべく速やかに，最後の結果が出てから遅くとも一日以内に行なってください．

順位の決定方法：

決勝では，各問題について，以下の方法で参加者にポイントを加算し，全問題についての合計ポイントがより多い者を上位とします．

参加者から提出されたEdge Cnt（ノード分割後の異なるノード集合にまたがるエッジ数）のうち，最良（最小）のEdge Cntを求め，各参加者には，「最良Edge Cnt」／「自分の算出したEdge Cnt」がポイントとして与えられる．即ち
```
      参加者iの提出したEdge Cnt：Ei
      全参加者の提出したEdge Cntのうち最良のもの：Ebest
    
      参加者iのポイント ＝  Ebest ／ Ei
```
例えば，全問題について最良のEdge Cntを求めることができた参加者には，5点が与えられる．
解が求まらなかった問題がある場合，その問題により加算されるポイント数は，0点とする．

5題の問題により与えられるポイントが同一の参加者が複数いる場合は，5題全ての問題の実行時間の合計が小さい方を上位とします．

updated: 2006/3/6
グリッドチャレンジ2006実行委員会