高校生向けの全ロシアのエンジニアリングオリンピック：BigDataとインテリジェントエネルギーシステム

最初の予選ステージ

最初の予選ラウンドはインターネット上で個別に実施され、作業はオンラインテストシステムによって自動的に評価されます。 参加者には、最初の予選段階の問題を解決するために3週間が与えられました。 各問題の解決策は、一定のポイントを与えます。 すべての参加者に共通のタスクセットが提供されますが、問題を解決するために、異なるレベル（9年生または10年生から11年生）の参加者には異なるポイントが与えられました。 問題の正しい解決策としてポイントが全額加算されます。 参加者は、このプロファイルのすべての科目（数学およびコンピューターサイエンス）の合計で問題を解決するための評価（合計0〜20ポイント）を受け取ります。

タスクの例：
数学の問題1.1.6（1ポイント）
不幸な宇宙飛行士イノケンティは、遠心分離機の後で気分が悪く、方向を判断できませんでした;彼は、委員会から5メートルのところにあり、直線で動いていました。 毎秒、等しい確率で、1メートルに近づくか、離れます。 彼が委員会に達した場合、彼はどこにも行かない。 10秒以内に委員会の手に落ちる可能性を見つけます。



インフォマティクスタスク1.2.2「ルート」（3ポイント）
少年Petyaの数はNです。しかし、Xの数とは異なり、彼はそれを必要としません。

自然数nからの次数kの整数根は、関係が成り立つ最大の正の整数と呼ばれます。 たとえば、1000のうち5次の整数根は3です。 としてそれを示す また、自然数のみがルートの程度になり得ると仮定します。

Petyaの場合、整数のルートを取得するのは難しいタスクであり、Xを取得するための式にあるルートの合計次数を最小限に抑えたいと考えています。

ペティアにも兄がいます。 その名前はディマです。 このディマは、プチの仕事に興味を持ち、そのような制限を加えることにしました：

1. PetyaはN以外の数値からルートを取得できません。
2. ルートを取得するか、他の数値を乗算する操作を使用して、Petyaが取得した数値のみを乗算できます。
3. 乗算の結果として得られた数、ルートを取得した数、または他の数の合計を追加できます。

Petyaが読みやすく、Dimaによって課せられた制限に適合する表現を書くのを助けてください。 探している式の最小の複雑さを見つけます。

入力フォーマット：
唯一の行には2つの整数NとXが含まれます

入力例：
100 126

出力形式：
唯一の正の整数-問題への答えを出力します。

出力例：
9

例の説明：

性能評価の方法
次のPythonコードを使用して、一意の条件を生成し、結果を検証します。 generate関数は、バリアントの条件と正解を返します。

def generate(): return [('{} {}\n'.format(n, x), ans) for n, x, ans in [ (100, 126, 9), (10, 10, 1), (1000, 1000, 1), (1, 1, 1), (1, 1000, 1000), (1000, 1, 10), (1000, 999, 17), (722, 966, 16), (774, 717, 21), (664, 177, 16), (655, 657, 7), (659, 65, 9), (901, 559, 21), (813, 314, 18), (528, 131, 16), (882, 258, 19), (516, 583, 12), (801, 767, 19), (147, 222, 11), (67, 743, 13), (413, 335, 21), (453, 467, 7), (600, 104, 9), (323, 209, 19), (462, 822, 18), (126, 743, 16), (77, 917, 17), (100, 999, 27), (1, 999, 999), (1000, 894, 29), (999, 712, 28), (123, 944, 24), (432, 277, 24), (945, 616, 28), (100, 999, 27), (1000, 894, 29), (999, 712, 28), (123, 944, 24), (432, 277, 24), (945, 616, 28) ]] def check(reply, clue): return int(reply.strip()) == int(clue) 

予選2段階目

2番目の予選段階は、インターネット上でチーム形式で行われ、作業はオンラインテストシステムによって自動的に評価されます。 2番目の予選段階の期間は2週間です。 タスクは学際的です
そして、より簡単な形式で、最終段階のエンジニアリングタスクを再作成します。 問題の解決にはプログラムの作成が含まれ、Pythonプログラミング言語の使用が許可されました。 各問題の解決策は、一定のポイントを与えます。 この段階で、合計0〜45ポイントを獲得できます。

データ分析タスク

タスク2.1.1（10ポイント）
1000人の学生がサマーキャンプに来ました。 学生が到着すると、彼はすぐにコピーされました（シリアル番号を最初から入れました-学生がキャンプに到着した方法）。 学童はすぐにユニットに分割され、ユニット内の人数は異なります。
最初のn1の学生は最初のユニットで、次のn2の学生は2番目のユニットで、次のn3は3番目のユニットというように識別されました。
すべての偶数ユニットが遠足で撮影されたら。 そして、委員会はキャンプに到着し、滞在していたすべての学生を書き直しました（各学生は、キャンプに到着したときに記録された番号を命名しました）。 間違って、何人かの生徒は何度か書き直されました。 どのユニットのどの学生を見つけるのですか？

キャンプに残ったコピーされた学童のシリアル番号に対応する数字の配列が入力に供給されます。
出力は数字のペアのセットです。最初の分隊の最初と最後の学童のシリアル番号、2番目の分隊の最初と最後の学童のシリアル番号などです。

問題を解決するために、参加者には10ポイントが与えられます。

入力例：
790443801518 63 75 491 91 ... 420 371 89 389 453 488 892 932 932

出力例：
[（0、92）、（93、343）、（344、521）、（522、772）、（773、999）]

プログラム実行制限時間： 15秒

RAMの使用の制限： 256 MB

解決策は174ページにあります 。

タスク2.1.2（15ポイント）
地図作成者は、各都市について、関連付けられている都市のリストを編集しました
道路で。 今、彼は2つの遠くの間を運転することが可能かどうか尋ねられます
都市。

市の2つの名前が入り口に送信されます。これを確認する必要があります。
他の都市と道路で接続されている都市のリスト。 答えが必要です
TrueおよびFalse形式で提供します。

問題を解決するために、参加者には15ポイントが与えられます。

入力例：
{'find'：（ 'd'、 'f'）、 'd'：['a'、 'b'、 'c'、 'e'、 'f'、 'g']、 'b'：[ 「a」、「c」、
「d」、「e」、「f」、「g」]、「q」：[「n」、「o」、「p」、「r」、「s」、「t」、「u」] 、 'f'：['a'、 'b'、
「c」、「d」、「e」、「g」]、「a」：[「b」、「c」、「d」、「e」、「f」、「g」]、「s」 ：['n'、 'o'、 'p'、
「q」、「r」、「t」、「u」、「c」]、「e」：[「a」、「b」、「c」、「d」、「f」、「g」] 、「u」：[「n」、「o」、
「p」、「q」、「r」、「s」、「t」]、「r」：['n'、 'o'、 'p'、 'q'、 's'、 't'、 'u']、 'p'：['n'、
「o」、「q」、「r」、「s」、「t」、「u」]、「c」：[「a」、「b」、「d」、「e」、「f」、 'g']、 'g'：['a'、
「b」、「c」、「d」、「e」、「f」]、「o」：['n'、 'p'、 'q'、 'r'、 's'、 't'、 'u']、 'n'：['o'、
「p」、「q」、「r」、「s」、「t」、「u」]、「t」：['n'、 'o'、 'p'、 'q'、 'r'、 「s」、「u」]}

プログラム実行時間制限： 3000秒
RAMの使用の制限： 256 MB

解決策は178ページにあります 。

タスク2.1.3（0-20ポイント）
タスクには、発明したソーシャルネットワークグラフが含まれます（ユーザーごとに、どのユーザーが彼を友達として追加したかが示されます）。 ユーザーごとに、彼の人気が計算されます。これは、友達であるユーザーと何人の友達が友達であるかに基づいています。

人気はXとして計算されます。これは、自分自身を数えて、友達と友達になっている人の総数です。
2つのパーセンタイル50と90を計算する必要があります。 人気の最も低い2つの値は、最初の確率が50％、2番目の確率が90％であるため、ランダムユーザーの人気はこの値よりも低くなります。

問題をコンピューターとシステムで解決して、各タスクの2つの数字の形式でソリューションをダウンロードする必要があります。

すべてのテストで少なくとも50のパーセンタイルをカウントした場合（50パーセントの確率で、人気は低くなります）、タスクから半分のポイントを獲得します。

入力例：
[{0：[5、8]、1：[7、2]、2：[8]、3：[10、0]、4：[0、10、2、1]、5：[1、5] 、
3、7]、6：[7、3、0]、7：[12、13、0、8]、8：[8、11]、9：[6、2、13]、10：[13] 11：
[2、0、8]、12：[0、13]、13：[4、11、8]、14：[0、4、12、2]}、{0：[14、11]、1： [7、
14、1]、2：[0]、3：[10]、4：[13]、5：[8、0]、6：[5、3]、7：[2、11、8、10] 、8：
[3、10、14、7]、9：[0、11、7、4]、10：[1、7]、11：[10、5、12、4]、12：[14、5]、
13：[7、6、3、1]、14：[10、6、0、8]}]

出力例：
[（4、6）、（7、9）]

RAMの使用の制限： 256 MB
1回の試行： 5分

解決策は186ページにあります 。

最終段階：個別およびコマンドユニット

そして、これらはGOTOキャンプやハッカソンで出会ったサッカーで繰り返し優勝した小学生です。

オリンピアードの最終段階は、2つの部分から構成されます。被験者の問題に対する個別の解決策（数学、コンピューターサイエンス）と、エンジニアリングの問題に対するチームによる解決策です。 問題の個別の解決策については、1人の被験者に2時間与えられます。 数学とコンピューターサイエンスのタスクは、9年生と10年生から11年生の共通点です。 各問題の解決策は、一定数のポイントを与えます（以下の評価基準を参照）。 数学では、タスクごとに、記述された基準に従って、0から指定された数のポイントを取得できます。

コンピューターサイエンスのポイントは、問題の正しい解決策として全額が認められています。

コンピューターサイエンスのタスクを解決するには、Pythonでタスクを作成する必要がありました。 参加者は、このプロファイルのすべての科目（数学およびコンピューターサイエンス）の合計で問題を解決するための評価（合計0〜24ポイント）を受け取ります。

数学3.1.1vでの割り当て（2点）。
心理学者のグループがテストを開発し、合格すると、各人が評価を受けます-数字Qは、彼の精神的能力の指標です（Qが多いほど、能力が高い）。 国の格付けは、この国のすべての居住者のQ値の算術平均です。

国Aの市民グループは国Bに移住し、国Bの市民グループは国Bに移住しました。その結果、各国の格付けは初期国よりも高くなりました。 その後、移民の流れの方向が反対方向に変わりました-Bの一部の居住者がBに移動し、Bの一部の居住者がAに移動しました。 2番目）。 （だから、いずれにせよ、これらの国の通信社は主張する。）これは可能だろうか（もしそうなら、そうでなければ、どうして、そうでなければ、なぜ）？ （考慮された期間中、Q市民は変化せず、誰も死亡せず、生まれもしなかったと想定されます。）

数学の問題3.1.2（6点）
VKontakteソーシャルネットワークの管理者は、「このコミュニティに友人の半分未満しかいないすべての人」というコミュニティを作成することを決定しました。 これを行うには、最終的に次のようにユーザーをコミュニティに含める必要があります。

• このコミュニティの全員は、半分以下の友人しかいませんでした。
• このコミュニティに参加していないすべての人には、少なくとも半数の友人がいます。

彼らはいつもそのようなコミュニティを作ることができますか？
（ユーザー自身がコミュニティに参加するのではなく、ソーシャルネットワークの管理者によって配布されると想定されています）

解決策は191ページにあります 。

情報学タスク3.2.4「最終認証」（3ポイント）
年末は、試験の準備をしている学生だけでなく、試験官にとっても忙しい時期です。 テストを作成するときは、学童にとってタスクがどれだけ難しいかを検討し、テストに合格する生徒の数を決定する必要があります。

今年は、5つの問題を解決するためにさまざまな学校の100人の生徒を招待して、テスト試験を実施することが決定されました。 各タスクはaiポイントで評価されます。 タスクはフルスコアで解決されるか、まったく解決されないため、ポイントが付与されません。 レビューアは部分的な決定を考慮しません。 試験の後、編集者は学生の結果を受け取りました。 生徒ごとに、すべてのタスクをチェックした結果がわかります。
1,000,000人の学生が試験を受ける場合、少なくともKポイントを受け取る学生の数を計算する必要があります。

特定の問題を解決する確率を確実に見つけることはできませんが、単一の問題を解決する確率を確実に推定することができると想定していることに注意してください。

入力フォーマット：
最初の行には、数K-テストに合格するために必要なポイントの数が含まれています。 2行目には、5つの自然数-タスクのポイントが含まれます。 最初の番号は最初のタスクのポイントに対応し、2番目は2番目のタスクなどに対応します。 これに100行が続きます。 各行には、番号に対応する問題が解決されたかどうかを示す5つの数字が含まれています。 最初の行は、最初の問題が解決されたかどうかを示し、2番目の問題は解決されたかどうかなどを示します。 問題が解決した場合、行は1を示し、そうでない場合は0を示します。

出力形式：
1,000,000人の学生が同じテストに合格した場合、同じテストに合格した予想人数を1行で印刷します。

解決策はここ200ページにあります 。

コマンド部

問題の声明。
最終段階の指揮部の参加者は、ソーシャルネットワークのユーザーのグラフを分析するための一連のタスクを解決する必要がありました。プロファイルでそれを示さなかったユーザーの年齢を予測します。 ユーザーの居住地域を予測する ソーシャルネットワークの他のどのユーザーが使い慣れたユーザーであると想定します。

参加者はPythonでプログラムを書くことになっています。 最終段階のコマンド部分の期間は3日間（合計18天文時間）です。 参加者はインターネットにアクセスでき、電話やラップトップを使用できました。
合計で、チームには3つのタスクが提供されました（毎日1つ）。 タスクの条件は、対応する日の朝に参加者に知られるようになりました。 各タスクについて、Odnoklassnikiの実際のソーシャルネットワークの2つのサブグラフが作成されました。

• 参加者には、特別に準備され、整理され、匿名化されたサブグラフが提示されました。
• ソリューションの品質管理は、最初の列からデータがクリアされた列全体で自動的に実行されました。

各タスクについて、参加者には効率の低い実用的な基本ソリューションが提供されました。参加者は、タスクをより良く解決するか、提案されたソリューションを改良できる独自のソリューションをゼロからプログラムするという選択肢に直面しました。 この場合、基本的なソリューションを部分的に使用することができました。たとえば、データモデルのみ、または入力データレコグナイザーのみです。

ソースデータの説明
すべてのタスクで、参加者にはユーザーのグラフ（ユーザー間の接続）と人口統計（各ユーザーの匿名データ）のファイルが提供されました。

ユーザー数
グラフはスパースマトリックスの形式で保存されます。各接続には、そのタイプ（相対、友人など）に関する情報がビットマスクの形式であります。 マトリックスの各行は、1人のユーザーの友人に対応し、次の形式を持ちます。
User_ID1 {（friend_id1、mask1）、（friend_id2、mask2）、...}

マトリックスはユーザーIDによって16個のファイルに分割され、各ファイルは標準のGZip圧縮プロトコルによって圧縮されます。
リンクのリスト内のペアは、フレンドID（昇順）でソートされます。 グラフのエントリの例：
102416
{（5362439.0）、（7321627.0）、（7345280.0）、（9939258.0）、（9976393.0）、（11260492.0）、
（11924364.0）、（16498676.0）、（16513827.0）、（21716731.0）、（21826340.0）、（23746537.0）、
（23751503.0）、（24412936.0）、（24423533.0）、（30287856.0）、（32321147.0.0）、（34243036.0）、
（37592142.0）、（39485706.0）、（41505243.0）、（42791620.0）、（52012206.0）、（52671472.0）、
（54652307.0）、（57293803.0）、（59242794.0）、（59252048.0）、（62535397.0）、（62563866.0）、
（62567154.0）、（64588902.0）}
102608
{（4167808,32784）、（6019974.32）、（6152844.16）、（9570536.64）、（10699806.33）、
（13290514.0）、（15064491.128）、（16432948.512）、（24473204.0）、（24655822.0）、
（25833075,256）、（28000951.64）、（30834507.2048）、（34567533.16）、（35766667.0）、
（37385121.0）、（40123805.512）、（43134386.1024）、（45439608.0）、（45484652.0）、
（47562525.0）、（52378153,256）、（52403136,512）、（52493894,1024）、（53483990,0）、
（54048767.0）、（54286279.2048）、（57401158.0）、（57956631.0）、（58183281.0）、
（61117236.32）、（61898065.0）、（61936634.0）、（64512205.512）、（65014849.0）、
（65112662.0）、（65259449.0）}

通信マスクでは、次のビットを設定できます。

• ラブ
• 配偶者または配偶者
• 親
• 赤ちゃん
• 兄か妹
• おじやおば
• 親Relative
• 親しい友人
• 同僚
• 同級生
• eph
• 祖父または祖母
• 孫または孫娘
• 仲間の学生
• 軍隊の友情
• 里親
• 里子
• ゴッドファーザー
• ゴッドファーザー
• スポーツの合同ゲーム

リレーションシップマスクにリストされているビットに加えて、ゼロビットが設定されている場合と設定されていない場合があります。 このビットは純粋に技術的な役割を果たし、物理的な意味はありません。 その結果、たとえば、タイプChildの関係は、数値16または17でエンコードできます。

データはApache Pigビッグデータストレージツールを使用して準備され、2つの対応するヘッダーファイルが含まれているため、参加者はデータの前処理/フィルタリングにこのツールを使用できます。

ユーザーの人口統計
人口統計データは、属性リスト形式のソーシャルリンク情報と同じ百万人のユーザーに提供されます。
userId create_date birth_date gender ID_country ID_Location loginRegion
ここで：

• userId-ユーザーID
• create_date-ユーザーアカウントの作成日（1970年1月1日からのミリ秒数）
• birth_date-ユーザーの生年月日（1970年1月1日からの日数、負の場合もあります！）
• 性別-ユーザーの性別（1-男性、2-女性）
• ID_country-プロファイルで指定された国の識別子
• ID_Location-プロファイルで指定された地域/都市識別子。
• loginRegion-ユーザーが最も頻繁にこのソーシャルネットワークにログインしている地域の識別子（存在しない場合があります！）

サンプルデータ：
44053078 1166032023073 3067 1 10414533690 2423601 99
12495764 1177932393270 1138
2 10405172143 188081
25646929 1165304175170 3756 2 10414533690 3953941 22
25646999 1160728984480 3884 2 10414533690 241372 120
12495833 1176909723643 3363 2 10414533690 2724941 11

人口統計は、グラフと同じスキームに従って分割されますが、圧縮されません（プレーンテキストとして送信されます）。 また、標準のApache Pigビッグデータストレージツールまたはその他のCSV対応ツールを使用して処理することもできます。

タスク

タスク4.2.1「生年月日」
分析のために表示されるソーシャルグラフのフラグメントには、ランダムに選択された数百人のユーザーの2段階の近隣にいる10万人のユーザーの関係に関する情報が含まれています。 参加者には、すべてのリンクを含むソーシャルネットワークグラフファイルと、年齢などのユーザーに関するデータを含む人口統計ファイルが提供されますが、すべてのユーザーについて年齢が示されるわけではありません。

グラフには存在するが人口統計には存在しないユーザーの場合、属性birth_date（生年月日）の値を設定する必要があります。

データは次の形式でファイルに書き込まれます。
（<ユーザーID> \ t（タブ）<生年月日>）

参加者の計算結果はtxtファイルで受け入れられ、参加者のデータと実際のデータの不一致を考慮する特別に作成されたプログラムによって完全なデータと比較されます。 不一致が小さいほど、チームの結果は高くなります。

問題の基本的な解決策は208ページです。

タスク4.2.2「地域」
分析のために表示されるソーシャルグラフのフラグメントには、ランダムに選択された数百人のユーザーの2段階の近隣にいる10万人のユーザーの関係に関する情報が含まれています。 参加者には、すべてのリンクを含むソーシャルネットワークグラフファイルと、地域を含むユーザーに関するデータを含む人口統計ファイルが提供されますが、すべてのユーザーに対して地域が示されるわけではありません。

グラフには存在するが、人口統計には存在しないユーザーの場合、ID_Location属性（地域）を設定する必要があります。

応答は次の形式でテキストファイルに書き込まれます。
（<ユーザーID> \ t（タブ文字）<ID_Location>）

参加者の計算結果はtxtファイルで受け入れられ、参加者のデータと実際のデータの不一致を考慮する特別に作成されたプログラムによって完全なデータと比較されます。 不一致が小さいほど、チームの結果は高くなります。

213ページの問題の基本的な解決策。

タスク4.2.3「関係の検索」
分析用に表示されるソーシャルグラフの断片には、ランダムに選択された数百人のユーザーの2段階の近隣にいる100万人のユーザーの関係に関する情報が含まれています。 参加者には、ユーザーごとにグラフと人口統計ファイルが提供されます。 提供されたソーシャルグラフの接続の一部は非表示になっており、参加者のタスクはそれらを完全かつ正確に明らかにすることです。

リンクの非表示は元の100万のユーザーのみに影響し、属性IDを11で割った残りは7（id％11 == 7）であり、これらの各ユーザーのリンクの約10％は非表示でした。 元の百万につながる通信のみが隠されていました。

予測では、コミュニケーションの存在を復元するのに十分であり、そのタイプは重要ではありません。 予測結果は、次の形式のCSVファイル形式で提示する必要があります。
ユーザーID1候補ID 1.1候補ID 1.2候補ID 1.3
ID_2 ID_2.1 ID_2.2

ID ( ), ( , ). :
5111 178542 78754
18807 982346 1346 57243

(Normalized Discounted Cumulative Gain, NDCG), . , , . ,
, . - , 0.

216 .

, -. (9 10-11 ) , . 3 . . . ( ) — 0 20 .

1.3.4 (5 )
0˚ 180˚ . ( ) 100 , ( ) — 500 . , .



, .

, -. — 2 .
. . . 0 8 .

:
2.1.4 (3 )
() . :

x y . x 1 3, y — 2 5.

x y, a b. .

:
a = 4.03 b = 74.64

:

, .

: , , , .

, - ,
( «»).

:


- «»

— , «» .



, , (. 3, 4). , .


«».

, , , – .
, :

• ;
• ;
• («») ;
• , ;
• «».

, :

• ,
• ,
• .

, , («»). 10 1 . «» . . .