Facebook Hacker Cupをまとめました。 世界中から11768人が参加したこのコンテストは、「オンザフライ」で3ラウンドの複雑なアルゴリズム問題を解決する形式で開催されます。 25人のファイナリストがパロアルトのFacebook本社に招待され、ファイナルマッチが行われました。
ポーランドから7名、ロシアから6名、アメリカから4名、日本から2名、中国、ドイツ、オランダ、シンガポール、スイス、ウクライナからそれぞれ1名が決勝に進みました。 全員がFacebookのオフィスで2日間を過ごすことができました。開発者と会い、Cafe Xで食事をし、カタンを演奏し、 RipStikに乗ろうとしました。
参加者はマシン（MacまたはPC）を選択する機会があり、その後、最終ラウンドが始まりました。 ファイナリストは、パーティータイム、最も安全な場所、エイリアンゲームの3つのアルゴリズムの問題をできるだけ早く解決する必要がありました。
結果は、各タスクのソリューションの準備が整うとすぐに裁判所に提示され、2時間のラウンドの終了時に、各参加者の合計ポイント数が計算されます。
Facebook Engineeringブログでタスクの条件を確認できます（ただし、要求があれば、後で翻訳してみることができます）。
その結果、私たちの同胞Pyotr Mitrichev（ 多くの同様の大会の参加者および勝者 ）が「ゴールド」になりました。
UPD＃1- Skiminokからの興味深い詳細：
また、勝者に関して驚くべき陰謀があったことを付け加えます。
ミトリチェフの主なライバルは、ACRushとしても知られるLou Tian Chengです。
この競争の原則は、3つのタスクのそれぞれが1ポイントで評価され、順位では、最もタスクの多いものが合格し、等しい場合、ラウンドの開始から各タスクに費やされた合計時間のあるものがより低いことです。 この場合、回答の最終チェックは、ラウンドが終了した後にのみ行われます。
そのため、ACRushはラウンド全体を通してMitrichevを上回っていました。 Mitrichevは同じタスクを引き渡しましたが、その数は常に同じでしたが、ACRushはより速くそれらを引き渡し、プチの勝利を望みませんでした。 そしてラウンドが終了し、最終チェックが行われ、ACRushは間違った答えで問題の1つを落とし、2つの点で自分自身を見つけ、2つの場所に落ちます。
UPD＃2-タスクの翻訳（ Skiminokに再び感謝）
タスク1.エイリアンのゲーム。
未知の惑星では、エイリアンは伝統的にロイテンと呼ばれるゲームをプレイします。 交代する2人のプレーヤーが関与します。 プレーヤーの前には、リンゴのバスケットN個が一列に並んでいます。 それらは、1から始まる整数で左から右に番号が付けられます。
各移動は、プレイヤーがバスケットの1つを選択することで構成されます。バスケットは、行の最初ではなく最後でもなく、リンゴの数は正であり、このバスケット内のすべてのリンゴを左側のバスケットに転送すると同時に、すべてを転送します右側のバスケットに。 はい、この本当に奇妙な惑星では、リンゴの数はマイナスになる可能性があります。 したがって、 x 、 y 、 zリンゴがそれぞれ3つの連続したバスケットがある場合、 yがゼロより大きい場合、それらで移動できます。 その結果、移動後、バスケットの数量はx + y 、 -y 、 z + yになります。 移動できないプレイヤーは負けます。
あなたはポポという名前の未知の惑星の住民の一人と知り合いです。 彼はロイテンの素晴らしい選手であり、ロイテンの惑星選手権の決勝に行った。 試合の前日、彼はどういうわけか、それぞれのバスケットにいくつのリンゴが入っているかを知りました。 残念ながら、彼はあまり良い記憶を持っていません、そして彼はバスケットにあるリンゴの数をP番で忘れていました。 彼は、この数値が絶対値でFを超えないことを覚えているだけです。
今、彼はあなたに勝つチャンスを計算するように頼みます。 優秀なプレイヤーはチャンピオンシップの決勝戦に進み、勝つチャンスを最大化するために常に最高の動きのみを行います。 プレーヤーが勝てない場合、同点がカウントされます。 ポポが勝つバスケットNo. Pにあるリンゴの可能な数を調べる必要があります。 ポポは、ゲームの最初の動きをするのは彼であると確信しています。
入力データ
入力の最初の行には、テストの数である単一の整数Tが含まれています。 各テストは、2つの整数を含む行で始まります： N 、バスケットの数、およびP 、リンゴの数が不明なバスケットの数。 次の行には、 N個の整数（対応するバスケット内のリンゴの数）が含まれています。 この行のP番目の数値は、 P番目のバスケット内のリンゴの数の制限に対応する正の整数Fです。
インプリント
出力ファイルには、テストごとに1行のT行が含まれている必要があります。 各行には、Pthバスケットのリンゴ数の可能な勝ち値の数、対応するテストへの答えがあります。
制限事項
T = 50
1≤P≤N≤2,000。
1≤F≤1,000,000,000,000。
ゲームの開始前に、各バスケットのリンゴの数は絶対値で1,000,000,000,000を超えません。
タスク2.安全な場所。
ビッグギャラクティックパーティーの295周年に向けて、あなたは突然不意にハイパースペースから追い出され、センサーによると、あなたはN個の宇宙爆弾に囲まれています。 疑いもなく、あなたは未知の卑劣な敵によって設定されたtrapに陥り、ハイパースペースに戻ることはできません。そして今、あなたはすべての爆弾の爆発を生き残るために近くで最も安全な場所を見つけなければなりません。 目に見えないライバルは、それを超えて飛び出すことのできない立方体の形で空間異常を作成しました。そのため、場所のオプションとして、この立方体内の点のみが利用可能です。
すべての爆弾が同時に爆発する前に、立方体[0、0、0]-[1000、1000、1000]内のすべてのポイントに到達するのに十分な時間があります。 あなたの直観がこれが最も安全な場所であるとあなたに言うので、あなたは最も近い爆弾までの距離が最大になるポイントを見つける必要があります。
入力データ
入力の最初の行には、テストの数である単一の整数Tが含まれています。 各テストは整数N 、爆弾の数で始まり、その後に各爆弾の座標を指定する3 * N整数が続きます。
インプリント
出力ファイルには、テストごとに1行のT行が含まれている必要があります。 各行には、立方体の最も安全な点から最も近い爆弾までの距離の2乗があります。
制限事項
T = 50
1≤N≤200
爆弾のすべての座標は[0、1000]以内です。
タスク3.パーティーの時間
あなたは友達のためにパーティーを開いていますが、友達の全員がお互いを知っているわけではないので、友達の何人かがパーティーを好まないのではないかと恐れています。 この状況を避けるために、あなたはあなたの友人の何人かの友人を招待することも決めました。 しかし、素晴らしいパーティーに招待するのは誰ですか？
幸いなことに、あなたはあなたの友人とあなたの友人の友人との間のすべての関係の詳細を知っています。 グラフ理論の観点では、ソーシャルグラフのサブグラフGがあり 、その頂点は友人とその友人（あなたを数えていない）に対応し、グラフの端は相互の友情を意味します。 さらに、招待された場合、 Gの各人がパーティーで食べる食べ物の量を正確に設定することができました。
Gから多くのゲストを選択します。 このゲストのセットには、すべての友人が含まれている必要があり、さらに、ゲストによって形成されたサブグラフGが接続されている必要があります。 2人のゲストが何か話すことがあるので、これは誰もがパーティーを楽しむのに十分だと思われます...
お金を節約するために、必要な食べ物の総量ができるだけ少なくなるように、非常に多くのゲストを選択することにしました。 これがいくつかの異なる方法で実現できる場合、ゲストの数が最も少ない方法が推奨されます。
ソーシャルグラフのサブセットGの人々/ピークには、0〜N-1の番号が付けられます。また、便宜上、友人には0〜F-1の番号があります。Fは招待する友人の数です。 Gは常に接続されていると仮定することもできます。 あなたが個人的にGに代表されていないことをもう一度思い出します。
入力データ
入力の最初の行には、テストの数である単一の整数Tが含まれています。 各テストの最初の行には3つの整数が含まれます。N - Gの頂点の数、 F-友達の数、 M -Gのエッジの数。次に、 M行、それぞれ2つの整数。 最初のそのような行には、2つの異なる整数uとvが含まれます。これは、人番号uと人番号vの相互の友情を意味します。 その後、テストの最後の行にはスペースを介したN個の整数が含まれます。i番目の数字は、人iが必要とする食物の量です。
インプリント
出力ファイルには、テストごとに1行のT行が含まれている必要があります。 各行には、スペースで区切られた2つの数字が含まれます。上記の条件を満たすパーティーの食事の最小合計量と、そのパーティーの最小人数。
制限事項
T = 50
1≤F≤11
F≤N -1
2≤N≤250
N -1≤M≤N *（ N -1）/ 2
Gは接続されており、ループや複数のエッジは含まれていません。
各人の必要な食物の量は、0〜1000の整数です。