Yandex.Algorithm 2017ファイナルの報告

先日、スポーツプログラミングのチャンピオンシップであるYandex.Algorithm 2017が終了しました。 最終ラウンドでは、25人のファイナリストが2時間半で6つの問題を解決しなければなりませんでした。 1位は、サンクトペテルブルクITMOのGennady Korotkevichが再び優勝しました。これは、2013年、2014年、2015年の大会後の4回目の勝利です。 チューリッヒのスイス高等技術学校のニコラ・ジョキッチと東京大学の卒業生である副島真が、 昨年の結果を繰り返して2位と3位になりました。 賞金の分配方法は次のとおりです。勝利-30万ルーブル、2位-15万、3位-9万。

Algorithm 2017への参加申請は4840人を提出しました。 それらの60％以上はロシア人です。 申請件数の2位はベラルーシで、続いてウクライナ、インド、中国です。 合計で、シンガポール、カメルーン、ベネズエラ、ペルーを含む数十カ国の住民が選手権に登録しました。

伝統により、私たちはフィナーレの問題に対する定式化と解体されたソリューションを公開しています。

タスクA.マウンテンチャレンジ

問題の著者 ：グレブ・エヴストロポフ（ヤンデックス、HSE）。

入力ファイル名：	出力ファイル名：	制限時間：	メモリ制限：
標準入力	標準出力	5秒（Javaの場合は13）	512メガバイト

競争のプログラミングとアルゴリズムの問​​題の解決にうんざりしていたArkadyは、少しの間休みを取り、職業を根本的に変えることにしました。 私たちのヒーローはいつも山に引き寄せられていたので、さまざまな競技で獲得した賞金を使って、小さなスキーリゾートを購入し、冬のシーズンに備えて準備を始めました。

利用可能な唯一のルートは $$$n$ から番号が付けられたチェックポイント $$$1$ 前に $$$n$ 。 チェックポイント $$$i$ 上にあります $$$h_i$ 、2つのポイントが同じ高さではありません。 高速道路にはエレベーターが1つしかないため、降下は常にチェックポイント番号から始まります $$$s$ チェックポイント番号で終了 $$$t$ 。 いくつか $$$m$ 制御点のペアは、より高い制御点からより低い制御点につながるルートのセクションによって接続されます。

チェックポイントに直接接続するルートの魅力 $$$u$ チェックポイント付き $$$v$ は、ポイントの高さの差に等しい、つまり $$$h_u-h_v$ 。 さらに、ルートの魅力、常にチェックポイントを訪れる $$$v_1、v_2、\ ldots、v_k$ サイトの魅力の最小値、つまり数量の最小値と呼ばれます $$$h_ {v_1}-h_ {v_2}、h_ {v_2}-h_ {v_3}、\ ldots、h_ {v_k}-h_ {v_ {k-1}}$ 。

一方で、アルカディアのリゾートを訪れる観光客は、ルートの魅力を気にかけ、もう一方で、ルートのルートのセクションの数として定義されるその長さを気にします。 Arkadyはもはやそのような問題を解決することができないため、可能なルート長ごとに計算するのはあなた次第です $$$x$ から $$$1$ 前に $$$n-1$ 可能な限り最大のルート魅力 $$$s$ で $$$t$ 少なくとも長さを持つ $$$x$ 。

入力形式

入力の最初の行には4つの整数が含まれます $$$n$ 、 $$$m$ 、 $$$s$ そして $$$t$ （ $$$2 \ leq n \ leq 100 \、000$ 、 $$$1 \ leq m \ leq 200 \、000$ 、 $$$1 \ leq s、t \ leq n$ 、 $$$s \ ne t$ ）-ルート上のコントロールポイントの数、ルートのセクションの数、開始コントロールポイントの数、および終了コントロールポイントの数。

2行目には $$$n$ 異なる整数 $$$h_1、h_2、\ ldots、h_n$ （ $$$0 \ leq h_i \ leq 100 \、000$ ）-コントロールポイントが配置されている高さ。

続いて $$$m$ ルートのセクションを説明する行。 で $$$i$ それらのうち2つの数字が書かれています $$$u_i$ そして $$$v_i$ （ $$$1 \ leq u_i、v_i \ leq n$ 、 $$$u_i \ ne v_i$ ）、という意味 $$$i$ ルートのセクションはチェックポイントから行く $$$u_i$ チェックポイントへ $$$v_i$ 。 ルートの2つのセクションが、コントロールポイントの高さと同じコントロールポイントのペアを直接接続しないことが保証されます。 $$$u_i$ チェックポイントの高さ以上 $$$v_i$ 、およびチェックポイントから少なくとも1つのルートがあること $$$s$ チェックポイントへ $$$t$ 。

出力形式

印刷する $$$n-1$ 行ごとに1つ、 $$$i$ そのうちのルートの可能な最大の魅力に等しくする必要があります $$$s$ で $$$t$ 以下の長さを持つ $$$i$ 。 一部の場合 $$$i$ それ以上のルートはありません $$$i$ その後、適切な行に印刷します $$$-1$ 。

例

標準入力	標準出力
4 4 2 4 3 4 2 1 2 4 2 1 1 3 3 4	3 1 1
3 2 1 3 3 2 1 1 2 1 3	2 -1
5 10 1 5 8 6 4 3 1 1 2 1 3 1 4 1 5 2 3 2 4 2 5 3 4 3 5 4 5	7 3 2 1

発言

最初の例では、開始コントロールポイントから最終コントロールポイントまでのルートの直接セクションがあります。 そのようなルートの魅力は $$$3$ 、および長さ $$$1$ 。 長さのパスもあります $$$3$ チェックポイントを通過する $$$2$ 、 $$$1$ 、 $$$3$ そして $$$4$ 、魅力が等しい $$$1$ 。 のために $$$x = 2$ 答えは、与えられた長さのパスになります $$$3$ 、これは少なくとも長さを持つ最も魅力的なパスであるため $$$2$ 。

タスクAの解析

すべてのコントロールポイントは異なる高さにあり、ルートのすべてのセクションは高いポイントから低いポイントに行くため、グラフは非周期的であることに注意してください。 トポロジの並べ替え（たとえば、頂点を高さで並べ替えるなど）を見つけて、引き続き操作します。

二次時間で問題を解決する2つの方法を説明します。 方法1：すべての可能な値を反復処理する $$$x$ ルートの魅力、そしてグラフにエッジのみを残す $$$（u、v）$ そのような $$$h_u-h_v \ geq x$ から最長のパスを見つける $$$s$ で $$$t$ そのようなリブのみを使用します。 そのようなソリューションの作業時間は $$$O（mC）$ どこで $$$C = h_s-h_t + 1$ 。 2番目の方法：動的プログラミング $$$d（v、len）$ -長さルートの最大の魅力 $$$len$ から $$$v$ で $$$t$ 。 値を計算するには $$$d（v、len）$ すべての発信エッジを考慮する $$$（v、u）$ リラクゼーションを使用します $$$d（v、len）= max（d（v、len）、min（d（u、len-1）、h_v-h_u））$ 。 そのようなソリューションの作業時間は $$$O（nm）$ 。

説明した2次の解決策の最初は、あまり楽しくないパスの答えをすばやく見つけ、2番目の解決策は短いパスの方が優れているため、これら2つのアプローチを組み合わせてみてください。 確かに、パスの長さ $$$x$ 彼の魅力が超えないことは事実です $$$C / x$ その逆もまた魅力的です $$$y$ 長さを超えることはできません $$$C / y$ 。 パラメータを紹介します $$$k = \ sqrt {C}$ 。 いずれにしても $$$s$ で $$$t$ その長さや魅力が超えないことは事実です $$$k$ 。 2番目の段落から両方のソリューションを適用し、最初の段落を $$$c \ leq k$ 、2番目の値のみを使用 $$$len \ leq k$ 。 結果として生じるソリューションの全体的な複雑さ： $$$O（m \ sqrt {C}）$ 。 必要に応じて、そのようなソリューションを使用して実装できることに注意してください $$$O（m）$ 余分なメモリ。

---

タスクB.無人車両

問題の著者 ：マキシム・アフメドフ（モスクワ州立大学ヤンデックス、HSE）。

入力ファイル名：	出力ファイル名：	制限時間：	メモリ制限：
標準入力	標準出力	4秒	512メガバイト

免責事項：このタスクで説明されている状況は、無人車の実際のプロジェクトとはほとんど関係がなく、独占的に競技者の想像力の産物です。

ご存知のように、最近、Yandexは無人車を開発しており、モスクワで開催されているコンペティション決勝の参加者の中には、自分で見る機会がある人もいます。 特別装備のトレーニング場での徹底したテストなしでは、無人車両の生産は不可能です。 このタスクの一環として、無人車両を木に見える埋立地に沿って移動できるかどうかを確認するよう求められます。

埋め立て地は $$$n$ 接続されたサイト $$$n-1$ 道路で。 パッドの番号は $$$1$ 前に $$$n$ 、無人車両は最初に $$$1$ 番目のサイト。 テストの目的は、車が1分間に1つの道路を走行していることがわかっていて、曲がり角や曲がり角の時間を無視できる場合、各サイトを少なくとも1回通るルートで最短時間で車を過ごすことです。

この実験のフレームワークでは、ナビゲーションは特別な無線ビーコンでのみ実行できるという事実により、タスクは複雑になります。 各サイトにはビーコンがあり、サイトに含まれるビーコンの料金 $$$i$ ちょうど十分に $$$a_i$ 分。 オフにすると、ビーコンは充電を消費しません。 最初は、すべてのビーコンがオフになっています。

移動のプロセスは次のように配置されます。 一度にオンにできるビーコンは1つだけです。 分の初めに車がサイトにある場合 $$$i$ 、ビーコンはサイトにあります $$$j$ そしてオンにした $$$t$ 分後、車は動き回る $$$t$ サイトまでの距離を短縮する道路 $$$j$ 。 車がすでにビーコンと同じプラットフォーム上にある場合、何も起こりません。 各ビーコンは、整数分の分、任意の回数オンにすることができます。

車が少なくとも1回すべてのサイトを訪れるように無線ビーコンのオン/オフ計画を作成できるかどうかを判断し、可能な場合は、これに必要な最小分数を見つけます。 開始サイトに戻る必要はありません 。

入力形式

最初の行には整数が含まれています $$$n$ （ $$$1 \ leq n \ leq 200 \、000$ ）-サイトの数。

2行目には整数が含まれます $$$a_1、a_2、\ ldots、a_n$ （ $$$0 \ leq a_i \ leq 10 ^ 6$ ）、ここで $$$a_i$ -サイトのビーコンに十分な充電がある分数 $$$i$ 。

その後に $$$n-1$ 行には、それぞれ2つの整数で構成される道路の説明が含まれます $$$u_i$ そして $$$v_i$ （ $$$1 \ leq u_i、v_i \ leq n$ 、 $$$u_i \ neq v_i$ ）-接続されたサイトの数。

出力形式

必要に応じて、すべてのサイトにアクセスするために必要な最小時間である単一の整数を出力します。 それ以外の場合は、番号を印刷します $$$-1$ 。

例

標準入力	標準出力
7 0 3 0 2 4 3 3 1 2 1 3 3 4 1 5 5 6 6 7	9
4 0 1 1 2 1 2 2 3 1 4	-1

発言

たとえば、最初のテストでは、条件から次のルートが適切です。

• 2分間、サイト4でビーコンを維持します。その結果、車はサイト4にあり、ビーコンは放電されます。
• 3分間、サイト2のビーコンをオンにしたままにします。その結果、車はサイト2にあり、ビーコンは放電されます。
• 2分間、サイト5のビーコンをオンにします。その結果、車はサイト5にあり、灯台は2分間充電されます。
• 2分間、サイト7のビーコンをオンにしたままにします。その結果、車はサイト7にあり、灯台の充電残量は1分間です。

したがって、9分ですべてのサイトにアクセスできます。

解析問題B

このタスクでは、通常とは異なる移動規則を使用してツリー内を移動する方法を理解できます。 凡例で使用されている車のタスクの代わりに、ツリーにチップがあり、ボタンがツリーの上部にあると仮定します。ボタンを1つ押すと、ビーコンを1秒間オンにすることになります。

したがって、ツリーがあり、その上部にチップがあり、その中にボタンのセットもあります：上部に $$$i$ 位置しています $$$a_i$ ボタンをクリックして、それをクリックして、ツリー全体で車を指揮する必要があります。

問題を解決するための有用な手法は、多くの場合、重要でない詳細によって異なる単純な問題を考慮することです。 この場合、最後のチップが必ず開始頂点に戻らなければならない設定を考慮すると便利です。 この定式化の際立った詳細は、そのような定式化では、チップが各エッジに対して少なくとも2回（1つの方向と他の方向に）通過する必要があることです。これは元の問題には当てはまりません。 いくつかの理由により、このタスクは元のタスクよりも簡単です。

正しい通過のルートを選択した後、各ボタンの動きを、渡されたエッジの端を越えて位置するツリーの部分のボタンに関連付ける必要があることに注意してください。 最適な検索ルートが少なくとも2回だけでなく、実際には正確に2回各エッジに沿って移動することは簡単にわかります。そうしないと、ボタンをより多くのエッジにマッピングする必要があり、明らかにより困難になります。

逆に、ボタンを各方向のエッジにマッピングできた場合、任意のいわゆる オイラーツリートラバース、および利用可能なマッピングを使用して、このトラバースを正常に完了します。

そのため、（単純化された設定での）問題に対する答えは常に $$$2n-2$ （そのようなオイラーツリートラバーサルの長さ）、およびチェックする唯一のことは、このエッジが指すサブツリーのエッジに対応するボタンの条件を満たすエッジにマッピングするボタンがあることです。 このタスクは、実際には、2部グラフ（1つは多くの方向付けられたエッジであり、もう1つは多くのボタンです）で一致するタスクであり、共有の1つを飽和させます。 ホール補題として知られるマッチング理論の古典的な事実は、そのようなマッチングの存在についての質問に答えます。

記法を紹介する-let $$$E$ これは、ツリーの多くの方向付けられたエッジです。 $$$B$ -たくさんのボタン、そして $$$s（e）$ のために $$$e \ in E$ これは、エッジが指すサブツリー内にあるボタンのセットです $$$e$ （正式に言えば、ボタン $$$b \ in s（e）$ リブの端の場合のみ $$$e$ rib骨の始まりの間にある $$$e$ とボタン $$$b$ ） ホールの補題は、方向付けられたエッジのセットの場合にのみ、私たちが求めるマッチングが存在すると述べています $$$A \サブセットeq E$ のすべてのエッジのサブツリーを結合する $$$A$ セットのエッジよりも少ないボタンはありません $$$E$ ：

$$

$$| A | \ leq \左| \ bigcup \ limits_ {e \ in A} s（e）\ right |$$

簡潔にするために、この不等式の右側にあるボタンのセットの結合を次のように示します。 $$$s（A）$ 。 この基準がサブセットの選択に対応する指数関数的な数の条件で構成されているため、この基準をどのように効果的に検証できるかはまだ明確ではありません。 $$$A$ 。 ただし、後で説明するように、テスト対象の条件のほとんどは冗長です。



まず、セット $$$A$ そのような $$$A$ 2つの方向に1つの同じリブがあるか、2つのリブがある $$$e_1$ そして $$$e_2$ お互いを見て $$$s（A）$ ツリー内のすべてのボタンのセットと一致します。つまり、そのようなセットの選択に関係なく $$$A$ 、同じエッジが不等式の右側にあります。 したがって、これらすべての不等式のうち、最も強いもの、つまり次のいずれかを検証すれば十分です。 $$$A$ と一致する $$$E$ 、このチェックは理にかなっています-実際、ツリー内のボタンの総数よりも指向性のあるエッジがないことをチェックします。 この状態を $$$（1）$ 。

そうでなければ、同様の方法で行動します。 もし $$$e \ in A$ 、その後、同じ方法でに追加することができます $$$E$ サブツリーにあるすべてのエッジ $$$e$ と同じ方向に見て $$$e$ （つまり、追加しても上記のケースにはなりません）。 実際、このようなエッジを追加しても、サブツリーで覆われているボタンのセットは変更されません。つまり、テストする条件が強化されるだけです。

これで、どの構造に多くのものがあるかが明確になりました $$$A$ および対応するボタンのセット $$$s（A）$ 。 多くの $$$A$ 互いに素なサブツリーのセットで構成されます。各サブツリーでは、サブツリーのルートからの方向を向いたすべてのエッジが使用されます。 $$$s（A）$ これらすべてのサブツリー上のボタンの組み合わせです。 すべてが多い場合は注意してください $$$A$ 満たされていない（すなわち $$$| A | > | s（A）|$ ）、コンポジション内のサブツリーの少なくとも1つ $$$A$ また、すべてのサブツリーの対応する不等式を合計することにより、セットが $$$A$ また満足しなければなりません。

だから、最終的にどのサブセットについて理解しました $$$A$ ホール補題からの基準を検証することで十分です：それは考慮することで十分です $$$2n-2$ サブセット。それぞれが「ルート」指向のエッジによって定義されます $$$e$ 、および方向を向いたすべてのエッジを含む $$$e$ サブツリー内 $$$e$ 。 繰り返しますが、このサブセットの不等式には明確な物理的意味があります-その中のボタンのサブツリーには、非指向性のエッジに1を加えたものが必要です（ここで、1つはルートエッジ自体から取得されます）。 方向付けられたエッジのこの状態を示します $$$e$ のために $$$（2_e）$ 。

状態 $$$（1）$ 明らかに、線形時間を確認できます。 条件 $$$（2_e）$ それ自体は線形の数値ですが、ツリーのサブツリーのサイズとその中のボタンの数を単純に計算することで、すべての条件が集約の線形時間をチェックできます。

したがって、問題の単純化されたバージョンを解決することを学びました。 元の状態に戻りましょう。各エッジに沿って両方向に移動することはありません。 私たちの道は今、最終的なピークによって特徴付けられていることが簡単にわかります $$$t$ 、それは必然的にシートであり、それから私たちが訪れた多くの方向のエッジから、 $$$t$ 開始ピークまで $$$1$ 。 上部に木を掛ける $$$1$ 、別の方法では、すべての立ち上がりエッジが $$$t$ 前に $$$1$ 。

同様に、ホール基準を適用し、どのような変化があるかを確認します。 お互いを見ているother骨についての議論はまだ真実であり、それは私たちに条件を与えます $$$（1 '）$ ：通過する方向付けられたエッジは、すべてのボタンにすぎません。 ここで正確に渡すことに注意してください $$$2n-2-深さ（t）$ したがって、この条件は、下限を目的の終端頂点の深さに設定します $$$t$ ： $$$depth（t）\ geq 2n-2-| B |$ （この条件は、次の場合に自動的に満たされることに注意してください。 $$$2n-2 \ leq | B |$ ）

方向付けられたエッジとそのサブツリーにあるすべてによって定義されたサブセットの基準の独立検証に関する議論はまだ真実ですが、これらのサブセットの形状はわずかに変わります。 すなわち、 $$$e$ -下を向いたエッジは彼にとって何も変わりません（単純化されたタスクと比較して、上を向いたエッジのみが消えたため）。 もし $$$e$ -エッジの見上げ、頂点の選択に応じて $$$t$ rib骨 $$$e$ 2部グラフから消える（その後、それに対応する条件を単に確認する必要がない）か、またはそれに対応する条件の左側が、サブツリーにあるドロップされたエッジの数だけ減少する $$$e$ と同じ方向に見て $$$e$ 。 左側の減少の大きさは $$$depth（lca（e、t））$ どこで $$$lca（e、t）$ rib骨の最小共通祖先です $$$e$ およびターミナルトップ $$$t$ 根がぶら下がっている木で $$$1$ 。

したがって、次の形式の一連の条件があります。

$$

$$2n-2-深さ（t）\ leq | B | \ quad（1 '）$$

下向きのエッジの場合：

$$

$$| edgeBelow（e）| + 1 \ leq | buttonsBelow（e）| \ quad（2_ {e \ downarrow} '）$$

見上げるrib骨の場合：

$$

$$| edgeAbove（e）| + 1-depth（lca（e、t））\ leq | buttonsAbove（e）|〜\ text {or}〜t〜\ text {in subtree}〜e \ quad（2_ {e \ uparrow} '）$$

条件 $$$（2_ {e \ downarrow} '）$ 線形時間は選択に依存しないため、すぐにチェックします $$$t$ 。 残りの2種類の条件を、頂点の位置に関する条件として定式化します。 $$$t$ 。 $$$（1 '）$ 、既に述べたように、頂点が $$$t$ 十分に低い、つまり、少なくとも深さ $$$2n-2-| B |$ 。 状態 $$$（2_e '）$ 所属と同等であることが判明 $$$t$ ツリーのサブツリー：実際、不等式の左側に移動する $$$（2_ {e \ uparrow} '）$ 期間 $$$depth（lca（e、t））$ 、下からピークの深さまでの制限を取得します。 $$$t$ への道から枝 $$$e$ 。 つまり、 $$$t$ 低くする必要があります（ $$$| edgeAbove（e）| + 1-| buttonsAbove（e）|$ ）からの途中のピーク $$$s$ 前に $$$e$ 、これはサブツリーに属する条件でもあります。

フォームの一連の条件「 $$$t$ 与えられたサブツリーに属します。「線形時間をチェックできます。ツリーを一周し、満たされた条件の数を維持し、この数が一般的な条件の数と一致する頂点をたどります。

最後に、すべての適切な頂点の最深部を選択し、条件が $$$（1 '）$ 、そして彼女は望ましい答えになります。 このソリューションは、入力データから線形時間で実装できます。

---

問題C.必要以上に密度が低い

問題の著者 ：マキシム・アフメドフ（モスクワ州立大学ヤンデックス、HSE）。

入力ファイル名：	出力ファイル名：	制限時間：	メモリ制限：
標準入力	標準出力	3秒	512メガバイト

無向グラフの密度は自然な量であり、頂点の数に対するエッジの数の比率に等しいと想定されます。 実生活から取得したグラフ（ソーシャルネットワークでの友情関係のグラフ、科学コミュニティでの共著グラフ、バイオインフォマティクスでのタンパク質間相互作用のネットワークなど）を含むさまざまなグラフの研究における重要なタスクは、密なサブグラフを見つけることです-つまり、このセットへのグラフの制限が高密度になるような頂点のセット。 高密度のサブグラフを見つけることはよく研究されていますが、かなり難しい作業です。このプロットを通常とは異なる外観で紹介します。少なくとも特定の密度のサブグラフを見つけることをお勧めします。

で構成される無向グラフを考えます $$$n$ からの整数で番号付けされた頂点 $$$1$ 前に $$$n$ 、そして $$$m$ rib骨 $$$（u_ {1}、v_ {1}）、（u_ {2}、v_ {2}）、\ ldots、（u_ {m}、v_ {m}）$ 。 のセットをしましょう $$$n$ 非負の実数 $$$x_1、x_2、\ ldots、x_n$ 条件を満たす $$$x_1 + \ ldots + x_n = 1$ 。 置く：

$$

$$\ lambda = \ sum \ limits_ {i = 1} ^ {m} \ min \ {x_ {u_i}、x_ {v_i} \}$$

少なくとも密度がこのグラフのサブグラフを見つけることが必要です $$$\ラムダ$ 。 正式には、そのような空でない頂点のセットを見つける必要があります $$$A \サブセットeq \ {1、2、\ ldots、n \}$ あれ $$$\ frac {| E（A）|} {| A |} \ geq \ lambda$ どこで $$$E（A）= \ {（u_i、v_i）〜\ mid〜u_i、v_i \ in A \}$ 。

入力形式

最初の行には2つの整数が含まれています $$$n$ そして $$$m$ （ $$$1 \ leq n \ leq 200 \、000$ 、 $$$0 \ leq m \ leq 200 \、000$ ）、グラフ内の頂点とエッジの数。

2行目には $$$n$ 実数 $$$x_1、x_2、\ ldots、x_n$ （ $$$x_i \ geq 0$ 、 $$$x_1 + \ ldots + x_n = 1$ ）小数点以下6桁以内で指定します。

で $$$i$ その後の $$$m$ 文字列は2つの整数です $$$u_i、v_i$ （ $$$1 \ leq u_i、v_i \ leq n$ 、 $$$u_i \ neq v_i$ ）接続された頂点の定義 $$$i$ グラフの端。 グラフには複数のエッジとループがないことが保証されています。

問題の要件を満たすサブグラフがグラフにあることが保証されます。

出力形式

最初の行に整数を出力します $$$k$ （ $$$1 \ leq k \ leq n$ ）-目的のセット内の頂点の数 $$$A$ 。

2行目で $$$k$ 整数 $$$d_1、d_2、\ ldots、d_k$ -少なくとも密度サブグラフを形成する頂点の数 $$$\ラムダ$ 。

導出したサブグラフの密度が以下である場合、回答は正しいとみなされます $$$\ lambda-10 ^ {-7}$ 。 頂点は任意の順序で表示できます。 可能な答えが複数ある場合は、正しいものを印刷できます。

例

標準入力	標準出力
4 4 0.2 0.1 0 0.7 1 2 2 3 3 1 3 4	3 1 2 4
5 6 0.25 0 0.25 0.25 0.25 2 1 1 3 3 5 5 4 4 1 1 5	4 1 5 3 4

発言

状態の最初のテスト： $$$\ lambda = \ min \ {0.2、0.1 \} + \ min \ {0.1、0 \} + \ min \ {0、0.2 \} + \ min \ {0、0.7 \} = 0.1 + 0 + 0 + 0 = 0.1$

頂点で構成されるサブグラフ内 $$$1$ 、 $$$2$ そして $$$4$ 、エッジは1つのみ $$$（1、2）$ 、したがって、その密度は $$$1/3> 0.1$ 。

条件の2番目のテスト：

$$

$$\ begin {eqnarray} \ lambda = \ min \ {0、0.25 \} + \ min \ {0.25、0.25 \} + \ min \ {0.25、0.25 \} + \ min \ {0.25、0.25 \} + \最小\ {0.25、0.25 \} + \最小\ {0.25、0.25 \} \ nonumber \\ = 0 + 0.25 + 0.25 + 0.25 + 0.25 + 0.25 = 1.25 \ nonumber \ end {eqnarray}$$

頂点で構成されるサブグラフ内 $$$1、5、3、4$ 5本の5骨 $$$（1、3）、（3、5）、（5、4）、（4、1）、（1、5）$ 、したがって、その密度は $$$5/4 = 1.25$ 。

タスクCの解析

明らかな事実に注意してください：与えられたグラフで最大密度の部分グラフを効果的に見つけることができれば、値のセットに関係なく、答えとして間違いなく適合するでしょう。 $$$x_i$ （答えが存在することが保証されているため）。 ただし、問題の状態で明確に伝えられるように、最も高い密度の部分グラフを見つける作業はかなり難しいため、与えられた値を何らかの方法で使用する必要があります。 $$$x_i$ ヒントとして。

次の事実は真実です。 置く $$$A（t）= \ {v〜\ mid〜x_v \ leq t \}$ 。 答えはあらゆる種類の中で常に見つけることができると主張されています $$$A（t）$ 、つまり、ソート順のある種の頂点サフィックスによって形成されるサブグラフ間 $$$x_i$ 常に少なくとも1つの密度サブグラフがあります。 $$$\ラムダ$ 。 この事実を示しています。

同様に設定します $$$E（t）= E（A（t））= \ {（u、v）〜\ mid〜x_u \ leq t、x_v \ leq t \}$ 。 機能を考える $$$f（t）= | E（t）| -\ラムダ| A（t）|$ 。 私たちは反対から議論します-半区間の各点で厳密にゼロ未満であると仮定します $$$[0、M）$ （これは単に $$$t$ 部分グラフ密度 $$$A（t）$ 等しい $$$\ frac {| E（t）|} {| A（t）|}$ 厳密に少ない $$$\ラムダ$ ）

で示す $$$M$ 最大数 $$$x_i$ 。 それから $$$\ int \ limits_ {0} ^ {M} f（t）dt <0$ 。 ただし、次の等式の連鎖は真です。

$$

$$\ begin {eqnarray} \ int \ limits_ {0} ^ {M} f（t）dt =＆\ int \ limits_ {0} ^ {M} | E（t）| -\ lambda \ int \ limits_ {0} ^ {M} | A（t）| \ nonumber \\ =＆\ int \ limits_ {0} ^ {M} \ sum \ limits _ {（u、v）\ in E} \ mathbf {1} \ {x_u \ leq t、x_v \ leq t \}〜 dt-\ lambda \ int \ limits_ {0} ^ {M} \ sum \ limits_ {v = 1} ^ {n} \ mathbf {1} \ {x_v \ leq t \}〜dt \ nonumber \\ =＆\ sum \ limits _ {（u、v）\ in E} \ int \ limits_ {0} ^ {M} \ mathbf {1} \ {x_u \ leq t、x_v \ leq t \}〜dt-\ lambda \ sum \ limits_ {v = 1} ^ {n} \ int \ limits_ {0} ^ {M} \ mathbf {1} \ {x_v \ leq t \}〜dt \ nonumber \\ =＆\ sum \ limits _ {（u、 v）\ in E} \ min \ {x_u、x_v \}-\ lambda \ sum \ limits_ {v = 1} ^ n x_v \ nonumber \\ =＆\ lambda-\ lambda = 0 \ nonumber \ end {eqnarray}$$

したがって、矛盾が発生します。つまり、少なくとも半間隔の1ポイントで $$$[0、M）$ 真の不平等 $$$f（t）> 0$ 、これは私たちの声明を証明しています。

したがって、決定は次の形式を取ります。頂点を降順で並べ替えます $$$x_i$ 、頂点を1つずつ追加し、現在のサブグラフの頂点の数を維持します。 密度がそれ以上なら $$$\ラムダ$ 、答えを印刷します。 結果として生じるソリューションの複雑さは $$$O（n \ log n + m）$ 。

---

タスクD.ハットショップ

問題の著者 ：ミハイル・ティホミロフ（MIPT）

入力ファイル名：	出力ファイル名：	制限時間：	メモリ制限：
標準入力	標準出力	2秒	512メガバイト

レイアウトされた店の窓の上 $$$n$ 左から右に番号が付けられた帽子 $$$1$ 前に $$$n$ 。 帽子には、男性用、女性用、ユニバーサルの3種類があります。 買い手は交代で店に入り、その後の各買い手は男性または女性のいずれかになることがあります。

各顧客はウィンドウを左から右に進み、自分に合った最初の帽子を選択します。 そのため、男性の買い手は男性の帽子と普遍的な帽子の中から一番左を選び、女性の買い手は女性の帽子と普遍的な帽子の中から一番左を選びます。 窓に適切な帽子がない場合、買い手は購入せずに立ち去ります。 誰かが帽子を購入するたびに、売り手は購入した帽子の数を書き留めます。

一日の終わりまでに、すべての帽子は売り切れ、売り手は次の番号の並び替えをしました。 $$$1$ 前に $$$n$ 。 この順列の可能なオプションはいくつですか？ 答えは非常に大きくなる可能性があるため、除算の残りの部分を決定する $$$10 ^ 9 + 7$ 。

入力形式

最初の行には単一の整数が含まれます $$$n$ （ $$$1 \ leq n \ leq 5000$ ）-ウィンドウ内の帽子の数。

2行目には $$$n$ 文字-番号順に帽子の種類。 記号「M」は男性の帽子、記号「W」は女性の帽子、記号「U」は普遍的な帽子を意味します。

出力形式

回答を除算した余りを出力します $$$10 ^ 9 + 7$ 。

例

標準入力	標準出力
3 UMW	2
3 MWU	4

発言

最初の例では、最初の買い手が間違いなく最初の帽子を（性別に関係なく）買います。 残りの2つの帽子は、任意の順序で購入できます。

2番目の例では、次の順列が可能です。 $$$（1、2、3）$ 、 $$$（1、3、2）$ 、 $$$（2、1、3）$ 、 $$$（2、3、1）$ 。

解析タスクD

いつでも、左端の男性、女性、および普遍的な帽子のいくつかを販売する必要があります。 $$$O（n ^ 3）$ 動的計画法：数量を数える $$$dp_ {m、w、u}$ -販売されている構成にいくつの方法が存在するか $$$m$ 最初の男性 $$$w$ 最初の女性と $$$u$ 最初の普遍的な帽子。

それだけが判明 $$$O（n ^ 2）$ DPのこのスキームの状態は達成可能です。 DPを使用して別のソリューションを提供します。 現在の構成では、 $$$i$ そして $$$j$ 男性と女性にそれぞれ適した売れ残り帽子の位置（適切な帽子が残っていない場合は、対応するインデックスを等しくする $$$n + 1$ ） すべての普遍的な帽子が位置の左側にあることを確認するのは簡単です $$$\ max（i、j）$ 販売する必要があります。 と仮定する $$$i \ geq j$ 。 男が帽子を買ったら、インデックスを動かすだけです $$$i$ 左に最も近い帽子に。 しかし、女性が帽子を買うなら、私たちは前進しなければなりません $$$j$ 汎用帽子をスキップします。 さらに、 $$$i = j$ それから $$$i$ 帽子は普遍的であり、性別に関係なく次の買い手がそれを購入するので、唯一の動きは動くことです $$$i$ そして $$$j$ 同時に最も近い適切な位置に。 その結果、漸近的解を得ることができます $$$O（n ^ 2）$ 。

---

タスクE.石を分割する時間

問題の著者 ：オレグ・クリステンコ（モスクワ州立大学、モスクワ工科大学）。

入力ファイル名：	出力ファイル名：	制限時間：	メモリ制限：
標準入力	標準出力	1秒	512メガバイト

遠い銀河のある惑星には、次の伝説があります。

時間の初めに、デミウルジュのヤン・デックスは世界で最も高い山に神殿を作りました。 寺院の中央には祭壇があり、その上に山があります $$$n$ 宝石。 毎朝、2人の司祭-教師と生徒-がこれらの石を分割し始め、山から順番にゼロではない数の石を取ります。 先生は最初の動きをします。 同時に、生徒は教師よりも多くの石を持てません。 結果として、石は均等に分割されるべきであり、単一の石が祭壇に残るべきではありません。

司祭がタスクを完了できないか、前日のいずれかの共有中に実行されたすべてのアクションを正確に繰り返すとき、悪霊破壊者バグが解放され、惑星を破壊します。

与えられた数の石 $$$n$ 時間の始まりからバグの到来までのこの世界の存在の最大可能時間を計算します。 答えは非常に大きくなる可能性があるため、次の値で割って残りを出力します。 $$$10 ^ 9 + 7$ 。

入力形式

入力の単一行には単一の整数が含まれます $$$n$ （ $$$1 \ le n \ le 10 ^ 6$ ）-祭壇上の宝石の数。

出力形式

整数を出力します-凡例に従って惑星が存在できる最大時間をモジュロ単位で $$$10 ^ 9 + 7$ 。

例

標準入力	標準出力
6	5
1	0

解析問題E

このタスクは、競争の中で最も簡単なタスクです。 実際、その中のよく知られた数学的構成の異常な再定式化を見ることが必要です。

石を分割するプロセスを再定式化します。 教師と生徒は順番に行くのではなく、任意の順序で進むと仮定しますが、生徒の石の数が常に教師の石の数を超えないという条件が満たされています。 このような再定式化は同等であることが容易にわかります。元の問題のイベントの展開の各シナリオは、再定式化されたタスクのシナリオと1対1で対応しています。

これで、石の数の条件は、\ texttt {'（'}記号が石を取っている教師に対応し、\ texttt {'）'}記号が石を取っている生徒に対応する行のブラケットシーケンスの正確性の条件と同等であることがわかります。 コンビナトリクスからよく知られているように、長さの通常のブラケットシーケンスの数 $$$k$ 等しい $$$k$ カタロニア語の数、式は次のようになります $$$\ frac {（2k）！} {k！（k + 1）！}$ 。 ここで、モジュロを慎重に計算する必要があります $$$10 ^ 9 + 7$ 、および問題の答えを取得します。番号が $$$n$ 奇数であり、答えは明らかに0です。

---

問題F. XORで遊ぶ

問題の著者 ：Lewin Gan（Dropbox）

入力ファイル名：	出力ファイル名：	制限時間：	メモリ制限：
標準入力	標準出力	2秒	512メガバイト

アリスとボブは次のリストで遊ぶ $$$n$ 整数 $$$a_1、a_2、\ ldots、a_n$ 。

アリスは最初に正の整数を選びます $$$k$ （必ずしもリストからではありません）、ボブに伝えます。 次に、アリスとボブは順番に動き、リストから整数を取り、リストが空になるまでボブが先に進みます。

ゲームの終わりに、アリスが彼女の番号の中から少しのサブセットを選択できるかどうかが決定されます $$$\ operatorname {XOR}$ -正確に合計する $$$k$ もしそうなら、彼女が勝ち、そうでなければボブが勝つ。

アリスがどの値を決定するのを助ける $$$k$ 彼女はこのエキサイティングなゲームで勝つことができます。

入力形式

最初の行には単一の整数が含まれます $$$n$ （ $$$2 \ leq n \ leq 15$ ）

次の行には $$$n$ 整数 $$$a_1、a_2、\ ldots、a_n$ （ $$$1 \ leq a_i \ leq 10 ^ 9$ ）

出力形式

単一の整数-値の数を出力します $$$m$ アリスが勝ちます。

次の行で $$$m$ 値を示す昇順の整数 $$$k$ アリスが勝ちます。

例

標準入力	標準出力
4 3 1 3 2	3 1 2 3

発言

, $$$k$ $$$1$ 、 $$$2$ そして $$$3$ 。 , , $$$k = 1$ 。 , $$$1$ , $$$1$ . , $$$2$ 。 $$$3$ , $$$1$ 形で $$$2 \operatorname{XOR} 3$ 。

F

:

• .
• $$$A,B$ $$$A+B$ $$$A-B$ .
• $$$span(A)$ , xor- $$$A$ (, ).
• $$$rank(A)$ , $$$span$ , $$$A$ 。

, $$$A$ 。 , , $$$B_1$ そして $$$B_2$ , $$$span(A+B_1) = span(A+B_2)$ そして $$$k \in span(A+B_1)$ 。 , $$$B_1$ そして $$$B_2$ $$$span(A)$ , $$$span$ $$$A$ 。

, $$$B_1,B_2$ $$$span(A+B_1) = span(A+B_2)$ そして $$$k \in span(A+B_1)$ , , .

$$$rank(A+B_1) - rank(A)$ , . 0, $$$k$ $$$span(A)$ , .

, $$$B_1,B_2$ 。 $$$B_1$ または $$$B_2$ , . , $$$B_1$ そして $$$B_2$ , $$$B_1$ そして $$$B_2$ , , , . $$$p$ , , $$$B_1$ それから $$$span((A+{p}) + B_1 - {p}) = span(A+B_1) = span(A+B_2) = span((A+{p})+B_2)$ $$$p \in span(A+B_2)$ 。 , $$$B_1' = B_1-{p}, B_2' = B_2$ 。

, $$$p$ から $$$B_1$ 。 , $$$p \notin span(A)$ , $$$rank(A+\{p\}) > rank(A)$ 。 , , $$$A + B_1$ そして $$$A + B_2$ $$$p \in (A + B_1) - (A + B_2) = B_1$ , $$$q$ で $$$(A + B_2) - (A + B_1) = B_2$ , $$$span(A + B_2 - \{q\} + \{p\}) = span(A + B_2)$ 。 , $$$B_1' = B_1 - p, B_2' = B_2 - q$ 。

. , $$$A$ , . , $$$B_1,B_2$ そのような $$$span(A+B_1) = span(A+B_2)$ そして $$$k \in span(A+B_1)$ 。

, . , , . , $$$rank(A+B_1) - rank(A)$ (, $$$B_1$ , — ).

$$$k \in span(A)$ , , 0 , ( ) $$$B_1$ そして $$$B_2$ 。

, $$$k \notin span(A)$ 。 , $$$p$ , $$$q$ . $$$X_1$ そして $$$X_2$ そのような $$$span(A+X_1+\{q\}) = span(A+X_2+\{q\})$ そして $$$k \in span(A+X_1+\{q\})$ 。 , , $$$k \notin span(A+X_1)$ ( $$$B_1 = X_1$ 、 $$$B_2 = X_2$ ）

, , , $$$q$ 。 $$$r$ . , $$$Y_1$ そして $$$Y_2$ そのような $$$span(A+Y_1+\{r\}) = span(A+Y_2+\{r\})$ そして $$$k \in span(A+Y_1+\{r\})$ (, , $$$k \notin span(A+Y_1)$ ）

, $$$q$ $$$X_1, X_2, Y_1, Y_2$ 。

$$$Z_1 = Y_2 + X_2 + \{r\}$ そして $$$Z_2 = Y_1 + X_1 + \{r\}$ 。

, $$$k \in span(A+Z_1)$ $$$k \in span(A+Y_2+\{r\})$ そして $$$A+Y_2+\{r\} \subseteq A+Z_1$ 。 , $$$span(A+Z_1) = span(A+Y_2+X_2+\{r\}) = span(A+Y_2+X_2+\{k\}) = span(A+Y_1+X_1+\{k\}) = span(A+Z_2)$ 。

$$$Z_1' = Z_1 - Y_1$ そして $$$Z_2' = Z_2 - Y_2$ 。 , $$$Z_1' \cap Z_2' = {r}$ 。 , $$$rank(A+Z_1') = rank(A+Z_1)$ , $$$y \in Y_1$ $$$span(A+Y_2+\{r\})$ , , $$$span(A+Z_1') = span(A+Z_2')$ 。

, $$$B_1 = Z_1' + \{q\} - \{r\}$ そして $$$B_2 Z_2'$ . , $$$k \not\in span(A+Z_1'-\{r\})$ , $$$q \in span(A+Z_1')$ , .

, , , — . $$$span$ $$$2 ^ n$ , $$$3^n$ ( $$$k$ $$$span$ ') $$$span$ . — $$$O(3^n \cdot n)$ 。