北大・日立新概念コンピューティングコンテスト2018

参加対象: All Rated対象: - ペナルティ: なし

お知らせ

  • 2019年1月22日:コンテストの参加者登録を開始しました。
  • 2019年2月7日:賞金及び賞品発送手続き等の委託先が決定しました。
  • 2019年2月13日:順位表スクリプトを公開しました。
  • 2019年2月14日:本コンテストの推奨ハッシュタグを追記しました。#HokudaiHitachiProcon2018
  • 2019年2月20日:本コンテストの一部賞品の変更と、外部委託業者から届く電子メールのアドレスを追記しました。
  • 2019年2月22日:オリジナルステッカーとポロシャツのデザインが決定しました。
  • 2019年2月24日: 問題Aの採点方法にシステムテストの条件を追記しました。
  • 2019年3月6日: システムテストの結果を追記しました。
  • 2019年3月7日:本コンテスト表彰式の事前参加登録の受付を開始しました。詳細はこちらをご確認ください。

今回のコンテストに係る賞金及び賞品の発送手続き、ならびに表彰式のご案内については、北海道大学がプライバシーマークを取得済みの株式会社 日立ドキュメントソリューションズに委託いたします。

概要

  • 日立製作所(日立)は北大キャンパス内に日立北大ラボを開設し、北海道大学(北大)と共同で従来の計算原理と異なる、新概念コンピューティングの研究開発を推進しています。
  • 当コンテストは、アニーリングマシンをはじめとする新概念コンピューティングのキー技術になると考えられている前処理アルゴリズムの効率化を目的に2017年度からスタートした、北大と日立が共同で開催するマラソン型のプログラミングコンテストです。
  • 2017年はグラフ変換アルゴリズムに関する問題で2回開催し、従来手法に勝るアルゴリズム(PSSA:Probablistic Swap Shift Annealing)が考案されました(1回目はこちら、2回目はこちらをクリック下さい)。
  • 考案されたPSSAは2017年度コンテストの優勝者と共に、北大・日立で実応用に向けた検討を実施中です(本開発成果を国際会議TPNC2018にて発表いたしました)。
  • 2018年度は、社会課題を新概念コンピューティングにマッピングするための定式化に関する問題が出題されます。
  • 問題文は日本語と英語で提供されます。

ルール

  • 所属・年齢・居住地を問わず、誰でも参加できます。必ず参加登録ボタンから参加登録を行ってください。参加登録は本日からコンテスト終了日まで、いつでも可能です。
  • コンテストの開催期間は2週間(2019年2月14日~2月27日)です。コンテストは、オンラインで実施されます。
  • コンテストは問題A、B、Cの3種類の問題を出題します。
  • コンテスト期間中は何回でも解答を提出できます。しかし、提出直後の1時間は再提出することができません(ただし、提出制限は問題ごとに独立となります)。
  • 問題のツール(テストケース生成や得点計算プログラム)はC++で提供します。
  • コンテスト開催期間中、自分のアイデアを共有したい方はTwitter やブログ等で共有頂いても構いません(推奨ハッシュタグは「#HokudaiHitachiProcon2018」でお願いします)。また、共有されたアイデアを参考にしながらコンテストの解答を作成頂いても構いません*。
    • * アイデアは自発的に共有頂いた時点で公共化することを意味します。共有されたアイデアをベースに第三者が効率のより良いアルゴリズムを発案された場合、そのアルゴリズムによる得点は、原則、第三者に帰属されることになりますので、その点だけご留意ください。
  • 問題A、B、Cの順位付けは、得点によって決定されます。同点の場合は同順位となります。
  • 総合順位の順位付けは、「問題Aの順位 × 問題Bの順位 × 問題Cの順位」が小さい順に上位となります。
  • 同順位の場合は、「min(問題Aの順位、問題Bの順位、問題Cの順位)」が小さい順に上位とします。それでも同順位の場合は、最後に順位表に反映された問題の解答コードの提出時間が最も早い参加者を上位とします。
  • 上記の順位づけルールを順位表に反映させるスクリプトを提供します。スクリプトはここからダウンロードできます。

賞金

  • 成績上位者には、下記の賞金・賞品をご用意しております。
  • 総合順位
    • 1位 300,000円
    • 2位   50,000円
    • 3位   30,000円
    • 4~20位 賞品(北大及び日立グッズ)の贈呈

  • 問題A
    • 1位 30,000円
    • 2~10位 賞品(北大及び日立グッズ)の贈呈

  • 問題B
    • 1位 30,000円
    • 2~10位 賞品(北大及び日立グッズ)の贈呈

  • 問題C
    • 1位 30,000円
    • 2~10位 賞品(北大及び日立グッズ)の贈呈

  • 上記に加えて入賞者全員にオリジナルポロシャツとステッカーを贈呈いたします。コンテスト終了後、入賞者には北大・日立より、外部委託業者を通じて電子メール(hokudai-lab2018@ml.hitachi-document.co.jp)にて通知させて頂きます。入賞者は、電子メールにて期日内に受賞に同意する旨をご返信ください。指定の期日内に返信メールをいただけないときは、受賞の取り消しとさせていただきます。予めご了承ください。

最終結果

システムテストの結果を以下に示します。大変多くの方々にご参加頂きありがとうございました。3/15(金)の表彰式もぜひご参加ください。

順位 総合 順位 総合
1 wata 11 miku
2 Aquarius 12 phocom
3 set0gut1 13 yosss
4 saharan 14 ts_
5 tomerun 15 kurenai3110
6 hakomo 16 hoshi524
7 roto_37 17 c7c7
8 m_tsubasa 18 yokozuna57
9 kt_tenel 19 beet
10 riantkb 20 TypedTypelessTy

なお、問題A,B,Cの結果は下記になります。

順位 問題A 問題B 問題C
1 saharan c7c7 wata
2 Aquarius wata tomerun
3 wata tomerun set0gut1
4 set0gut1 mtsd Aquarius
5 riantkb saharan yosss
6 kurenai311 yosss m_tsubasa
7 hakomo roto_37 kt_tenel
8 roto_37 Aquarius hakomo
9 phocom tanakh uts45
10 ts_ noshi91 hoshi524

表彰式

  • 情報処理学会 第81回全国大会のランチョンにて表彰式を開催します。
  • 日時:2019年3月15日(金) 11:40 – 12:30
  • 会場:福岡大学 七隈キャンパス A棟 A203(第4イベント会場)
  • 内容:コンテストの背景説明、各問題の解説、総合得点・問題毎の成績上位者の表彰と記念講演*を予定しております。
  • * 総合得点優勝者、問題A~Cの各優勝者には、居住地に応じた旅費(定額)を支給いたします(ただし、国内居住者に限定する予定です)。また、演者の皆さまには謝礼を贈呈いたします。
  • ** 表彰式終了後、福岡大学近辺の会議室で当コンテスト入賞者の皆様と北大・日立関係者との意見交換会を予定しております。詳細については、対象者に電子メールにてご連絡いたします。

その他

  • 使用可能言語は、AtCoder Regular Contestに準じます。
  • AtCoder社の利用規約、チュートリアル、ルール、用語集、よくある質問 をお読みください。

2017年度コンテストの様子

  • グラフ変換アルゴリズムにフォーカスした、2017年度のコンテストは2週間のマラソン型で計2回開催されました(登録者数は1000名超)。
  • 年代は中高生から社会人に渡り、300名を超える参加者が実際に解答コードを提出頂き、ランキングが時々刻々と入れ替わるハイレベルな展開になりました。
  • 情報処理学会 第80回全国大会にて表彰式を開催し、成績優秀者の表彰及び優勝者による記念講演等が行われました。大変多くの方々にご参加頂きありがとうございました。

当コンテスト出題問題の適用先
(背景に興味がある方向け)

  • 従来の計算機は、所望の処理を実行するための手順を順序立ててプログラムに記述し、それを逐次的に実行することで一意的な値を導出します。
  • 一方、新概念コンピューティングでは、社会システムに内在する社会課題の要因(因子)を物理現象の構成要素に同定します。
  • 下図に、新概念コンピューティングの計算フローを示します。
    1. 社会システムをグラフ表記する前処理が行われます((1)→(2))。この前処理の実体は、社会システムに内在する社会課題を物理現象のエネルギー関数に定式化する操作です。ここで、社会課題の要因(因子)はエネルギー関数の変数として扱われます。
    2. グラフ変換アルゴリズムが行われます。このアルゴリズムは、複雑で不規則なグラフ構造をハードウェアで実装可能な単純かつ規則的な構造に変換する処理です((2)→(3))。
    3. 物理現象の収束動作を実行・観測します。エネルギー関数が所定の値に達した際の、因子の値が、所望の近似解です。専用ハードウェアを用いて、収束動作を実行・観測することで、短時間で適切な近似解が導出されます((3)→(4))。

  • このような計算機を実現する際の課題は、従来のプログラミングに相当する、定式化・グラフ変換アルゴリズム等の前処理技術の効率化です。北大と日立は、オープンイノベーションによる課題の解決をめざしています。

Announcement

  • Participant registration opens/has opened on January 22, 2019.
  • The company entrusted with the distribution of prizes (awarded money and special gifts) was announced on February 7th 2019.
  • This year's sticker and T-Shirt design has been announced.
  • A specification about the use of the random seed during the final score evluation has been announced in problem A.
  • The ranks obtained after the final system test have been announced on March 6th 2019.

Hokkaido University has entrusted Hitachi Document Solutions [Japanese: 株式会社 日立ドキュメントソリューションズ] with the distribution of award money and special gifts for the best ranked contestants. The same company will contact high ranked contestants on behalf of the organizers in order to invite them to attend the award ceremony or else give guidance on the award ceremony. Note that Hitachi Solutions has a 'privacy mark', ensuring high quality standards on handling of personal information.

Contest Background

  • The organizers of this contest are a group of researchers at Hitachi Ltd. and Hokkaido University, who collaborate at Hitachi Hokkaido Laboratory for developing new computing concepts, which go beyond the conventional von Neumann architecture. At the moment we focus on the development of the CMOS Annealing Machine to boost non-convex optimization.
  • Targeting the preprocessing algorithms for CMOS Annealing we organized our first two marathon-type programming contests in 2017 revolving around the topic of graph transformations. (See first and second contest). The award winning algorithms of last years contests are now successfully in use at Hitachi Ltd. and Hokkaido University. One of these algorithms -- Probabalistic Swaft Shift Annealing (PSSA) -- was even presented at the international conference TPNC2018 and published in the accompanying proceedings with Springer's Lecture notes in computer science.
  • This year's programing contest will again be of marathon-type, extending over a period of two weeks. Its topic will focus on the expression of certain optimization problems in the format required by typical annealing hardware.
  • This contest will be held in both Japanese and English.

Rules

  • Anyone is eligible to participate in the contest, regardless of age, gender, nationality, or affiliation. The contest is open for registration any time until the contest closes. For registration of participation, click here.
  • The contests will be held for a two-week period from February 14 to February 27, 2019.
  • We will prepare three different subproblems A, B and C.
  • During the contest period participants may submit as many answers as they like. However, within one hour after submitting a solution, e.g., to subproblem A, the server may reject further submissions to the same subproblem, in order to avoid overload. So please wait for at least one hour before you submit improved solutions.
  • Sharing ideas through Twitter or blogs during the contests period is explicitly allowed. You can also solve problems based on ideas which others have posted.*

    * Note that voluntarily shared ideas are public. Hence, if a third party creates the award winning algorithm based on previously shared ideas, the score will be attributed to the algorithm of the third party.

  • The submission for each problem will be ranked separately, according to a specified score.
  • The overall rank will be determined by multiplying the participants rank in problem A, B and C and ordering the resulting number starting from the minimum.
  • Should multiplying a participants rank from problems A, B, and C result in the same overall rank, the participant with the earlier submission date will be ranked better. A participants submission date is defined by the last top-scoring submission to problems A, B, or C.
  • A script for accessing the overall score of each contestant is provided under the following url .
  • We will prepare sample code for generating input problems and score evaluation for use at the participants personal PC in C++.

Prizes

  • The top-scoring contestants will be awarded the following prizes.
  • Total Score (Based on combination from ranks of problem A, B and C)
    • 1st rank 300,000 yen
    • 2nd rank 50,000 yen
    • 3rd rank 30,000 yen
    • 4th~20th Special Gifts (Hokkaido University and Hitachi Ltd.’s goods)

  • Problem A
    • 1st rank 30,000 yen
    • 2nd~10th Special Gifts (Hokkaido University and Hitachi Ltd.’s goods)

  • Problem B
    • 1st rank 30,000 yen
    • 2nd~10th Special Gifts (Hokkaido University and Hitachi Ltd.’s goods)

  • Problem C
    • 1st rank 30,000 yen
    • 2nd~10th Special Gifts (Hokkaido University and Hitachi Ltd.’s goods)

  • In addition, we award all prize winners with an original T-shirt and a sticker. After the contest, all prize winners will be contacted by Hokkaido University and Hitachi Ltd. through a third party via Email. Please reply to this e-mail within the specified time limit, if you agree to receiving the prize. Please note that we will have to cancel the prize, in case we do not receive a reply by the designated date.

Final Ranking

The final ranking of contestants after conducting the full system test is announced in the table below. We thank every contestant for their contribution to as well as their participation in the contest. If possible, please come and attend the ceremony on Friday March 15th (as announced further below).

Rank Contestant ID Rank Contestant ID
1 wata 11 miku
2 Aquarius 12 phocom
3 set0gut1 13 yosss
4 saharan 14 ts_
5 tomerun 15 kurenai3110
6 hakomo 16 hoshi524
7 roto_37 17 c7c7
8 m_tsubasa 18 yokozuna57
9 kt_tenel 19 beet
10 riantkb 20 TypedTypelessTy

The rank of contestants with respect to sub problems A, B, and C is listed below.

Rank Problem A Problem B Problem C
1 saharan c7c7 wata
2 Aquarius wata tomerun
3 wata tomerun set0gut1
4 set0gut1 mtsd Aquarius
5 riantkb saharan yosss
6 kurenai311 yosss m_tsubasa
7 hakomo roto_37 kt_tenel
8 roto_37 Aquarius hakomo
9 phocom tanakh uts45
10 ts_ noshi91 hoshi524

Awards Ceremony

  • The contest's awards ceremony will be held during the lunch seminar session of the 81st National Convention of the Information Processing Society of Japan.
  • Date and time: March 2019 (Friday) 11:40-12:30
  • Place: Fukuoka University Nanakuma Campus A Building A203, Auditorium #4
  • Content: After explanation of the contest’s background and the proposed problems, the award winners of problems A, B, and C as well as the overall winner are invited to give short lectures, explaining the main ideas of their algorithms (*,**).

    *Note that travel expenses can only be supported for speakers residing in Japan. **We are planning to have a meeting to exchange ideas with the winners and the participants from Hokkaido University and Hitachi after the award ceremony at a conference room near Fukuoka University. Participants in question will be contacted by e-mail.

Other

  • The programming languages used should be compatible with AtCoder Regular Contest.
  • Please read AtCoder Inc.’s terms of service, tutorials, rules, glossaries, and frequently asked questions.

Impressions of 2017's contest

  • Last year we held two marathon-type programming contests, each of which lasting two weeks. The contests content focused on problems of graph embedding, which are relevant to the construction of Annealing Machines.
  • Altogether, both contests had more than 1000 participants, whose age ranged from high-school students up to grown ups. More than 300 people submitted successfully working solutions and scores kept ever changing, resulting in a narrow race among the participants.
  • The award ceremony was held at the 80th National Convention of the Information Processing Society of Japan. Both award winners gave lectures on the ideas entering their award winning algorithm.

Applications of the contest submissions
(For those interested in the contests background)

  • While conventional computers follow well-defined procedures with the target to produce a unique and well defined result, New-Concept Computing tries to identify relevant factors in social systems and simulate them by mapping the relevant process onto a physical process.
  • The flow of mapping of a social system to a physical system and ultimately onto annealing hardware is illustrated in the figure below:
    1. The social system is expressed in terms of a physical energy-function whose components can be described by a graph, see Fig.(1)→(2).
    2. A graph conversion algorithm is run. This algorithm converts a complex, irregular graph structure into a simple and regular structure that can be implemented into hardware, see Fig.(2)→(3).
    3. The hardware, see Fig. (4) simulates the cooling process of a physical system. Its resulting state and energy, give the solution to the original social problem in Fig.(1).

  • In order to make use of efficient hardware, it is pertinent to develop efficient formulations of social problems as well as efficient algorithms for their conversion into hardware compatible formats. Hokkaido University and Hitachi Ltd. are tackling such challenges together through open innovation.
    FYI: Here is a (Japanese) pamphlet introducing our team and our research.