"Programación en vivo": ¿Cómo funcionó la Semifinal Regional de ICPC en la Universidad ITMO?

A principios de diciembre, la semifinal del campeonato mundial de programación estudiantil ICPC. Le diremos qué "pruebas" tomaron los participantes y quién representará a la región de Eurasia del Norte en la primavera, en el principal torneo mundial de programadores deportivos.


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

Quince ganadores

Las competiciones, en las que participaron más de 300 equipos, tuvieron lugar simultáneamente en cuatro sedes: en San Petersburgo, Barnaul, Tbilisi y Alma-Ata. La Universidad ITMO ha recibido más de cien equipos de Rusia y los estados bálticos. Los participantes lucharon por la Copa NEERC del Norte de Eurasia y el derecho a ir a las finales de la ICPC.


El equipo de la Universidad Estatal de Moscú se convirtió en el campeón absoluto, resolviendo once problemas. Nadie logró hacer esto más. El segundo y tercer lugar fueron participantes del MIPT. El progreso de las "batallas" se podía ver en vivo. Hay un registro en el canal de YouTube ICPC:


En total, se seleccionaron quince equipos en la final de la ICPC-2019 (la lista completa se puede encontrar aquí ), incluidos los muchachos de la Universidad ITMO. A finales de marzo, irán a la ciudad de Oporto (Portugal) para luchar por el título de campeones del mundo.

¿Cómo fueron las semifinales?

Los estudiantes usaron los lenguajes de programación Java, C ++, Python o Kotlin. Todas las tareas requieren atención, concentración y conocimiento de varios algoritmos.

Por ejemplo, el dos veces ganador del ICPC propuso la siguiente tarea como parte del equipo de la Universidad ITMO Gennady Korotkevich :

Hay un gráfico no ponderado no dirigido. La distancia entre dos vértices u y v está determinada por el número de aristas en el camino más corto. Encuentre la suma d (u, v) de todos los pares de vértices desordenados.

Primero, dos números n y m (2 ≤ n ≤ 10 ⁵ ; n-1 ≤ m ≤ n + 42): el número de vértices y aristas, respectivamente, se alimenta a la entrada del programa. Los vértices están numerados del 1 al n . Luego, las líneas m se ingresan con dos valores enteros: x _i e y _i (1 ≤ x _i , y _i ≤ n; x _i ≠ y _i ): estos son los puntos finales del i-ésimo borde. Hay al menos un borde entre cualquier par de vértices.

Programa de ejemplo con una solución (propuesta por un miembro del jurado):

Código 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; } 

Y aquí está el código que uno de los equipos participantes propuso como solución:

Código 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; } 

El análisis de la solución se puede encontrar en el documento oficial de nuestro sitio web ( página 3 ).

Otra tarea es el "ajedrez":

Elma aprende a jugar al ajedrez y ya sabe que la torre se mueve horizontal o verticalmente. La abuela de Elma le dio un tablero de ajedrez de 8x8 y le pidió que encontrara una manera de mover la torre de la celda A1 a H8 en n movimientos. En este caso, todas las celdas en las que se detiene la figura deben ser diferentes. La entrada se suministra con el valor n (2 ≤ n ≤ 63). Los participantes deben enumerar todas las celdas en las que Elma colocó la torre.

Aquí hay un ejemplo de la solución a este problema que fue propuesto por los miembros del jurado:

Código 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 lista completa de tareas se publica en el sitio web oficial de la competencia . Allí puede encontrar respuestas con un análisis detallado de soluciones. El código que sugirieron los participantes se encuentra en un archivo separado , y aquí puede encontrar todas las soluciones y pruebas que se utilizaron para la verificación automática.

Durante la Olimpiada, los participantes remitieron sus decisiones a un servidor de prueba, que "verificó" el código en un conjunto de pruebas previamente preparado. En caso de completar con éxito todas las pruebas, los participantes obtuvieron puntos. De lo contrario, el equipo recibió comentarios sobre el error y podría hacer ajustes al código.

De acuerdo con las reglas de ICPC, el equipo que ha resuelto la mayoría de las tareas gana.

Si varios participantes obtuvieron el mismo número de puntos a la vez, su posición en la clasificación está determinada por el tiempo de penalización. El tiempo de penalización se acumula para cada problema resuelto correctamente y es igual al tiempo transcurrido desde el comienzo de la competencia hasta que el código pasó todas las pruebas. Además, por cada intento fallido de pasar la tarea, se agregan 20 minutos a la penalización (solo si al final se puede resolver el problema). No se otorga ninguna penalización si el equipo no ha ofrecido la solución correcta al problema.


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

¿Por qué competirán los finalistas?

Como ya dijimos, los campeones de semifinales, quince equipos, irán a Portugal, a la ciudad de Oporto, donde lucharán por la Copa del Mundo y $ 15,000. Los equipos que tomarán lugar del primero al cuarto recibirán medallas de oro. Los participantes que "terminaron" en los lugares quinto a octavo recibirán medallas de plata, y del noveno al duodécimo - bronce. También se les otorgan premios en efectivo.

El equipo de la Universidad ITMO se ha convertido en el campeón de ICPC siete veces (la última, en 2017). Este es un récord mundial que aún no ha sido superado por nadie: en segundo lugar en el número de títulos de campeones también están los compatriotas, la Universidad Estatal de San Petersburgo, con cuatro copas, y los rivales extranjeros más cercanos, el estadounidense Stanford y la Universidad China de Jao Tong: tres victorias. Durante siete años seguidos, las finales mundiales han sido invariablemente ganadas por los equipos rusos. Esperemos que en ICPC 2019 los chicos muestren un resultado decente.

Sobre qué más escribimos en Habré:

• ITMO University Digest: nuevos estudios y proyectos internacionales
• Cómo funciona el curso de programación de bajo nivel en la Universidad ITMO