„Live-Programmierung“: Wie verlief das ICPC Regional Semifinal an der ITMO University?

Anfang Dezember, dem Halbfinale der ICPC-Weltmeisterschaft für Studentenprogramme. Wir werden Ihnen sagen, an welchen „Versuchen“ die Teilnehmer teilgenommen haben und wer die Region Nord-Eurasien im Frühjahr beim Hauptweltturnier der Sportprogrammierer vertreten wird.


^{icpcnews / Flickr / CC BY / Final ICPC-2017}

Fünfzehn Gewinner

An vier Austragungsorten fanden gleichzeitig Wettbewerbe statt, an denen über 300 Teams teilnahmen: in St. Petersburg, Barnaul, Tiflis und Alma-Ata. Die ITMO-Universität hat mehr als hundert Teams aus Russland und den baltischen Staaten empfangen. Die Teilnehmer kämpften um den NEERC Northern Eurasia Cup und das Recht, das ICPC-Finale zu erreichen.


Das Team der Moskauer Staatsuniversität wurde der absolute Champion, nachdem es elf Probleme gelöst hatte. Das hat niemand mehr geschafft. Der zweite und dritte Platz waren Teilnehmer von MIPT. Der Fortschritt der "Schlachten" konnte live verfolgt werden. Auf dem ICPC-YouTube-Kanal gibt es eine Aufzeichnung:


Insgesamt wurden im Finale der ICPC-2019 fünfzehn Teams ausgewählt (die gesamte Liste finden Sie hier ), darunter auch Mitarbeiter der ITMO University. Ende März werden sie in die Stadt Porto (Portugal) reisen, um um den Weltmeistertitel zu kämpfen.

Wie verlief das Halbfinale?

Die Schüler verwendeten die Programmiersprachen Java, C ++, Python oder Kotlin. Alle Aufgaben erforderten Aufmerksamkeit, Konzentration und Kenntnis verschiedener Algorithmen.

Zum Beispiel wurde die folgende Aufgabe vom zweifachen Gewinner der ICPC als Teil des ITMO-Universitäts-Teams Gennady Korotkevich vorgeschlagen :

Es gibt ein ungerichtetes ungewichtetes Diagramm. Der Abstand zwischen zwei Eckpunkten u und v wird durch die Anzahl der Kanten auf dem kürzesten Weg bestimmt. Finden Sie die Summe d (u, v) aller ungeordneten Eckpunktpaare.

Zunächst werden zwei Zahlen n und m (2 ≤ n ≤ 10 ⁵ ; n-1 ≤ m ≤ n + 42) - die Anzahl der Eckpunkte bzw. Kanten - der Programmeingabe zugeführt. Die Eckpunkte sind von 1 bis n nummeriert. Als nächstes werden m Linien mit zwei ganzzahligen Werten eingegeben: x _i und y _i (1 ≤ x _i , y _i ≤ n; x _i ≤ y _i ) - dies sind die Endpunkte der i-ten Kante. Zwischen jedem Scheitelpunktpaar befindet sich mindestens eine Kante.

Beispielprogramm mit einer Lösung (vorgeschlagen von einem Jurymitglied):

C ++ - Code

#undef _GLIBCXX_DEBUG #include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0); int n, m; cin >> n >> m; vector<set<int>> gs(n); for (int i = 0; i < m; i++) { int x, y; cin >> x >> y; x--; y--; gs[x].insert(y); gs[y].insert(x); } long long ans = 0; vector<int> weight(n, 1); set<pair<int,int>> s; for (int i = 0; i < n; i++) { s.emplace(gs[i].size(), i); } while (s.size() > 1) { int i = s.begin()->second; assert(!gs[i].empty()); if (gs[i].size() > 1) { break; } s.erase(s.begin()); int j = *gs[i].begin(); gs[i].clear(); ans += (long long) 2 * weight[i] * (n - weight[i]); weight[j] += weight[i]; auto it = gs[j].find(i); assert(it != gs[j].end()); s.erase({gs[j].size(), j}); gs[j].erase(it); s.emplace(gs[j].size(), j); } if (s.size() == 1) { cout << ans / 2 << '\n'; return 0; } vector<vector<int>> g(n); for (int i = 0; i < n; i++) { g[i] = vector<int>(gs[i].begin(), gs[i].end()); } vector<int> id(n, -1); int cnt = 0; for (int i = 0; i < n; i++) { if ((int) g[i].size() > 2) { id[i] = cnt++; } } if (cnt == 0) { for (int i = 0; i < n; i++) { if ((int) g[i].size() == 2) { id[i] = cnt++; break; } } assert(cnt > 0); } vector<int> rev_id(n, -1); for (int i = 0; i < n; i++) { if (id[i] != -1) { rev_id[id[i]] = i; } } vector<vector<vector<vector<int>>>> edges(cnt, vector<vector<vector<int>>>(cnt)); for (int i = 0; i < n; i++) { if (id[i] >= 0) { for (int j : g[i]) { if (id[j] >= 0) { edges[id[i]][id[j]].emplace_back(); } } } } for (int i = 0; i < n; i++) { if ((int) g[i].size() == 2 && id[i] == -1) { vector<int> edge; edge.push_back(weight[i]); id[i] = -2; vector<int> fin(2); for (int dir = 0; dir < 2; dir++) { int x = g[i][dir]; int px = i; while (id[x] == -1) { assert((int) g[x].size() == 2); edge.push_back(weight[x]); id[x] = -2; int nx = px ^ g[x][0] ^ g[x][1]; px = x; x = nx; } fin[dir] = x; reverse(edge.begin(), edge.end()); } edges[id[fin[1]]][id[fin[0]]].push_back(edge); } } vector<vector<int>> dist(cnt, vector<int>(cnt, n + 1)); for (int i = 0; i < cnt; i++) { dist[i][i] = 0; } for (int i = 0; i < cnt; i++) { for (int j = 0; j < cnt; j++) { for (auto &p : edges[i][j]) { dist[i][j] = dist[j][i] = min(dist[i][j], (int) p.size() + 1); } } } for (int k = 0; k < cnt; k++) { for (int i = 0; i < cnt; i++) { for (int j = 0; j < cnt; j++) { dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]); } } } vector<vector<vector<vector<long long>>>> edge_pref_sum(cnt, vector<vector<vector<long long>>>(cnt)); vector<vector<vector<vector<long long>>>> edge_pref_sum_by_pos(cnt, vector<vector<vector<long long>>>(cnt)); for (int i = 0; i < cnt; i++) { for (int j = 0; j < cnt; j++) { edge_pref_sum[i][j].resize(edges[i][j].size()); edge_pref_sum_by_pos[i][j].resize(edges[i][j].size()); for (int k = 0; k < (int) edges[i][j].size(); k++) { edge_pref_sum[i][j][k].resize(edges[i][j][k].size() + 1); edge_pref_sum_by_pos[i][j][k].resize(edges[i][j][k].size() + 1); for (int t = 0; t < (int) edges[i][j][k].size(); t++) { edge_pref_sum[i][j][k][t + 1] = edge_pref_sum[i][j][k][t] + edges[i][j][k][t]; edge_pref_sum_by_pos[i][j][k][t + 1] = edge_pref_sum_by_pos[i][j][k][t] + (long long) edges[i][j][k][t] * t; } } } } auto get = [&](int i, int j, int k, int from, int to, int coeff_from, int coeff_to) -> long long { if (from > to) { return 0; } assert(0 <= from && to <= (int) edges[i][j][k].size() - 1); long long ret = (edge_pref_sum[i][j][k][to + 1] - edge_pref_sum[i][j][k][from]) * coeff_from; if (coeff_from != coeff_to) { assert(abs(coeff_from - coeff_to) == to - from); long long other = edge_pref_sum_by_pos[i][j][k][to + 1] - edge_pref_sum_by_pos[i][j][k][from]; other -= (edge_pref_sum[i][j][k][to + 1] - edge_pref_sum[i][j][k][from]) * from; ret += other * (coeff_from < coeff_to ? 1 : -1); } return ret; }; for (int v = 0; v < cnt; v++) { long long w = weight[rev_id[v]]; for (int j = 0; j < cnt; j++) { ans += dist[v][j] * w * weight[rev_id[j]]; } for (int i = 0; i < cnt; i++) { for (int j = 0; j < cnt; j++) { for (int k = 0; k < (int) edges[i][j].size(); k++) { int x = dist[v][i]; int y = dist[v][j]; int cc = (y - x + (int) edges[i][j][k].size() + 1) / 2; cc = min(max(cc, 0), (int) edges[i][j][k].size()); ans += w * get(i, j, k, 0, cc - 1, x + 1, x + cc); ans += w * get(i, j, k, cc, (int) edges[i][j][k].size() - 1, y + ((int) edges[i][j][k].size() - cc), y + 1); } } } } vector<pair<int,int>> pairs; for (int i = 0; i < cnt; i++) { for (int j = 0; j < cnt; j++) { if (!edges[i][j].empty()) { pairs.emplace_back(i, j); } } } for (int ii = 0; ii < cnt; ii++) { for (int jj = 0; jj < cnt; jj++) { for (int kk = 0; kk < (int) edges[ii][jj].size(); kk++) { for (int tt = 0; tt < (int) edges[ii][jj][kk].size(); tt++) { long long w = edges[ii][jj][kk][tt]; for (int i = 0; i < cnt; i++) { int d1 = dist[ii][i] + tt + 1; int d2 = dist[jj][i] + (int) edges[ii][jj][kk].size() - tt; ans += w * weight[rev_id[i]] * min(d1, d2); } for (auto &p : pairs) { int i = p.first; int j = p.second; for (int k = 0; k < (int) edges[i][j].size(); k++) { if (i == ii && j == jj && k == kk) { int d1 = tt; int d2 = (int) edges[ii][jj][kk].size() - tt + dist[i][j] + 1; if (d1 <= d2) { ans += w * get(i, j, k, 0, tt, tt, 0); } else { int cut = (d1 - d2 + 1) / 2; ans += w * get(i, j, k, 0, cut - 1, d2, d2 + cut - 1); ans += w * get(i, j, k, cut, tt, tt - cut, 0); } int d3 = (int) edges[ii][jj][kk].size() - 1 - tt; int d4 = tt + 1 + dist[i][j] + 1; if (d3 <= d4) { ans += w * get(i, j, k, tt, (int) edges[i][j][k].size() - 1, 0, (int) edges[i][j][k].size() - 1 - tt); } else { int cut = (d3 - d4 + 1) / 2; ans += w * get(i, j, k, (int) edges[i][j][k].size() - cut, (int) edges[i][j][k].size() - 1, d4 + cut - 1, d4); ans += w * get(i, j, k, tt, (int) edges[i][j][k].size() - 1 - cut, 0, (int) edges[i][j][k].size() - 1 - cut - tt); } } else { int d1 = dist[ii][i] + tt + 1; int d2 = dist[jj][i] + (int) edges[ii][jj][kk].size() - tt; int d3 = dist[ii][j] + tt + 1; int d4 = dist[jj][j] + (int) edges[ii][jj][kk].size() - tt; int x = min(d1, d2); int y = min(d3, d4); int cc = (y - x + (int) edges[i][j][k].size() + 1) / 2; cc = min(max(cc, 0), (int) edges[i][j][k].size()); ans += w * get(i, j, k, 0, cc - 1, x + 1, x + cc); ans += w * get(i, j, k, cc, (int) edges[i][j][k].size() - 1, y + ((int) edges[i][j][k].size() - cc), y + 1); } } } } } } } assert(ans % 2 == 0); cout << ans / 2 << '\n'; return 0; } 

Und hier ist der Code, den eines der teilnehmenden Teams als Lösung vorgeschlagen hat:

C ++ - Code

 #include <bits/stdc++.h> #define ll long long #define ld long double using namespace std; int main() { int n,m; cin>>n>>m; int b[n+1][n+1]={}; int c[n+1][n+1]={}; int a1,b1; vector < vector <int> > v(n+1); vector <int> met(n+1); queue <int> q; for(int i=0;i<m;i++){ cin>>a1>>b1; v[a1].push_back(b1); v[b1].push_back(a1); c[a1][b1]=1; c[b1][a1]=1; } long long ans=0; for(int i=1;i<=n;i++){ q.push(i); met.clear(); met.resize(n+1); while(!q.empty()){ int frontt = q.front(); met[frontt]=1; for(int j=0;j<v[frontt].size();j++){ if(!met[v[frontt][j]]){ if(b[i][frontt]+1<b[i][v[frontt][j]] || b[i][v[frontt][j]]==0){ ans-=b[i][v[frontt][j]]; b[i][v[frontt][j]]=b[i][frontt]+1; ans+=b[i][v[frontt][j]]; } q.push(v[frontt][j]); met[v[frontt][j]]=1; } } q.pop(); } } cout<<ans/2; return 0; } 

Die Analyse der Lösung finden Sie im offiziellen Dokument auf unserer Website ( Seite 3 ).

Eine andere Aufgabe ist "Schach":

Elma lernt Schach zu spielen und weiß bereits, dass sich der Turm horizontal oder vertikal bewegt. Elmas Großmutter gab ihr ein 8x8-Schachbrett und bat sie, einen Weg zu finden, um den Turm in n Zügen von Zelle A1 nach H8 zu bewegen. In diesem Fall müssen alle Zellen, auf denen die Abbildung stoppt, unterschiedlich sein. Der Eingang wird mit dem Wert n (2 ≤ n ≤ 63) versorgt. Die Teilnehmer müssen alle Zellen auflisten, auf denen Elma den Turm platziert hat.

Hier ist ein Beispiel für die Lösung dieses Problems, die von den Jurymitgliedern vorgeschlagen wurde:

Java-Code

 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.io.PrintWriter; import java.util.ArrayList; import java.util.StringTokenizer; public class easy_chess_va_wa { BufferedReader br; StringTokenizer st; PrintWriter out; public String nextToken() throws IOException { while (st == null || !st.hasMoreTokens()) { st = new StringTokenizer(br.readLine()); } return st.nextToken(); } public int nextInt() throws IOException { return Integer.parseInt(nextToken()); } public class Cell { int x, y; public Cell(int x, int y) { this.x = x; this.y = y; } public String toString() { return (char) ('a' + x) + "" + (y + 1); } } public void solve() throws IOException { int n = nextInt() + 1; ArrayList<Cell> cells = new ArrayList<>(); int k = Math.min(8 * 8, n + 4); if (k <= 8 * 7) { for (int i = 0; i < 7 && cells.size() < k; i++) { for (int j = 0; j < 8 && cells.size() < k; j++) { cells.add(new Cell(i % 2 == 0 ? j : 7 - j, i)); } } Cell last = cells.get(cells.size() - 1); if (last.x != 7) { cells.add(new Cell(last.x, 7)); } cells.add(new Cell(7, 7)); } else { for (int i = 0; i < 7; i++) { for (int j = 0; j < 8; j++) { cells.add(new Cell(i % 2 == 0 ? j : 7 - j, i)); } } for (int i = 0; i < 8; i++) { for (int j = 0; j < 2; j++) { cells.add(new Cell(i, i % 2 == 0 ? 7 - j : 6 + j)); } } Cell last = cells.get(cells.size() - 1); if (last.y != 7) { cells.add(new Cell(last.x, 7)); } cells.add(new Cell(7, 7)); } while (cells.size() > n) { cells.remove(1); } for (Cell cell : cells) { out.print(cell + " "); } } public void run() { try { br = new BufferedReader(new InputStreamReader(System.in)); out = new PrintWriter(System.out); solve(); out.close(); } catch (IOException e) { e.printStackTrace(); } } public static void main(String[] args) { new easy_chess_va_wa().run(); } } 

Die vollständige Liste der Aufgaben wird auf der offiziellen Website des Wettbewerbs veröffentlicht . Dort finden Sie Antworten mit einer detaillierten Analyse der Lösungen. Der von den Teilnehmern vorgeschlagene Code befindet sich in einem separaten Archiv . Hier finden Sie alle Lösungen und Tests, die für die automatische Überprüfung verwendet wurden.

Während der Olympiade leiteten die Teilnehmer ihre Entscheidungen an einen Testserver weiter, der den Code anhand einer vorbereiteten Testreihe „überprüfte“. Bei erfolgreichem Abschluss aller Tests erhielten die Teilnehmer Punkte. Andernfalls erhielt das Team eine Rückmeldung über den Fehler und konnte Anpassungen am Code vornehmen.

Nach den Regeln der ICPC gewinnt das Team, das die meisten Aufgaben gelöst hat.

Wenn mehrere Teilnehmer die gleiche Anzahl von Punkten erzielt haben, wird ihre Position in der Gesamtwertung durch die Strafzeit bestimmt. Für jedes korrekt gelöste Problem wird eine Strafzeit berechnet, die der Zeit entspricht, die vom Beginn des Wettbewerbs bis zum Bestehen aller Tests durch den Code vergangen ist. Darüber hinaus werden für jeden erfolglosen Versuch, die Aufgabe zu bestehen, 20 Minuten zur Strafe hinzugefügt (nur wenn das Problem am Ende gelöst werden kann). Es wird keine Strafe vergeben, wenn das Team nicht die richtige Lösung für das Problem angeboten hat.


^{icpcnews / Flickr / CC BY / Final ICPC-2017}

Wofür werden die Finalisten antreten?

Wie wir bereits gesagt haben, werden die Halbfinalmeister - fünfzehn Teams - nach Portugal in die Stadt Porto reisen, wo sie um die Weltmeisterschaft und 15.000 Dollar kämpfen werden. Teams, die vom ersten bis zum vierten Platz antreten, werden mit Goldmedaillen ausgezeichnet. Teilnehmer, die vom fünften bis zum achten Platz „fertig“ sind, erhalten Silbermedaillen und vom neunten bis zum zwölften Bronze. Für sie werden auch Geldpreise bereitgestellt.

Das Team der ITMO-Universität wurde sieben Mal (zuletzt - 2017) ICPC-Champion. Dies ist ein Weltrekord, der noch von niemandem geschlagen wurde: Auf dem zweiten Platz in der Anzahl der Meistertitel stehen auch Landsleute, die St. Petersburg State University mit vier Pokalen und die engsten ausländischen Rivalen, American Stanford und Chinese University of Jao Tong - drei Siege. In sieben aufeinanderfolgenden Jahren haben russische Teams das Weltfinale konsequent gewonnen. Hoffen wir, dass die Jungs auf der ICPC 2019 ein anständiges Ergebnis zeigen.

Über das, was wir sonst noch über Habré schreiben:

• ITMO University Digest: Neue Studien und internationale Projekte
• Wie der Low-Level-Programmierkurs an der ITMO University funktioniert