Yandex.Algorithm 2015の最終ラウンドのすべてのタスクの分析

本日、Yandexが主催するスポーツプログラミングチャンピオンシップであるYandex.Algorithmの決勝が終了しました。 2015年に、競争はYandex.Conestプラットフォームで完全にオンラインで行われました。 参加の申請は、73か国のプログラマーによって行われました。 参加者のほとんどはロシア、ウクライナ、ベラルーシ、カザフスタン、インド、アメリカ、日本、中国から来ていますが、一般的に選手権の地理は非常に広大です-ブラジル、インドネシア、ペルー、ドミニカ共和国、モザンビーク、セネガル、ケイマン諸島。 登録されている人の8.9％は女の子です。 参加者の約半数は学生です。 合計で、3722人から応募があり、そのうち28人が決勝に達しました。

Yandex.Algorithm-2015の勝者はGennady Korotkevichでした。 習慣から、彼は最高の結果を示し、最終ラウンドで6つの問題のうち5つを解決し、80分のペナルティ時間を受け取りました。 Gennadyは2013年と2014年にYandexチャンピオンシップで1位になりました。



2位はPeter Mitrichev、3位はEvgeny Kapunでした。 彼らはそれぞれ4つの問題を解決し、ピーターは31分、ユージンは79分を記録しました。 すべてのファイナリストの結果は、 Yandex.Algorithm Webサイトで表示できます。

Yandex.Algorithmのタスクは、Yandexの従業員と招待された専門家（ACM ICPCおよびTopcoder Openコンテストの勝者とファイナリストを含む）の両方を含む国際チームです。 そして、従来、すべてのタスクの分析を準備してきました。 誰もそれらのすべてを解決できませんでした。 ほとんどの参加者はタスクBに対処しましたが、タスクAとDはそれぞれ1人で解決しました。

タスクA.タスクマネージャー

分析と問題の作者は、Gleb Evstropovです。 MSU卒業、2回金メダリストACM ICPC。

研修生のBomboslavは、Yandexの従業員が使用するタスクマネージャーの改善に取り組んでいます。 マネージャーの現在のバージョンは、従業員に割り当てられたn個のタスクのそれぞれに、2つのパラメーターc _iおよびu _i-このタスクの重要性と緊急性を関連付けます。 パラメータ値が高いほど、特定のタスクの重要度または緊急度が高くなります。

どの従業員も、自分に割り当てられたタスクを実行する順序を選択できます。 唯一の制限は次のとおりです。タスクiがタスクjよりも重要かつ緊急の場合、つまりc _i > c _jおよびu _i > u _jの場合、それはより早く完了する必要があります。

Bobmoslavは、推奨システムをタスクマネージャーに追加することを決定しました。これにより、既存のタスクを完了するために必要な順序がわかります。 このような注文を作成するのは簡単すぎるため、Bomboslavは従業員が各タスクの値p _iを示す機能を追加しました。これは、このタスクを実行することで得られる喜びを意味します。 異なるタスクのp _iの値は異なる必要があります。

n個のタスクのそれぞれに対してp _iの値が示された後、システムは従業員に実装の順序を提供する必要があります。まず、必須の制限に違反しないようにし、次に、これらのタスクに対応するp _i値のシーケンスが辞書式に最大になるようにします。 言い換えれば、重要性と緊急性の制限を満たすタスクのすべてのシーケンスから、最初に実行されたタスクから従業員が受け取る喜びが最大になるものが選択されます。 そのようなオプションがいくつかある場合、2番目に完了したタスクの喜びが最大になるオプションが選択されます。

入力形式 入力の最初の行には、1つの数値n-この従業員のタスク数（1≤n≤100 000）が含まれます。
次のn行は、マネージャーのタスクを説明しています。 それぞれには、3つの非負整数c _i 、 u _iおよびp _iが含まれています-それぞれ、従業員がこのタスクを実行する重要性、緊急性、および欲求（0≤c _i 、u _i 、p i≤10 ⁹ ） 。 すべてのp _iがペアごとに異なることが保証されています。

出力フォーマット。 従業員がすべてのタスクを実行するための正しいシーケンスを印刷します。このシーケンスでは、対応する数量p _iのシーケンス_が辞書的に最大になります。 タスクには、入力に現れる順番で番号が付けられます。 各タスクは、シーケンス内で1回だけ発生する必要があります。 答えが常に唯一のものであることを示すのは簡単です。

問題Aの解決策

最小のソースを繰り返し抽出する貪欲なアルゴリズムを使用できるため、すべてのp _iの差の条件が不可欠であることに注意してください。 アルゴリズムのより詳細な説明：

1. 最適な回答のプレフィックスを作成し、元のグラフから特定のサブグラフのみが残ります。
2. 現在のグラフの多くのソース、つまり、エッジを含まない多くの頂点を考慮してください。 明らかに、現在のトポロジ分類は、このセットに属する頂点のいくつかによって継続されなければなりません。 これらのピークをアクティブと呼びます。
3. すべてのp _iは辞書式比較の構造により異なるため、次の頂点は一意に決定されます。 最大のp _iを持つアクティブな頂点を現在の応答プレフィックスに追加し、グラフから削除します。

アルゴリズムのテキスト記述を単に実装する場合、このソリューションの漸近的な複雑さはO（V∙E）です。 Oの漸近的挙動（V∙logV + E）は簡単に達成できます-すべての頂点の現在の半入力角度を覚えて、要素をすばやく追加して最大値を抽出する機能を持つアクティブな頂点のセットをいくつかの構造に保存するだけです。 このような構造は、バイナリヒープまたはバランスの取れた検索ツリーです。

ただし、この問題では、グラフは暗黙的に指定されており、一般的に、 Eのサイズはn ²のオーダーである可能性があり、これらの制限には大きすぎます。 グラフから次のソースを削除した後、新しいアクティブな頂点をすばやく識別する方法を考え出す必要があります。

圧縮されたセグメントの2次元ツリーの概念に戻ります。 この構造の詳細な分析はここでは想定されていません。メモリから次元O（n∙logn）を持ち、グループクエリ（ O（log ² n）時間中に最大、最小、長方形の合計など）に応答できることだけを思い出してください。 この複雑さは、クエリ領域を1つの次元のO（logn）バンドに分割することによって実現されます。各次元については、セグメントの1次元ツリーの構造がすでに構築されています。 次に、これらの各バンドは再びO（logn）パートに分割されます。

x> x _iおよびy> y _iの形式のV角度ごとに、前の段落で示したパーティションを構築します。 次に、与えられた角度を構成するすべての基本領域が空になる瞬間に、頂点はアクティブなもののセットに分類されます。 各基本領域について、その中の現在のポイント数を維持するとともに、各ポイントについて、その角度を形成し、まだ空ではない基本領域の数を維持します。 ここで、特定の角度に該当するすべての基本領域ではなく、セグメントの2次元ツリーへのクエリで領域のパーティションを形成するそれらのO（log ² n）のみを意味することに注意してください。

アルゴリズムのステップは次のようになります。

1. 最大のパイを持つアクティブな頂点を選択し、アクティブな頂点のセットから削除します。
2. 与えられた頂点に対応する点を含むセグメントの2次元ツリーのすべての基本領域を考慮します。 この構造の特性によれば、 O（log ² n）しかありません。 そのような領域ごとに、カウンターを1つ減らします。
3. カウンターがゼロになったすべてのエリアについて、すべてのポイントのリストを考慮する必要があります-このエリアがそれらに対応する角度の拡大に含まれるように。 これらのリストは、メインアルゴリズムが起動する前であっても、事前に作成されます。 リスト内の各ポイントについて、カウンターも1つ減少します。
4. カウンターがゼロになったすべてのポイントについて、対応する頂点がアクティブな頂点のセットに追加されます。

合計実行時間： O（n∙log ² n） 、および占有メモリ。

タスクB.バスでのピクニック

問題と分析の著者はミハイル・ティホミロフです。 モスクワ州立大学卒業、Topcoder Open 2014ファイナリスト。

毎年夏、Yandexの従業員はYandex.Picnicで自然に出かけます。 自分の車を持っていない従業員のために、バスはオフィスから休憩所までレンタルされます。

バスを必要とする従業員の数に関する情報があります。 さらに、一部の従業員グループは、バスの同じ列の席に座りたいと考えています。 運送会社が提供するバスには、1列に6席があります。 注文する前に、従業員のすべてのグループを希望に応じて収容するために必要な6席の行数を決定する必要があります。

入力形式 最初の行には、単一の整数（1≤n≤100） -従業員のグループ数が含まれています。 次の行には、スペースで区切られた n個の整数a _i-グループサイズ（ 1≤a i≤6）が含まれています。

出力フォーマット。 1つの番号を印刷します。6席の最小行数で、希望に応じてすべてのグループに対応できます。

問題Bの解決策

一般的なアイデア：行の座席数が6を超えない場合、単純な貪欲なアルゴリズムが機能します。

明らかに、サイズ6、5、または4の各グループは別々の行に配置する必要があります。 サイズ3のグループはできるだけ密に配置する必要があります。 トリプルのペアの行、およびおそらく残りの1つは別の行に配置する必要があります。 実際、最適なパーティションには2つの行があり、それぞれに1つのトリプルが含まれているとします。 次に、トリプルの1つを、2番目のトリプルと同じ行にあるグループと交換します。 いくつかのそのような操作の後、記述された条件が満たされるようにすべてのトリプルを移動します。

次に、2つのグループと1つのグループを配置します。 ユニット以外のすべてを配置すると、ユニットの場所が明確に決定されます。使用された行の残りの空き場所を埋め、次に新しい行を次々に完全に埋めます。 デュースも同じように配置する必要があることは簡単にわかります。使用されている行の1つには少なくとも2つの場所がありますが、次のデュースをそこに配置します。

説明したアルゴリズムは、次のように簡単に説明できます。グループをサイズの降順で検討し、スペースが少ないがグループには十分な行にそれぞれを配置します。

問題C.製品全体

問題と分析の著者はオレグ・クリステンコです。 Yandex.Algorithm、Open Cupのコーディネーター、snarknewsプロジェクト。

N -1分数u_i / d_iが与えられ、 2≤u i≤Nおよび2≤d i≤Nの場合、すべてのu _iはペアごとに異なり、すべてのd _iはペアごとに異なります。 分母が素数の累乗であり、選択されたすべての分数の積が整数になるように、少なくとも1つ、最大でN / 10分数を選択します。

入力形式 最初の行には、単一の整数N（10≤N≤10 ⁶ ）が含まれています。 次のN-1行のそれぞれには、 u_i / d_i（2≤u _i 、d i≤N、u _i ≠u _j for i≠j、di≠dj for i≠j ）の形式の小数部が1つ含まれています。 数字と「/」記号の間にスペースはありません。

出力フォーマット。 2行印刷します。 最初の要素には整数M-選択した分数の数が含まれている必要があります。 次のM行には、入力と同じ形式で1行に1つずつ指定された分数自体を含める必要があります。 選択したすべての分数の分母は、素数の累乗である必要があります。つまり、 ここで、 p _iは素数、 k _iは正の整数です。 分数は任意の順序で表示できます。 1つの分数は1回しか選択できません。

複数の解決策がある場合は、いずれかを印刷します。 解決策がない場合は、最初の行に-1を出力します。

タスクCの解析

10 ⁵から2∙10 ^5までの Nの場合、 Nを超えない素数^の数はN / 10未満です。
P（N）以上の分数（P（N）はNを超えない素数の数）を選択する必要がある場合、問題には常に建設的な解があることを示します。

次のように選択します。 まず、分数N / 2を選択します。 Nが偶数の場合、回答が受信されます。 Nが奇数の場合、分母として最小の素数Nをもつ分数を選択します。 分子が偶数の場合、最初の2つの小数が答えです。 分子を分母で割ると、2番目の小数が答えになります。 次の各ステップで、分母として前の分子の最小の素因数を持つ分数を選択しようとします。 この番号がi番目のステップで分母に既にあることが判明した場合、i番目の端数から最後に選択された端数までのセクションが答えです。 それ以外の場合は、適切な分数を選択します。 したがって、最悪の場合、分母としてNを超えないすべての素数を選択します。その後、繰り返しが必然的に発生します。

タスクD.団結して征服する

分析と問題の作者は、Gleb Evstropovです。

少し前まで、Yandexの従業員は、ネットワーク経由で送信するための大量の順序付けられたデータの最適な断片化のためのアルゴリズムの特許を取得しました。 今、彼らは断片化されたデータの中から既に断片化されたテンプレートを見つけるという課題に直面しています。 かなり複雑に聞こえますが、特にあなたの助けを借りて、彼らはこのタスクに挑戦する準備ができています。 私たちは彼らのやる気を起こさず、すぐに問題の声明に進みます。

1〜5のn個の数字で構成される初期シーケンスa _iがあり、ソースデータの断片化における連続部分のサイズを表します。 1から5までのm個の数字からなるシーケンスb _iもあり、同様にサンプルの断片化における連続部分のサイズを示します。

1つのアクションで、2つのシーケンスのいずれかで2つの隣接する要素を選択し、それらを組み合わせて、1つの要素をその合計に等しい値に置き換えることができます。 したがって、1回のアクションでシーケンス1、2、2から取得できるのは、シーケンス3、2および1、4だけです。 この操作を実行すると、要素が5より大きいシーケンスに表示される場合があります。シーケンスb _iがシーケンスa _iのサブストリング_になるために、これらのシーケンスで実行する必要があるアクションの最小数を計算する必要があります。

入力形式 入力の最初の行には、2つの整数nとmが含まれます。それぞれ、ソースデータのパーティション内のフラグメントの数と、検索用のテンプレートのパーティション内のフラグメントの数です（1≤n、m≤200 000） 。

次の行には、ソースデータのパーティション内のフラグメントのサイズを指定する、それぞれ1〜5のn個の数値a _iが含まれています。

最後の行には、テンプレートのパーティション内のフラグメントのサイズを同様の形式で記述するm個の数値b _iが含まれています。
出力フォーマット。 単一の整数-2番目のシーケンスが最初のシーケンスのサブストリングになるために必要なアクションの最小数を出力します。 これが不可能な場合は、 -1を出力します。

解析問題B

まず第一に、肯定的な答えがあるという多項式時間チェックの問題を解決する方法を学びます。 元のシーケンスの2つの境界を反復します。 シーケンスb _iが原則として選択したフラグメントa _iにマッピングできることを確認するにはどうすればよいですか？ すべての要素b _iの合計が、選択された要素a _iの合計_と等しいかどうかを確認します。 操作の数を制限することなく、すべての要素を1つにまとめることができるため、この条件が必要かつ十分であることは容易にわかります。

上記のアルゴリズムの複雑さはO（n ² + m）です。 すべての要素が正であるため、サブセグメントの合計は両方の境界に沿って厳密に単調な関数になることに注意してください。 2つのポインターの方法を使用して、時間O（n + m）における回答の存在を検証する問題を解決します。

シーケンスb _iの要素の合計が、あるシーケンスc _i （サブセグメントa _i ）の要素の合計に等しいことがわかっていると仮定します。 これらのシーケンスを同じにするために必要なマージ操作の最小数を定義します。 両方のシーケンスのプレフィックスがxに等しい任意の正数xを考えます。 これらの数字xの 1つは、すべての結合が完了した後、両方のシーケンスの最初の文字に対応します。 上記の要件を満たす₂つの異なるx ₁およびx ₂ （x ₁ <x ₂ ）が存在する場合、最小数の結合（したがって最大長）を持つ回答はx _2で開始することは決して有利ではないことがわかります。

実際、最終回答の各要素は各シーケンスb _iおよびc _iのサブラインに対応するため、このサブラインは常に2つに分割でき、要素x ₁およびx ₂ -x _{1を形成し}ます。 したがって、両方のシーケンスの接頭辞がxになるようにすべてのxを使用して、最適な回答を貪欲に入力できます。 そのようなxの数は、応答の長さ、したがって操作の数を決定します。

O（n）の興味深いサブセグメントを区別し、 O（n + m）の間にそれぞれの答えを見つける方法を学びました。 まだ遅すぎます。 両方のシーケンスですべての部分和を計算し、ビットマップでマークします。 次に、一致する要素の数の計算は、2つのビットシーケンスのスカラー積の計算に削減されます。 あるシーケンスと別のシーケンスのすべての接尾辞とのスカラー積の結果は、高速フーリエ変換を使用して計算できます。 解の最終的な複雑さ： O（cn・log（cn）） 、ここでcは要素a _iおよびb _iの上限です。

問題E.コンパクト行

問題と分析の著者は、Michal Forishekです。 Yandex.Algorithm 2013のファイナリスト、タスクACM ICPC、IOIの著者。

この問題では、小文字のラテン文字（「a」〜「z」）の文字列が考慮されます。 この文字列内の2つの同一の文字の間に同じ文字のみが見つかった場合、文字列はコンパクトと呼ばれます。 たとえば、文字列yandex、aacccb、eeeeeはコンパクトですが、文字列abaとaazbbzcはコンパクトではありません。

小文字のラテン文字と疑問符（ "？"）で構成されるテンプレートが提供されます。 各疑問符は任意の小文字のラテン文字を表し、NFindは、指定されたパターンに一致するさまざまなコンパクト行の数を示します。 答えは非常に大きくなる可能性があるため、 10 ⁹ + 7で割った余りを出力します。

入力形式 入力の最初の行には、整数t-テストケースの数（1≤t≤100）が含まれます。 次のt行はそれぞれ1つのテストケースを定義します。テストケースは、 1文字以上10 ⁴文字以下の長さのパターンです。 パターンは、小文字のラテン文字と疑問符のみで構成できます。

出力フォーマット。 各テストケースについて、1つの整数（それに対応するコンパクトな行の数を10 ⁹ + 7で割った余り）を出力します。

解析問題E

最初に、より単純なタスクを考えます。テンプレートが与えられた場合、それに一致する少なくとも1つのコンパクトな行がありますか？ このような問題は、単に線形時間で解決されます。すべての疑問符を削除し、結果の文字列がコンパクトかどうかを確認する必要があります。 したがって、決定の最初のステップはそのようなチェックになります。 合格しない場合は、0を出力します。

その後、いくつかの事前計算を行います。これは将来に役立ちます。同じ文字が左右に連続する疑問符（ z ??? zなど ）の行が表示されるたびに、疑問符は一意に開示できるため（この文字と同じになります）、このタスクのコンテキストでは、この文字列をそのような文字1つに置き換えることができます（つまり、フラグメントz ??? zがzに変わります）。

さらに、次の表記を使用します。

• Nは、指定されたパターンの長さを示します（このタスクでは10 ^4以下 ）。
• アルファベットのサイズを示すS （この場合は26）;
• このパターンで見つからないアルファベットの文字数を示すU。

U = 0の場合、問題は単純に解決されます。 連続する疑問符のブロックごとに、最初の文字がどこで終わり、2番目の文字がどこで始まるかは不明のままです。

たとえば、???? bブロックでは、疑問符を先頭の複数の（場合によってはゼロの）文字aに置き換えることができ、残りの疑問符は文字bに置き換えられます。 したがって、各ブロックのオプションの数は疑問符の数に1を足した数に等しく、ブロックは独立しているため、オプションの合計数はこれらの数の積に等しくなります。

一般的な場合、 U≠0の場合、追加のオプションが表示されます。テンプレートに含まれていない文字のうち、最終行に存在する文字と場所を特定する必要があります。 これらの文字はそれぞれ最終行の連続部分文字列を形成する必要があるため、そのような文字がどこかで発生した場合、その発生はすべて連続する疑問符の同じブロックに属している必要があります。

このような行の数を効果的に数える方法はいくつかあります。 考えられるアプローチの1つは、かなり標準的な方法を使用します。これらのすべての行を再帰的に生成し、一度に1文字ずつ追加してから、生成をメモ化によるカウントに置き換えます。 適切なアクションが正しく行われた場合、結果として、 O（NU）timeでの要求に応答するメモ化された再帰関数を取得します。

再帰関数は次の引数を取ります。

1. 処理するために残されたテンプレート内の文字数。
2. まだ使用されていない文字の数。
3. 処理された最後の文字のタイプ。

タイプは、次の4つの値のいずれかを取ることができます。

• 修正済み ：最後に処理された文字は文字であり、文字列に入れる必要があるためです。
• 過去 ：最後に処理された文字は疑問符であり、最後に処理された文字に置き換えることにしました。
• future ：最後に処理されたものは疑問符でした。これを将来テンプレートに表示される次の文字に置き換えることにしました（タスクはカウントのみであるため、どの文字であるかを知る必要はありません）。
• 未使用 ：最後に処理された文字は疑問符であり、以前に使用されたことのない文字に置き換えることにしました。

前の手紙の種類を知っていれば、次の疑問符を開示する機会を知っています。 たとえば、タイプがfutureの場合、 futureタイプはブロックのすべての文字になります。

さらに、わずかに高速なソリューションを提供する別のアプローチがあります。 初期化（ソリューションの存在を確認し、すべての自明なブロックを1文字に置き換える）後、連続する疑問符のS + 1ブロック以下を取得できることに注意してください：行の先頭にある場合があり、残りのブロックの開始前に、いくつかのブロックがあるはずです手紙。 初期化後、これらのすべての文字はペアごとに異なります。 したがって、ブロックの数は、アルファベットの文字数を1を超えて超えることはできません。

これで、組み合わせメソッドを使用して、パターンに一致するすべてのコンパクトな部分文字列をカウントできます。 これを行うには、連続する疑問符のブロックを処理する再帰関数を使用します。 したがって、関数には2つの引数があります。処理するブロックの数と、現在使用されていない文字の数です。

新しいブロックを処理するとき、このブロックで少なくとも1回使用する未使用の文字数のすべてのオプションを考慮します。 したがって、答えは、特定の未使用文字セットを選択する方法の数（二項係数）と、すでに選択されている文字をソートする方法の数（階乗）と、あるタイプの文字のチェーンが終了し、他の文字のチェーンが開始する場所（二項係数）の積と等しくなります残りの未使用の文字を使用して残りのブロックを埋める方法の数（再帰呼び出しの結果）。

したがって、 O（NU）時間を使用して、特定のモジュールの二項係数のテーブルを作成し、時間O（SU ² ）のユニット要求に応答するソリューションを取得します。

問題F.ランダムポイント

著者はイヴァン・カズメンコです。 サンクトペテルブルク州立大学の卒業生、サンクトペテルブルク州立大学とオープンカップの選手権のタスクの著者。

次の線形合同擬似乱数ジェネレーターを検討してください。 ジェネレーターには状態-整数s（0≤s <2 ³² ）があります。 間隔[0、X）で次の擬似乱数整数が必要になるたびに、ジェネレーターは変換S _new =（a∙S _old + c）mod2 ^{32を実行し}ます。 その後、 S _newはジェネレータの新しい状態になり、結果は数値として宣言されます 。

この問題では、 a = 134,775,813およびc = 1-これらの値は、Borland Delphi 7の組み込み擬似乱数ジェネレーターで使用されます。このジェネレーターは、座標が区間[0、100 000 000 ） ポイントを生成する2つの方法を検討してください。

最初の方法（コードネームRAW）では、ジェネレーターは初期状態sになり 、その後、希望する間隔で2n個の擬似乱数a ₁ 、a ₂ 、...、a _2nを順次生成します。 この後、 n個のランダムな点は、次の座標ペアによって定義されます： （a ₁ 、a ₂ ）、（a ₃ 、a ₄ ）、...、（a _2n-1 、a _2n ） 。

2番目の方法（コード名SHUFFLED）では、プロセスの始まりは同じです：ジェネレーターはいくつかの初期状態sになり、その後、希望の間隔で2n個の擬似乱数a ₁ 、a ₂ 、...、a _2nを順次生成します。 ただし、これらの_2n番号は、次のバージョンのFisher-Yatesアルゴリズム （擬似コード）を使用してランダムに再配置されます。

i = 1,2、...、2∙nの場合：
k =ランダム[0、i）+ 1
スワップ（a _i 、a _k ）

ここでrandom [0、i）は、区間[0、i）からの擬似乱数整数であり、その生成には同じジェネレーターが使用され、 swap（a _i 、a _k ）は数字a _iとa _kを交換します。 この場合i = kの場合、何も起こりません。 擬似コードの実行を開始する前に、ジェネレーターは、番号a ₁ 、a ₂ 、...、a _2nを生成した後に自分自身を見つけた状態にあります

番号a ₁ 、a ₂ 、...、a _{2 n}が再配置された後、最初の方法のように、 n個のランダムな点は次の座標のペアによって与えられます： （a ₁ 、a ₂ ）、（a ₃ 、a ₄ ）、 ...、（a _{2 n-1} 、a _{2 n} ） 。

nポイントのシーケンスが指定されています（10,000≤n≤100,000） 。 上記の2つの方法のいずれかで取得されることが知られています。 どのメソッドが選択されたか、および初期状態sが何であったかは不明です。 どのポイント生成方法が使用されたかを調べます。

入力形式 最初の行には、整数n-ポイント数（10000≤n≤100 000）が含まれます。 次のn行には、ポイントの説明が1行に1つずつ含まれています。 ポイントの各記述は、スペースxで区切られた2つの整数で構成されます-その座標xおよびy（0≤x、y <100,000,000） 。 条件に記載されている2つの方法のいずれかでポイントが取得されることが保証されます。

出力フォーマット。
最初の方法でポイントを生成した場合は「RAW」、2番目の方法で使用した場合は「SHUFFLED」を印刷します。

問題Fの解決策

一般的な観察。 生成された乱数が2 ³²個の数字の1つの循環シーケンスを形成していることを示すのは簡単です。 初期状態からは、この周期的シーケンスのどの要素が生成を開始するかのみに依存します。

最初の決定。 この解決策は確率論的です。つまり、1に近い確率で正しい答えを与えます。 主なアイデアは、2つの生成方法のうち1つだけに固有のプロパティを考え出し、このプロパティが満たされているか、ほとんど満たされていないことを確認することです。

このようなプロパティの簡単な例を次に示します。 小さい数k （たとえば、 k = 10 ）を修正します。 n点の座標を順番に生成します。 次に、長さkのポイントの連続サブシーケンスも、何らかの状態から開始する乱数の連続生成によって取得されます。 また、座標混合を使用してn個のポイントを生成する場合 、長さkのポイントの連続サブシーケンスが乱数の連続生成によって取得される確率は非常に小さくなります。

このプロパティをテストするソリューションは次のようになります。 十分に大きい数t （たとえば、 t = 10 ⁶ ）を修正します。 次のステップのうちtを実行します。ランダムな初期状態を選択し、座標を混合せずにkポイントを生成します。 各ステップで、 kポイントが、与えられたnポイントの中で連続したサブシーケンスとして出会うことを確認します。 これが少なくとも1つのステップで発生した場合、座標は混合せずに生成されたと答えます。 そうでない場合は、ミキシングが行われたと答えます。

kとtの選択された値で、それぞれの場合のエラーの確率は10-10以下であることが示されます。

各ステップで、 O（k）またはO（k log n）でチェックを行うことができます。最初に、 O（1） （ハッシュテーブル）またはO（ logn） （バイナリ検索ツリー）。 ソリューションの合計実行時間は、ハッシュテーブルの場合はO（n + tk） 、バイナリ検索ツリーの場合はO（n log n + tk log n）です。

2番目の解決策。 ミキシングがなかったとします。 最初の座標（x ₁ ）を生成した後、ジェネレーターの状態を復元してみましょう。 私たちはそれを知っています 。 sはほぼ等しい 。 このようなx _1の値を取得できるのは約43 の値だけ_です。 それらをすべて整理し、それぞれについて、さらに2n-1個の数値、y ₁ 、x ₂ 、y ₂ 、...、x _n 、y _{nを生成し}ます。 いくつかのsに対して、結果のポイントが指定されたポイントと一致した場合、明らかに混合はありませんでした。 そのようなものがなければ、明らかにミキシングが行われました。

このソリューションが正しく機能するためには、最初のいくつかのポイントのみを考慮するだけで十分であることに注意してください。各sについて、シーケンスは完全に一致するか、ほぼ即座に異なることがわかります。 残りの入力データは読み取ることさえできません。