Yandex Data Analysis Schoolの入学試験を解決する方法

夏は入学試験の時期です。 現在、Yandex Data Analysis Schoolへの選択は完了間近です。すでに試験に合格している人へのインタビューが進行中です。 ShADは、機械学習、コンピュータービジョン、自然言語テキスト分析、および現代のコンピューターサイエンスの他の分野を教えています。 2年間、学生は大学プログラムに含まれない科目を研究しますが、科学と産業の両方で大きな需要があります。 モスクワだけでなく、エカテリンブルク、ミンスク、キエフ、ノボシビルスク、サンクトペテルブルクに支部があります。 また、メールで勉強したり、ビデオ講義を見たり、モスクワ学校の教師とやり取りしたりできる通信部もあります。



ただし、SHADに参加するには、ウェブサイトのフォームに記入し、入学試験に合格し、面接を受けるための3つの段階を経る必要があります。 毎年、モスクワ州立大学、モスクワ物理技術大学、ITMO、サンクトペテルブルク州立大学、UrFU、NSUの学部生、卒業生、大学院生がShADに来て、全員がテストに対応しているわけではありません。 今年、3,500人からアンケートを受け取り、そのうち1,000人が試験に合格し、わずか350人が合格しました。

自分で試して、彼の能力を理解したい人のために、今年の入学試験のレビューを用意しました。 私たちがあなたのために選んだオプションで、それを決めた人の56％が管理しました。 この表では、その中の各タスクを解決できた人数を確認できます。

タスク	1	2	3	4	5	6	7	8
決めた	57％	68％	40％	35％	29％	12％	20％	6％

しかし、初心者のために、私たちが試験でテストするものと、そのコンパイルにどのようにアプローチするかを説明したいと思います。 ShADが誕生して最初の数年間は、筆記試験は行われませんでした。アプリケーションがまだ少ないため、オンラインテストに直接合格したすべての人と話をすることができました。 しかし、その後、インタビューは長くなりました。 一部の卒業生は、6時間にわたってどのように彼らと話したかを思い出し、多くの困難な課題を提供しました。 その後、より多くの応募者がいました-そして、2012年に筆記試験が登場しました。

モスクワSHADのキュレーターは、バリアントの作成に携わっています。その1つは私です。 ブランチの同僚がタスクの選択を手伝います。 バリアント内のタスクの数は、この4年間であまり変化していません。最初は7でしたが、昨年は8になりました。 各バージョンには、数学の問題（5〜7）とアルゴリズムの問​​題（1〜2）があります。

数学に関しては、もちろん、申請者がプログラムの主要なセクションである代数、数学的分析、組み合わせ論、および確率論を所有しているかどうかを確認します。 しかし、詰め込みによって達成され、テストや試験の1週間後に忘れられるのは、不定積分の表や生徒の分布関数からのひどい公式のように、私たちにとって重要な知識ではありません。 そのため、応募者は筆記試験にあらゆる紙の資料を持ち込むことができます。 何が起こっているのかを理解することは、はるかに価値があります。また、異常な状況で標準的な事実と方法を適用する能力も重要です。 また、計算の複雑さを最小限に抑えます。 2桁の数字でもまれに乗算する必要があります。 そのため、試験では、日常的で退屈な計算の練習は見つかりません。また、多くのタスクは非標準的で、おそらくオリンピックのようにも見えます。

アルゴリズムに関する部分では、特定のデータ構造（検索ツリー、ハッシュテーブルなど）またはアルゴリズム（高速ソートアルゴリズム、グラフ上の最短パスを見つけるためのアルゴリズムなど）の知識を必要とするタスクを回避します。 さらに、申請者は、プログラミング言語で本発明のアルゴリズムの実装を作成する必要はありません。 それどころか、私たちはあらゆる面でそれを思いとどまらせます。 実際、筆記試験では、私たちが最も興味を持っているのはプログラミングスキルではなく、アルゴリズムを明確に説明し、必要に応じて、作業時間と割り当てられたメモリ量の制限を満たしていることを読者に納得させる能力です。 ただし、読むことができる任意の言語のコードを含む決定も受け入れられますが、検証が難しく、さらに、正当性を正当化する必要があります。

タスク1

シーケンスの制限（a _n ）を見つける

タスク2

側面10と側面20を持つ同一の長方形（側面に隣接する長方形）でタイル張りされた平面で、半径4のランダムな円を描きます。円がちょうど3つの長方形と共通の点を持つ確率を求めます。

タスク3

DimaとVanyaは交互に2n×2nマトリックスを埋めます。 Vaniaの目標は、結果のマトリックスに1の値を持たせることであり、Dimaの目標はそれを防ぐことです。 ディマが最初に歩きます。 それらのいずれかが勝利戦略を持っていますか？

タスク4

行列A =（a _ij ）の行列式を見つけます。ここで、

タスク5

整数の2つの配列a [1..n]およびb [1..k]が与えられ 、 bのすべての要素が異なります。 セットa [i_1]、...、a [i_k]が配列bの要素の順列であり、差i_k-i_1が可能な限り小さいインデックスセットi_1 <i_2 <... <i_kを見つける必要があります。 時間制限はO（nk）です （ただし、より高速に行うことができます） 。メモリ制限はO（nk ）です。

タスク6

2222年に、新しいシステムに従ってバレーボールトーナメントが開催されます。 AがBまたはBに勝つチームに勝った場合、チームAはチームB よりも優れていると言われます。各チームのペアは1回プレーします。 抽選はバレーボールルールによって除外されます。 チャンピオンは、他のすべてのチームを超えたチームとして宣言されます。 （a）チャンピオンが確実にいることを証明する（b）チャンピオンが正確に2人いることはできないことを証明する。

タスク7

積分を計算する

タスク8

n個のリンクを持つポリラインが平面に描かれます。 各リンクの長さは1で、隣接するリンク間の指向角は同様にαまたは–αになります。 開始点から終了までの距離の2乗の数学的期待値を見つけます。