Yandex.Algorithm 2018：アリスの開発者による最適化トラックとMLタスク

A.見ているガラスの時間

制限時間1秒
512Mbのメモリ制限

Bomboslavが働くオフィスには、スタイリッシュなデザイナーウォッチがあります。 彼らのダイヤルには標準的なマーキングがあります：円には分に対応する60の目盛りがあり、そのうち12は（円の中心から上に位置する円から始まり、5目盛りずつ均等に）残りの部分よりも大きく、つまり時計に対応しています。 この時計はスタイリッシュで、ダイヤルには数字が含まれていないという事実があります。これは、誰もが現在の時刻の値に対応する区分をよく知っていると想定されているためです。

今日、そのような時計はボンボスワフの職場に掛けられていました。 それらを定期的にちらっと見て、彼は最初に矢印の方向にある奇妙なことに気づきました。 よく見ると、Bomboslavは実際に職場の上に鏡があり、時計が彼の後ろの壁にあることを発見しました。 これは、Bomboslavが、その中心を通る垂直軸に対してダイヤルが反映されていることを意味します。 今、彼は現在の現在の時刻をすばやく判断する方法を学びたいと思っています。これは、反映されたダイヤルに表示される時刻を知っています。

時計は、両針が別々に動くように配置されています。つまり、時針は常に現在の時間数に対応する12の主要な区分の1つを示し、分針は現在の分数に対応する60の区分の1つを示します。

入力形式
入力の単一行には2つの整数が含まれます $$$h$そして $$$m$（ $$$0 \ le h \ le 11$、 $$$0 \ le m \ le 59$）-反射ダイヤルの時針の位置と分針の位置。 $$$h = 0$時針が垂直に上を指していることを意味します $$$h = 3$厳密に右を指す矢印に対応し、 $$$h = 6$-矢印が下を向いており、 $$$h = 9$-厳密に左。 同様の指示が値の分針に適用されます。 $$$m = 0、m = 15、m = 30$そして $$$m = 45$。

出力形式
2つの整数を出力します $$$x$そして $$$y$（ $$$0 \ le x \ le 11$、 $$$0 \ le y \ le 59$）-クロックの現在時刻の実際の値。

解決策：
「直接」矢印と「反射」矢印の動きを考慮してください。 「直接」矢印が特定の角度だけ回転する間、「反射」矢印は同じ角度だけ回転しますが、他の方向、つまり矢印の回転の合計角度は最大回転に等しくなります。 各矢印について、その位置を個別に計算します。 1時間ごとの場合、これは12から現在の位置を差し引いたものであり、分については60-現在の位置を引いたものです。 どちらの場合でも、12または60をゼロに置き換えることを忘れないでください。

B.回文因子

制限時間1秒
512Mbのメモリ制限

Arkadyは、あらゆるタスクで機械学習を使用する大ファンです。 彼は、この人気のある若い科学の魔法の無限の力を信じています。 そのため、Arkadyは常に、さまざまなオブジェクトに対して計算できる新しい要素を常に増やしています。

回文は、最初から最後まで、そして最後から最初まで同じ方法で読み取られる行であることを思い出してください。 データベース内の各行について、Arkadyは最短サブストリングを見つけたいと考えています。これは少なくとも2文字で構成され、回文です。 そのような部分文字列が複数ある場合、Arkadyは辞書編集的に最小限のものを選択します。

入力形式
入力の1行には、Arcadiaデータベースからの1行が含まれます。これは、小文字の英語の空でないシーケンスです。 行の長さは少なくとも2で、200,000文字を超えません。

出力形式
入力データから文字列の最小の部分文字列を印刷します。これは、少なくとも2文字で構成され、回文です。 そのようなすべての行の中で、アルカディは辞書編集的に最小限のものを見つけたいことを思い出してください。

解決策：
パリンドロームであるサブストリングがあります。 最初と最後の回文文字を削除すると、残りの行も回文になります。 （パリティに応じて）2文字または3文字の行が残るまでこのプロセスを繰り返します。

長さ2または3の部分文字列の数は常に線形であり、その合計の長さも線形であるため、そのような文字列の中で、単純なアルゴリズムを使用して答えを選択できます。 この長さの部分文字列のいずれも回文ではない場合、導出 $$$-1$。

C.それらをすべて分離する

制限時間1秒
512Mbのメモリ制限

仕事の後、オリャとトリヤは一緒に射撃場に行くことにしました。 入門ブリーフィングを完了し、武器を受け取った後、彼らは発射位置にあり、それらの反対側は $$$n$ターゲット。 すべてのターゲットは、無限の平面に置かれた図形と見なすことができ、各ターゲットは円または長方形であり、ターゲットは任意に重なり、交差できます。

撮影を開始する前に、OlyaとTolyaは、撮影結果を一意に識別できることを確認したいと考えています。 これを行うために、彼らは、ターゲットを含む平面を2つの部分に分割する線を引くことに同意しました。 ただし、人を傷つけないように、各ターゲットが正確に半分に分割されるように直線を描画する必要があります。つまり、各円と各長方形について、線がそれを等しい面積の2つの図形に分割することが真実でなければなりません。

OlyaとTolyaが最終的にターゲットを2つの部分に分割するためのすべての条件を完成させたとき、彼らはそのような直接的な線を引くことが可能であることを疑い始め、この質問に答えるよう求めました。

入力形式
入力の最初の行には整数が含まれます $$$n$（ $$$1 \ le n \ le 100,000$）ターゲットの数です。 以下のそれぞれ $$$n$行には整数が含まれます $$$t_i$（ $$$0 \ le t_i \ le 1$）ターゲットのタイプを示します。 もし $$$t_i = 0$、ターゲットは円で、その後に3つの整数が続きます $$$r_i$、 $$$x_i$そして $$$y_i$円の中心の半径と座標をそれぞれ決定する（ $$$1 \ le r_i \ le 1000$、 $$$−10000 \ le x_i、y_i \ le 10000$） もし $$$t_i = 1$、ターゲットは長方形で、8つの整数によって決定されます $$$x_ {1、i}、y_ {1、i}、x_ {2、i}、y_ {2、i}、x_ {3、i}、y_ {3、i}、x_ {4、i}、 y_ {4、i}$-4つの頂点すべての座標（ $$$−10000 \ le x_ {j、i}、y_ {j、i} \ le 10000$）時計回りまたは反時計回りのトラバース順でリストされています。 これらの4つの頂点が非ゼロ領域の長方形を形成することが保証されています。

出力形式
既存の各円と長方形を同じ領域の2つの部分に分割する線がある場合は、「はい」を出力します。 それ以外の場合は「いいえ」を印刷します。

解決策：
この問題を解決するには、直線が円を2つの等しい部分に分割するという単純な幾何学的事実が必要です。 同様に、長方形の場合、対角線の交点を通過する場合にのみ、線はそれを等しい面積の2つの部分に分割します。 どちらの場合も、この点に関する対称性から十分であり、この点を介して所定の点に平行に直線を引くことで必要性を確立できます。

ここで、入力データで指定された数値のすべての中心が直線上で真であるかどうかを確認するだけです。 便宜上、中心の二重座標を考慮し、長方形の中心を取得するには、2つの反対側の頂点の座標を追加するだけで十分です。

構築されたポイントセットに2つ以下の異なるポイントしかない場合、答えは間違いなく肯定的です。 それ以外の場合、異なるポイントのペアを検討し、他のすべてのポイントがこのペアで定義された線上にあることを確認します。 3つのポイントを検証する最も便利な方法 $$$a$、 $$$b$そして $$$c$（ $$$a \ ne b$）1つの直線上にある-ベクトルのベクトル積を使用する $$$b-a$そして $$$c-a$。 ソリューションの全体的な複雑さ： $$$O（n）$。

D.インタビューのタスク

3秒の制限時間
512Mbのメモリ制限

アレクセイは定期的にインターンの候補者とのインタビューを行っています。 そして、彼はすでに100回以上のインタビューを行っていますが、最近このプロセスは容易ではありませんでした-候補者は、Alexeyのすべてのテスト済みタスクとテスト済みタスクを簡単に解決し始めました！

することは何もありません、そして、次のインタビューを見越して、アレクセイは新しい仕事を思いつきました。 最初のステップには2つの数字1からなる数値シーケンスがあります。次のステップの各ステップでは、2つの隣接する要素の間に合計に等しい新しい要素が追加されます。 最初のいくつかのステップの後、シーケンスは次のとおりです。
1 1
1 2 1
1 3 2 3 1
1 4 3 5 2 5 3 4 1

インタビューで、アレクセイは候補者に与えられた数のプログラムを書くように依頼したい $$$n$回数を決定します $$$n$順番に発生します $$$n$ステップ？ アレクセイは彼の問題を解決する方法をまだ学んでいませんが、彼が今インタビューする候補者がスポーツプログラミングで高い結果を達成したと聞いたので、彼はこの問題に簡単に対処する可能性があります。

入力形式
入力には単一の数字が含まれます $$$n$（ $$$1 \ le n \ le 10 ^ {13}$）

出力形式
数字の出現回数に等しい単一の整数を出力します $$$n$ステップの条件で記述されたシーケンスに $$$n$。

解決策：
いくつかの補題を証明しましょう。

補題1.あるステップで隣接することが判明した数値は互いに素です。

帰納法で証明します。 基本は明らかです（1と1は相互に単純です）。 証明してみましょう $$$n$ステップ。 に書かれたすべての数字 $$$n + 1$-番目のステップは合計です
隣の二人 $$$n$-数のステップ、つまり、互いに素な2つの数の合計。 しかし、GCD（ $$$a + b$、 $$$b$）= GCD（ $$$a$、 $$$b$）= 1。 補題が証明されます。

補題2.隣接する番号の順序ペアはありません $$$（a、b）$シーケンス内で複数回発生することはできません（単一のステップでも、異なるステップでも発生しません）。

させないで、番号をメモしてください $$$k$繰り返しが初めて発生したステップ（つまり、このステップまたは前のステップで存在したペアが繰り返された）。 カップルにしましょう $$$（p、q）$起源 $$$k$そして $$$i$ステップ（ $$$i \ le k$） しかし、その後 $$$p> q$それから $$$p$隣人の合計として建てられました $$$q$そして $$$p-q$（もし $$$p <q$それから $$$q$合計として構築されました $$$p$そして $$$q-p$）、つまり $$$k-1$そして $$$i-1$-番目のステップにも繰り返しがありましたが、これは私たちの仮定と矛盾しています。
補題が証明されます。

補題3.順序のある素数のペアは、いずれかのステップで必ず隣接します。

数字をいただけますか $$$pq$次のステップで立ってみましょう $$$p> q$（一般性を失うことなく）。 それから $$$p$量として受け取った $$$p-q$+ $$$q$、つまり、前の
ステップの隣に立った $$$p-q$そして $$$q$。 もし $$$p-q <q$その後、右に2ステップ戻ります $$$q$数がありました $$$2q-p$もし $$$p-q> q$次に、の左側に $$$p-q$数がありました $$$p-2q$などなど。 以来 $$$p$そして $$$q$
相互に単純である場合、いくつかのステップで、本質的に一種のユークリッドアルゴリズムであるこのプロセスは、一方でそれが判明するという事実につながります $$$1$そして他の-いくつか
自然数。 しかし、カップル $$$（1、x）$または $$$（x、1）$のために $$$x$上の隣接シーケンスになります $$$x$ステップ。 そして、アクションが明確に復元されるため、
これは、最初のペアが $$$（p、q）$ある時点で隣人として会います。

したがって、相互に素数の順序付けられた各ペアは、指定されたシーケンスのネイバーとして1回だけ発生します。 したがって、タスクは相互に素数の順序付けられたペアの数をカウントすることになり、合計で $$$n$。 以来 $$$p$そして $$$n$相互に単純な場合 $$$p$そして $$$n-p$相互に単純である場合、そのようなペアの数は、相互に単純な数の数に明確に対応させることができます。 $$$n$、またはオイラー関数の値 $$$n$。

そのような数の数を数えることはよく知られた問題であり、オイラー関数の乗法性に基づいています。 $$$n = p_1 ^ {k_1} \ cdot p_2 ^ {k_2} \ cdot \ ldots \ cdot p_n ^ {k_n}$、次に相互に単純 $$$n$
数字は $$$（p_1 ^ {k_1} -p_1 ^ {k_1-1}）\ cdot（p_2 ^ {k_2} -p_2 ^ {k_2-1}）\ cdot \ ldots（p_n ^ {k_n} -p_n ^ {k_n-1 }）$。 レイアウトする $$$n$経時的な素因数による $$$O（\ sqrt {n}）$。

E.バックアップ

5秒の制限時間
512Mbのメモリ制限

ユーザーデータの安全性を確保するために、Arkadyは常に新しいバックアップ組織スキームを発明し、テストしています。 今回、彼は1から $$$n$そして、1から $$$n − 1$バックアップコンピューターを割り当てた $$$p_i$。 同時に、バックアップ用のコンピューターの数は常にコンピューター自体の数よりも大きいという規則、つまり $$$p_i> i$。 このため、番号を持つコンピューター $$$n$バックアップ用のコンピューターはありません。

現在の実験中に、Arkadyは特定の値の構成を選択しました $$$p_i$1秒ごとにコンピューターの電源が切れます。 Arkadyがコンピューターの電源を切ると、実験は終了します $$$n$。 最初は、各コンピューターにサイズ1のデータブロックがあります。この番号のコンピューターの電源を切ると、 $$$x$、最初に配置されたサイズ1のデータブロックは、番号を持つコンピューターに転送されます $$$p_x$、コンピューター上の番号 $$$x$他のデータブロック（オフになっているときに他のコンピューターから受信）があった場合、それらは消えます。 コンピューターが $$$p_x$すでに切断されてから、コンピューターからのデータブロック $$$x$どこにも送信されず、また消えます。

Arkadyは実験をできるだけ長く続けたいと考えていますが、別の追加の制限を遵守することを余儀なくされています。 $$$k$データブロック、そして鉄を保持するために、このコンピューターはすぐに次の1秒以内にオフにする必要があります。 最後の1秒（その間にコンピューターの電源が切れる $$$n$）は考慮されません。

入力形式
入力の最初の行には整数が含まれます $$$t$（ $$$1 \ le t \ le20$）-テストケースの数。

次は $$$t$テストケースの説明。各説明は2つの整数を含む行で始まります $$$n$そして $$$k$（ $$$1 \ le n \ le 100,000$、 $$$2 \ le k \ le 10$）-実験に参加しているコンピューターの数と1台のコンピューター上のデータブロックの最大数。 2行目には $$$n − 1$数 $$$p_1、p_2、\ ldots、p_ {n − 1}$（ $$$i + 1 \ le p_i \ le n$）

出力形式
それぞれの $$$t$1つの整数を印刷します-実験の最大可能期間、つまり、Arkadyがその数値でコンピューターの電源を切ることができる最大秒数 $$$n$。

解決策：
タスクでは、ルートツリーが与えられ、各ステップでツリーの頂点の1つが削除されます。 さらに、頂点のルートがまだ削除されていない場合、その値は1増加します（最初はすべての値が1です）。 ある頂点の値が等しくなる場合 $$$k$、次のステップで削除されるのは彼女です。 ルート頂点が削除されるステップ番号を最大化する必要があります。

ルート頂点が以下の場合 $$$k-1$子孫の場合、頂点番号に触れる前にツリーのすべての頂点を削除できます $$$n$。 それ以外の場合、ルートのすべての子は3つのセットに分割されます：サブツリーが完全に削除されるもの、ルートがそのまま残るもの、および頂点自体を削除するルートを削除した後の1つのサブツリー $$$n$。 ツリーの深さを迂回し、動的プログラミングの3つの値をサポートします。

$$$a（v）$頂点を削除できる場合、特定のサブツリーで削除できる頂点の数に等しい $$$v$必ずしも最後ではありません。 それは簡単にわかります $$$a（v）$サブツリーのサイズに等しい。

$$$b（v）$頂点が次の場合、このサブツリーで削除できる頂点の数に等しい $$$v$手を加えないでください。 等しい $$$a（v）-1$上部にある場合 $$$v$少ない $$$k-1$息子。 それ以外の場合は、いくつかを選択する必要があります $$$k-2$値が使用される子孫 $$$a（u）$そして他の皆のために使用する $$$b（u）$。 そのように $$$k-2$最大の差でピークを取ることが有益な子孫 $$$a（u）-b（u）$。

$$$c（v）$頂点を削除できる場合、特定のサブツリーで削除できる頂点の数に等しい $$$v$ただし、サブツリーの最後に削除された頂点でなければなりません。 価値 $$$c（n）$そして問題への答えになります。 いくつか選択する必要があります $$$k-2$値が使用される子孫 $$$a（u）$、私たちが使用する1つの子孫 $$$c（u）$そして、他の皆のために、答えが追加されます $$$b（u）$。 どの子孫を使用するかを整理しましょう $$$c（u）$（つまり、誰が最後のリモート子孫になり、その後、頂点も削除されます $$$v$） さて、残りの中で、すべての値の合計を取る必要があります $$$b（u）$そして $$$k-2$最大 $$$a（u）-b（u）$。 これを行うには、すべての合計があれば十分です $$$b（u）$で並べ替えられた息子のリスト $$$a（u）-b（u）$。 トップの場合 $$$x$価値をとることにした $$$c（x）$最大の差で頂点をヒットし、次を使用します $$$k-1$top（そのようなことがあります。そうでない場合は、サブツリー全体を破棄します）。

ソリューションの複雑さ $$$O（n \ log n）$。

F.嘘つきプロセッサー

3秒の制限時間
512Mbのメモリ制限

Eugeneは新しい機械学習アルゴリズムをテストするために、 $$$n \ cdot m$サイズボードのユニットセルにあるプロセッサ $$$n \回m$。 したがって、プロセッサは $$$n$ランク付け $$$m$各プロセッサ。 この場合、2つのプロセッサーが同じ行の隣接するセルにあるか、隣接する行の同じ位置にある場合、2つのプロセッサーは隣接していると見なされます。

新しいアルゴリズムでの実験が失敗した結果、一部のプロセッサはユージーンに嘘をつくことを学びました。 ただし、アルゴリズムの基本バージョンのみが使用されたという事実により、一部のプロセッサが嘘をつき始めた場合、常にこれを行うため、その作業の結果を解釈することは依然として難しくありません。

現在、Eugeneは、どのプロセッサが常に間違った情報を提供しているかを判断するタスクに直面していますが、最初に問題の規模を評価したいと考えています。 これを行うために、彼は各プロセッサーに質問を送りました：それに隣接するプロセッサーの中に健全なプロセッサーと嘘つきプロセッサーの両方があるのは本当ですか？ ユージンの驚いたことに、すべての処理者はこの要求に肯定的に答えました。 今、彼は嘘つきプロセッサの最小数がボード上にあることができることを知りたいですか？

$$$n$そして $$$m$( $$$1 \le n \le 7$、 $$$1 \le m \le 100$) — .

— - , , -.

:
, $$$n \le 7$. $$$i$, $$$i - 1$. , , .

$$$dp(i, m_1, m_2)$, $$$i$1 $$$m$, $$$m_1$そして $$$m_2$— 0 $$$2^n - 1$。 -, , $$$i$, $$$i - 1$, $$$m_1$そして $$$m_2$. $$$O(m \cdot 2^{2n})$。 , $$$m_3$$$$dp(i + 1, m_2, m_3)$。

$$$O(m \cdot 2^{3n})$。 , $$$(m_1, m_2)$( $$$m_3$）

: , $$$O(nm 2^{2n})$。