予選詳細
予選詳細
予選問題として5題の問題データ（下記参照）が用意されます．各問題データには，ノード分割後の異なるノード集合にまたがるエッジ数（Edge Cnt）に関して，上限値が定められています．各問題について，Edge Cntが上限値以内となる解を求め，結果を提出してください．算出したEdge Cntが上限値以内であるかどうかは，各自のプログラム中で判定してください．
全ての問題データは，予選開始時にGCF上の各クラスタ上に置かれます．（クラスタ上の任意のノード上から参照可能です．） 参加者は，クラスタの任意のノード上で問題取得用API GetProblem()を1回だけ実行して，問題ファイルの保存場所を取得してください． また，問題データ毎に定められるEdge Cntの上限値は下記「予選問題」を参照してください．
予選問題は，下記の5題の問題（問題番号11〜15）からなります．各問題を解く場合は，問題取得用API GetProblem() の引数（problem_number）に下記の問題番号（11〜15）を指定してください． 問題サイズは，最も大きな問題でグラフ中のノード数が1,500個です．決勝問題では，より大規模な問題（最大ノード数が40,000個程度）を用意する予定です．予選通過の条件となるEdge Cntの上限値は以下の表の通りです．
予選問題の上限値
| 問題番号 | Edge Cntの上限値 |
| 11 | 50 |
| 12 | 6 |
| 13 | 50 |
| 14 | 20 |
| 15 | 250 |
予選の出題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() の出力が一部変更されています（2006/02/13）．予選では変更後のAPIの仕様を使用します． 詳細はこちらを参照してください．また，変更されたAnswerProblem()を含むお試しキットも同ページから入手できます．
解答用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つ選んで提出してください．
結果提出はなるべく速やかに，最後の結果が出てから遅くとも一日以内に行なってください．(結果を順次確定していくため）
予選の順位は，より早く最後の問題を解き終えた参加者を上位として順位づけを行ないます．ただし，解き終えた時刻の差が1分未満である場合は同時刻とみなして，以下のように判定します．
最後の問題を解いた時刻が同時刻となった場合，最後から2番目の問題について同様に比較して順位を決めます．それでも同着なら同様に，順々に全ての問題について比較を繰返し，もし最後まで順位がつかない場合は申し込み順により順位を決定します． 予選の順位は，本選期間中のクラスタ占有利用時間帯を参加者の希望に沿って選ぶときの優先度になります．具体的には上位チームから希望する時間帯を選ぶことができます．