Yandex.Algorithm 2014の最終タスクの分析

8月1日に、最近ベルリンに開設されたYandexオフィスが、プログラミングチャンピオンシップの決勝戦を開催しました。 そして彼の勝者は、スポーツプログラミングに興味のあるすべての人、 Gennady Korotkevichに再び知られるようになりました。



アルゴリズムのタスクは、国際チームによって準備されました。 ロシア、ベラルーシ、ポーランド、アメリカのプログラマーが含まれていました。 これらはモスクワ州立大学のM.V.にちなんで名付けられた専門家です。 ロモノソフ、カーネギーメロン大学、Yandex、Googleの従業員。 Yandexでは、タスクはミンスクとキエフのオフィスの開発者であり、同僚でテストしました。 昨年のコンパイラの1人は、彼自身がアルゴリズムのファイナリストでした。 特にHabrahabrについては、著者に関するすべての問題を整理しました。 ところで、競争が終わったという事実にもかかわらず、あなたは仮想コンテストで自分自身を試すことができます。







多くのファイナリストが勝ったと主張しました。 その中には、ACM ICPCとTopCoder Openの勝者と入賞者、GoogleとFacebookの開発者がいました。 最終ラウンドでは、2013 Algorithm Evgeny KapunとShi Bisunの勝者、ACM ICPCチャンピオンMikhail Kever 、および世界で最もタイトルのあるスポーツプログラマーの1人であるPeter Mitrichevが戦いました 。 今年、アルゴリズム2013のタスクのコンパイラーであり、TopCoder Openの管理者でもあるSoejimo Makoto氏も賞を競うことにしました。



ジェナディ・コロトケビッチと東京大学の保坂和弘の間で、1位争いが燃え上がった。 最良の結果-ペナルティ時間の66分で4つのタスク-コロトケビッチがチャンピオンのタイトルを確認しました。 カズヒロは同じ数の問題を解決しましたが、ペナルティ時間（90分）以上を獲得し、2位になりました。 3位は清華大学の王Q子が勝ちました。彼は125分のペナルティで4つの問題を解決しました。

タスクA. 1024 Stack Edition

制限時間： 1秒

メモリ制限： 512メビバイト



最近、少女クセニアはオンラインストアでアプリケーション「1024 Stack Edition」を購入しました-ターンベースのアーケード。 名前が示すように、ゲームは2の累乗で満たされたスタックの周りで行われます。 ゲームのルールに従って、各ターンでプレイヤーはスタックで次の3つのアクションのいずれかを実行できます。

• スタックの最後に乱数を追加します。
• スタックから最後の番号を削除します。
• 最後の2つの数値が等しい場合、それらを合計で置き換えます。

プレイヤーがスタックに乱数を追加することを選択した場合、チャンスpで数字1がスタックに追加され、チャンス1- pで数字2が追加されます。プレイヤーがスタックから最後の数字を削除することを選択した場合、1コインの罰金を支払います。 スタックから最後のアイテムを削除する以外のすべての操作は罰金にならないことに注意してください。 勝つためには、プレイヤーはスタックを1つの要素（1024）だけの状態にする必要があります。さらに、ペナルティーが少なければ少ないほど良いです。



Ksyushaが電話を無人のままにすると、帰国後、誰かが「1024 Stack Edition」をプレイしていることがわかりました。 Ksyushaは、自分が誰であり、彼の動機が何であるかを知ることに興味がありません。 彼女は、罰金の数学的予想が何であるかを知りたいと考えており、ゲームをプレイする場合、彼女は個人的に最適なゲームに支払う必要があります。 ご想像のとおり、あなたの仕事はこの数を計算することです。



タスクAの解析



まず、 N = 0の場合を考えます 。 f（i）を数2 ⁱを収集するために費やさなければならないコインの予想最小数とする。 p <100の場合のf（i）の計算式を示します。p= 100の場合、同じ式が簡単に適用されます。

1. f （0）= 1.0 / p-1;
2. f （1）= min （ f （0）•2; 1 /（1- p ）-1、1-p）;
3. f（i） = 2• f （ i -1）、i> 1。

N = 0の場合、問題の答えはf （10）です。

ここで、 N > 0と仮定します。g（i、j）で、スタックの最後（上）のi要素から2 ^jを1つだけ取得するために必要な予想最小コイン数を示します。 固定iのg（i、*）の計算は2段階で行われます（ S（i）により、スタックのi番目の最上位要素のバイナリ対数を示します）。



1. g（i、S（i））= 1 + min（g（i-1; *））、i> 1を計算します。 このケースは、要素iの上のすべてから特定の番号を取得し、その後削除するという事実に対応します。



g（i、S（i）+ 1）= g（i-1、S（i））も計算します。 このケースは、 iの上にあるすべての要素から番号2 ^S（i）を収集し、それを2 ^S（i）に等しい現在の要素と結合するという事実に対応します。 S（i）およびS（i）+ 1以外のすべてのjに対して、 g（i、j） = + infを置きます。



2.最初の段階で、数S（i）を「形にした」。 g（i + 1、*）および数S（i + 1）に進む前に、スタックのi番目の要素でいくつかのアクションを実行し、他の要素に変換することができます。 これをダイナミクスで考慮するために、次のようにg（i、*）を再計算します。



• g（i、0）= min（g（i、0）、min（g（i、*））+ 1.0 / p） -すでに見つかった値g（i、0）を使用するか、任意の数を取るそれを削除してそこに1 = 2 ⁰を置き^ます 。

• g（i、j）= min（g（i、j）、min（g（i、*））+ 1 + f（j）、g（i、j-1）+ f（j-1）） 、j> 0 ここで、場所iにあった番号を削除してから、 f（j）コインに番号2 jを付けるか、 g（i、j-1）ステップに番号2 j − 1を付け、 f（j-1）のステップを収集します。 2 ^{j − 1をさらに増やし} 、それらを組み合わせます。



問題の答えはg（N、10）です。 中間計算では、 g（*、11）も考慮する必要があることに注意してください。 解の複雑さはO（NR）です 。ここで、 Rは入力に存在する2の最大電力です（この場合、 R≤10 ）。

問題B.ラインタスク

制限時間： 4秒

メモリ制限： 512メビバイト



検索クエリ-改善点 質問を入力するフィールド、「検索」ボタン-およびインターネット全体が回答の順序付けられたリストに組み込まれています。 毎日何百万もの検索クエリが保存されるため、将来より速く、より良い回答が得られますが、これだけでは十分ではありません。



ユーザーが検索クエリ自体をすばやく入力できるようにすることが重要です。 たとえば、ユーザーに人気のあるまたは興味深いクエリオプションを表示し、設定に従って並べ替えることができます。 しかし、誰が質問をしているのか分からない場合はどうなりますか？ 2つの手がかりを辞書編集順に提供するアルゴリズムを開発するように指示されます。 まあ、ほぼ辞書式です。



ユーザーは、リクエストを入力するときにタイプミスをする可能性があることが知られています。 行Aでラテンアルファベットの任意の小さい文字で1文字しか置換できず、行Aが行Bより辞書編集的に小さくなる場合、行Aは行Bよりほぼ小さいと言います。



N個のヒントワードが与えられます。 単語のペアの数をカウントします。最初のペアは2番目のペアよりもほとんど少なくなります。 順序を考慮してペアの数を計算する必要があります。2つの単語が相互にほぼ小さい場合は、両方のペアを検討します。



解析問題B



数行のsとwを考えます。 文字列sは 、1文字を置換することでsから取得できる辞書編集上の最小文字列s ^minが厳密にwより小さい場合にのみ、文字列wよりほぼ小さくなります。



ただし、見やすいように、文字列sからs ^minは 、「a」に等しくない最初の文字を文字「a」で置き換えることによって取得されます。 文字列sが文字 'a'のみで構成される場合、 s = s ^min 。 行s _iを検討し、 C _i - s ^min _i <s _jとなる行s _j （おそらくi = j ） の数を見つけます。 次に、 s ^min _i ≠s _iの場合はC _i -1を回答に追加し、そうでない場合はC _iを追加する必要があります。



C _iの値を見つけるには、2つの方法を使用できます。

• 行s _iをソート_し、バイナリ検索でC _iを見つけます。
• すべての行をtrieに追加し、実行してC _iを見つけます。

問題C.キューブ

制限時間： 2秒

メモリ制限： 512メビバイト



面には1〜6のさまざまな整数で番号が付けられた立方体が与えられます。Hexaminoも与えられ、そのすべてのセルには1〜6のさまざまな整数で番号が付けられます。



ヘキサミノをセルの境界に沿って曲げるだけで、カットできない場合は、面の番号が特定のキューブの面の番号と一致するように回転できる、特定のhexaminoからキューブを作成できるかどうかを判断します。



タスクCの解析



このタスクで注意すべき主なことは、hexaminoをさまざまな方向に曲げることができるということです。 これにより、1組の反対側の数字の相互の並べ替えだけが互いに異なる2つのキューブが生成されます（180度回転すると2組の反対側の数字が並べ替えられるため、3組すべての並べ替えは1組の並べ替えに相当します）。



さらに、いくつかの解決方法があります。 それらの1つは、次の手順で構成されます。

1. 対応するhexaminoセルの底面を使用してキューブを設定します。
2. 軸を中心とするキューブの4回転ごとに、キューブが回転し、下面が対応する番号のセルに当たるまで、hexaminoに沿って回転し始めます。
3. いくつかのターンで6つのセルすべてにアクセスする場合、答えは「はい」です。
4. そうでない場合は、右側と左側の番号を交換し、手順2からの手順を繰り返します。
5. この場合、どのターンでも6つのセルすべてにアクセスしなかった場合、答えは「いいえ」です。

11スキャンすべてを計算し、hexaminoの一致をチェックして（標準位置に戻す）、一致する場合は、キューブの反対側に番号を付けるために使用される数字のペアをスキャンの同じペアと一致させることもできます。

タスクD. UFO

制限時間： 1秒

メモリ制限： 256メビバイト



夜になると、UFOがVasiny Houseの近くにある湖に落ちました。 crash落時、湖の底部と海岸にあったrib骨自体とは対照的に、rib骨間の接合部は崩壊しました。



朝、ヴァシャは湖岸にやって来て、チタンの棒を見つけました。 これらのロッドがUFOスケルトンのエッジであり、おそらくいくつかのリブがまだ水中にあると仮定して、UFOが到着したスペースの最小の寸法を決定します。



問題Dの解決策



これは最も簡単な採用タスクです。 明らかに、平行六面体の寸法は、異なる長さのエッジの数以上です。 また、同じタイプの^K次元平行六面体の2 ^K-1エッジ、つまり、 Xの同一のエッジがある場合、 [（X-1）/ 2 ^{k − 1} ] + 1測定を使用することに注意してください。



したがって、上記の式で計算された測定値の合計数が現在の次元以下になるまで、昇順ですべての次元をソートします。 K = 21では、1つのタイプのエッジが2 ²⁰ > 10 ⁶になるため、検索は小さくなります。

タスクE.不完全な一致

制限時間： 1秒

メモリ制限： 512メビバイト



Artyomkaはマッチングが非常に好きです。 無向グラフでのマッチングは、ペアワイズの非隣接エッジのセットで、すでに含まれているエッジを削除せずにもう1つのエッジをマッチングに追加できない場合、不完全と呼ばれます。



無向グラフは、その頂点を2つのセットに分割して、グラフの任意のエッジが異なるセットの頂点を接続できる場合、2部グラフと呼ばれます。



Artyomkaには2部グラフが与えられました。 そのタスクは、1 000 000 007（10 ⁹ + 7）を法とする不完全マッチングの数を見つけることです。 あなたの仕事は彼を助けることです。



問題Eの解決策



この問題を解決するために、左ローブの頂点の数が少ないことに注意してください。



右ローブから1つの頂点を追加して、次のダイナミクスを検討します。f（i、j） -右ローブの最初のi頂点を調べた場合のエッジを配置する方法の数。エッジによって右ローブの頂点に接続できませんでした、1-頂点はエッジによって右ローブの頂点に接続できましたが、このエッジを配置しませんでした、2-頂点はエッジによって右ローブの頂点の1つに接続されました



したがって、右ローブの次の頂点を考慮すると、左ローブの頂点のマスクを再計算できます。 明らかに、答えを計算するとき、1のないマスクを考慮する必要があります。



したがって、3進レコードに単位を含まないすべてのValidMask 3進マスクの場合、答えは合計f（n ₂ 、ValidMask）です。

タスクF.ミュージックワールド

制限時間： 1秒

メモリ制限： 512メビバイト



更新されたYandex.Musicでは、音楽の推薦が以前よりもさらに優れています！ ユーザーがサービスの使用開始当初からリッスンする各トラックを考慮し、すでにリッスンしているトラックに応じて、推奨事項のプールを増やします。 プレーヤーには、推奨されるトラックがランダムに含まれているため、1日が含まれます。



しかし、Yandexサーバーは非常に高速であるため、ユーザーが現在聴いているトラックだけでなく、ランダムに選択された次のトラックのすべてのオプションを推奨できます。



ユーザーが最初のトラックを選択すると、アルゴリズムは先のN曲の推奨を自動的に構築します。 i番目の世代の各曲から、（ i + 1）番目の世代のKi（1≤Ki≤5）以下の新しい曲を取得できます。i番目の世代では、曲iに基づいて、現在の世代では、0からKiまでのjごとにj個の新しい曲が予測されます。



実験的研究はインディーのジャンルで行われたため、推奨されるトラックはすべて異なります。 曲の類似性に関するさまざまな収集統計を測定するために、トラックの各ペアの類似性が測定されます。 Yandex開発者がこの測定のメモリコストを推定できるように、（ N + 1）番目の世代の推奨プール内のトラックペアの数の数学的期待値を計算します。



問題Fの解決策



Y _iは、 i番目の世代の歌の数に等しいランダム変数を示します。 問題に対して提案された解決策は、生成関数の概念に基づいています。 慣れていない場合は、例えばウィキペディアの記事ru.wikipedia.org/wiki/Performance_function_of_sequencesで見つけることができます。



入力で指定されたランダム変数の生成関数を考えます 、そして

ランダム変数の関数も生成します 。



すべてのψiの明示的な形式と、φ1 （x）= xの明示的な形式があります。 φi +1をψiとφi で表現することを学びます。



Y _i = kであることが確実にわかっていれば、φi _{+ 1} （x）=ψi（x） ^kであると主張できます。 しかし、 Y _iはランダム変数であるため、望ましい生成関数は異なる値に対応する生成関数の合計であり、重みはこれらの値の確率に等しくなります。 。



必要な量の最大値は非常に大きいため、 Y _{n + 1の}生成関数の明示的な形式を計算することはできません。 ただし、彼は必要ありません。 計算される値は簡単にわかります







前の関数を使用して、（1）の関数φi _{+ 1} （x）の₁次および2次導関数である値を再計算する方法を学習します。 φi（1）=ψi（1）= 1であることを思い出します。ご存知のように、 φi _{+ 1} （x）=φi（ψi（x））です。 それから





置換x = 1を使用すると、これらの式は単純化され、次の形式を取ります。









また、10 ⁹ + 7を法としてすぐに計算を実行できることも理解しやすく、元の確率を対応する法値で置き換えます。