«Programmation en direct»: comment s'est déroulée la demi-finale régionale du CIPC à l'Université ITMO

Début décembre, la demi-finale du championnat du monde de programmation étudiante ICPC. Nous allons vous dire quels «essais» les participants ont pris et qui représentera la région Nord Eurasie au printemps, lors du principal tournoi mondial de programmateurs sportifs.


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

Quinze gagnants

Des compétitions, auxquelles ont participé plus de 300 équipes, se sont déroulées simultanément sur quatre sites: à Saint-Pétersbourg, Barnaul, Tbilissi et Alma-Ata. L'ITMO University a reçu plus d'une centaine d'équipes de Russie et des États baltes. Les participants se sont battus pour la NEERC Northern Eurasia Cup et le droit d'aller à la finale du CIPC.


L'équipe de l'Université d'État de Moscou est devenue la championne absolue, après avoir résolu onze problèmes. Personne n'a plus réussi à faire ça. Les deuxième et troisième places étaient des participants du MIPT. La progression des "batailles" pouvait être regardée en direct. Il existe un enregistrement sur la chaîne YouTube de l'ICPC:


Au total, quinze équipes ont été sélectionnées lors de la finale de l'ICPC-2019 (la liste complète peut être consultée ici ), y compris des gars de l'Université ITMO. Fin mars, ils se rendront à Porto (Portugal) pour se battre pour le titre de champion du monde.

Comment se sont passées les demi-finales?

Les étudiants ont utilisé les langages de programmation Java, C ++, Python ou Kotlin. Toutes les tâches exigeaient de l'attention, de la concentration et de la connaissance de divers algorithmes.

Par exemple, la tâche suivante a été proposée par le double vainqueur de l'ICPC au sein de l'équipe de l'Université ITMO Gennady Korotkevich :

Il existe un graphique non pondéré non orienté. La distance entre deux sommets u et v est déterminée par le nombre d'arêtes dans le chemin le plus court. Trouvez la somme d (u, v) de toutes les paires de sommets désordonnées.

Tout d'abord, deux nombres n et m (2 ≤ n ≤ 10 ⁵ ; n-1 ≤ m ≤ n + 42) - le nombre de sommets et d'arêtes, respectivement, est appliqué à l'entrée du programme. Les sommets sont numérotés de 1 à n . Ensuite, m lignes sont entrées avec deux valeurs entières: x _i et y _i (1 ≤ x _i , y _i ≤ n; x _i ≠ y _i ) - ce sont les points d'extrémité du ième bord. Il existe au moins une arête entre n'importe quelle paire de sommets.

Exemple de programme avec une solution (proposé par un membre du jury):

Code C ++

#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; } 

Et voici le code que l'une des équipes participantes a proposé comme solution:

Code C ++

 #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; } 

L'analyse de la solution se trouve dans le document officiel sur notre site Internet ( page 3 ).

Une autre tâche est les «échecs»:

Elma apprend à jouer aux échecs et sait déjà que la tour se déplace horizontalement ou verticalement. La grand-mère d'Elma lui a donné un échiquier 8x8 et lui a demandé de trouver un moyen de déplacer la tour de la cellule A1 à H8 en n mouvements. Dans ce cas, toutes les cellules sur lesquelles la figure s'arrête doivent être différentes. L'entrée est fournie avec la valeur n (2 ≤ n ≤ 63). Les participants doivent lister toutes les cellules sur lesquelles Elma a placé la tour.

Voici un exemple de la solution à ce problème qui a été proposée par les membres du jury:

Code Java

 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(); } } 

La liste complète des tâches est publiée sur le site officiel du concours . Vous y trouverez des réponses avec une analyse détaillée des solutions. Le code que les participants ont suggéré se trouve dans une archive distincte , et ici vous pouvez trouver toutes les solutions et tests qui ont été utilisés pour la vérification automatique.

Pendant l'Olympiade, les participants ont transmis leurs décisions à un serveur de test, qui a «vérifié» le code sur un ensemble de tests pré-préparé. En cas de réussite de tous les tests, les participants ont obtenu des points. Sinon, l'équipe a reçu des commentaires sur l'erreur et pourrait apporter des modifications au code.

Selon les règles de l'ICPC, l'équipe qui a résolu la plupart des tâches gagne.

Si plusieurs participants ont marqué le même nombre de points à la fois, leur position au classement est déterminée par le temps de pénalité. Le temps de pénalité est cumulé pour chaque problème correctement résolu et est égal au temps écoulé depuis le début de la compétition jusqu'à ce que le code réussisse tous les tests. De plus, pour chaque tentative infructueuse de réussir la tâche, 20 minutes s'ajoutent à la pénalité (seulement si à la fin le problème peut être résolu). Aucune pénalité n'est accordée si l'équipe n'a pas proposé la bonne solution au problème.


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

Pourquoi les finalistes concourront-ils?

Comme nous l'avons déjà dit, les champions de demi-finale - quinze équipes - iront au Portugal, dans la ville de Porto, où ils se battront pour la Coupe du monde et 15 000 $. Les équipes qui se classeront du premier au quatrième seront récompensées par des médailles d'or. Les participants qui «ont terminé» aux places du cinquième au huitième recevront des médailles d'argent, et du neuvième au douzième - le bronze. Des prix en espèces leur sont également fournis.

L'équipe de l'Université ITMO est devenue championne de l'ICPC à sept reprises (la dernière - en 2017). C'est un record du monde qui n'a encore été battu par personne: en deuxième position du nombre de titres de champion se trouvent également des compatriotes, l'Université d'État de Saint-Pétersbourg, avec quatre coupes, et les rivaux étrangers les plus proches, l'American Stanford et l'Université chinoise de Jao Tong - trois victoires. Pendant sept années consécutives, l'équipe russe a remporté la finale mondiale. Espérons qu'à ICPC 2019 les gars montreront un résultat décent.

À propos de ce que nous écrivons d'autre sur Habré:

• ITMO University Digest: Nouvelles études et projets internationaux
• Comment fonctionne le cours de programmation de bas niveau à l'Université ITMO