🌧️ 📐 ⛹🏾 VKが3回目のチャンピオンシップVKカップを開始 👨🏽‍🤝‍👨🏻 🏗️ 🏅

みなさんこんにちは！ ソーシャルネットワークVKontakteは、Habréでブログを再開しました。

最初に話したいのは、VK Cup 2016スポーツプログラミングチャンピオンシップと、昨年のいくつかの興味深い問題の分析です。

チャンピオンシップについて一言。 VKは、ロシア語を話す若い専門家、学生、学童、そしてアルゴリズムとデータ構造の愛好家の間でのプログラミングチャンピオンシップである3番目のVKカップを開催します。

2人のチームが参加するよう招待されています（個人で参加できます）。年齢は14〜23歳です。予選ステージは3月から5月まで開催され、ベスト20チームが決勝に招待されます。ファイナルは7月にサンクトペテルブルクで開催され、上位8チームに賞が授与されます。

1位 -1048576ルーブル

2箇所-524288ルーブル

3箇所 -262144ルーブル

4-8箇所 -131072ルーブル

コンテストはCodeforces会場で開催されます。登録は既に公開されています- 急いでチームを登録してください！ 3月13〜14日と20〜21日に開催される資格段階から参加を開始します。 2つとそれらのいずれにも参加できます。すべての詳細は、チャンピオンシップページのリンクから入手できます。

一方では、VKカップチャンピオンシップはプログラミングチャンピオンシップの伝統に従い、参加者にアルゴリズムとデータ構造に関するタスクを提供します。一方、フォーマットを拡張しようとしています。そのため、昨年のチャンピオンシップでは、2つの珍しいラウンド（ワイルドカードラウンド1および2）が開催されました。

最初の段階では、参加者は簡単なタスクを提供されましたが、ラウンドの開始時にのみ解決できる言語を学びました。ラウンドの言語はあまり知られていないPicat言語でした。 2時間の競争の中で、参加者はこの言語の基本を学び、言語のいくつかの問題を解決しなければなりませんでした。たとえば、タスクの1つはレーベンシュタイン距離を計算することでした。

タスク条件

英語の文字で構成される行間のレーベンシュタイン距離は、ある行を別の行に変換できる一連のアクションの最小合計コストとして計算されます。許可されるアクション：

*置換：ある文字を別の文字に置き換えるコストは、アルファベットのこれらの文字のシーケンス番号の差に等しくなります。

*挿入/削除：文字列に文字を挿入したり、文字列から文字を削除したりするコストは、アルファベットのその文字のシリアル番号と同じです。

2行が表示されます。それらの間のレーベンシュタイン距離を見つけます。

参加者の1人が送信したソリューションは次のとおりです。

Picatソリューション

~~~~~ table(+, +, min) edit(I, J, Cost) ?=> str(S), goal(G), N = length(S), M = length(G), ( I <= N, J <= M, edit(I + 1, J + 1, NextCost), Cost = abs(ord(S[I]) - ord(G[J])) + NextCost ; I <= N, edit(I + 1, J, NextCost), Cost = ord(S[I]) - 0'a + 1 + NextCost ; J <= M, edit(I, J + 1, NextCost), Cost = ord(G[J]) - 0'a + 1 + NextCost ; I > N, J > M, Cost = 0 ). main => S = read_line(), G = read_line(), cl_facts([$str(S), $goal(G)]), edit(1, 1, Cost), println(Cost). ~~~~~

2回目のワイルドカードラウンドはその週に行われました。この間、参加者は、プログラミングの問題を解決するために最も正確な盗作検索アルゴリズムをコンパイルして実装する必要がありました。残念ながら、オンラインプログラミングコンペティションでは、一部の参加者が互いにソリューションをコピーし、わずかな（場合によってはそうではない）編集を行います。参加者は、一連のファイルを読み取り、同等のソリューションのグループを識別するプログラムを作成する必要がありました。ラウンドの勝者は盗作の発見で大きな進歩を遂げ、彼のソリューションは現在、詐欺師を探すためにCodeforceで使用されています。

そして、これは最初の予選ラウンドからの古典的なフォーマットの問題の例です。

例

犬のソーシャルネットワークVBudkeには、猫に関するダウンロード可能なクリップを圧縮するためのk個の特別なサーバーがあります。ダウンロード後、各ビデオはいずれかのサーバーで処理する必要があり、その後のみソーシャルネットワークに保存されます。

各サーバーは、1秒間に小さな断片を圧縮することが知られています。したがって、いずれのサーバーでも、長さがm分のビデオファイルはm秒で圧縮されます。

n個のクリップのそれぞれのソーシャルネットワークへのダウンロード時間は既知です（サーバーが一般的に起動した瞬間からの秒数）。すべてのビデオは異なる時点で到着し、受け取った順に処理されます。映画が時間sに到着した場合、その瞬間にすぐに処理を開始できます。すべてのサーバーが混雑しているため、一部のクリップは処理を待機する場合があります。この場合、サーバーが解放されるとすぐに、次の映画の処理がすぐに開始されます。保留中のローラーはキューに入れられています。処理の開始時に複数のサーバーが空いている場合、いずれかのサーバーが処理を開始します。

ビデオごとに、処理の終了の瞬間を決定します。

入力データ

入力の最初の行には、整数nとk（1≤n、k≤5・10 ^ 5）-それぞれクリップとサーバーの数が含まれています。

次に、n行で、ビデオの説明の後に整数のペアs_i、m_i（1≤s_i、m_i≤10 ^ 9）が続きます。ここで、s_iはi番目の映画が到着した秒単位の時間、m_iは分単位の持続時間です。すべてのs_iが異なることが保証され、クリップはロードの時系列順、つまりs_iの昇順で設定されます。

インプリント

n個の数字e_1、e_2、...、e_nを出力します。e_iは、i番目の映画が処理されるサーバーの開始からの秒数です。

条件の全文はこちらから入手できます。そこで自分で解決して、検証のために解決策を送信することができます。最も短気な人のために、ここにソリューションの説明があります。

ソリューションの説明

優先度キューを開始し、k個のサーバーのそれぞれの近い将来のリリースをそこに格納します。したがって、キューには常にk個の要素があります。標準言語ライブラリに組み込みの優先度キューがない場合は、単純に順序付きセットまたはヒープを使用できます。最小値を削除して要素を追加する操作が対数よりも長く機能しないことが重要です。次に、次のビデオs_i、m_iを処理するときに、e_i = max（s_i、A）+ m_iの時間に処理されることを理解するのは簡単です。ここで、Aはすべてのサーバーの最小リリース時間、つまり優先度のあるキューの先頭（または最上部）ヒープまたはセット）。したがって、e_iを導出し、キューの先頭から要素を削除してから、そこにe_iを追加する必要があります。

C ++でのそのようなソリューションの主要部分は次のとおりです。

 priority_queue<long long, std::vector<long long>, std::greater<long long>> q; int n, k; scanf("%d %d", &n, &k); for (int i = 0; i < k; i++) q.push(0); for (int i = 0; i < n; i++) { long long s, m; scanf("%lld %lld", &s, &m); s = max(s, q.top()) + m; printf("%lld\n", s); q.pop(); q.push(s); }

VKカップ2016でお待ちしています！チームを登録し、予選ラウンドに参加します。最初のイベントに参加する時間がない場合は、3月20〜21日に開催される2番目のイベントに参加できます。頑張って

VKが3回目のチャンピオンシップVKカップを開始

More articles: