“Programação ao vivo”: como foi a Semifinal Regional do ICPC na Universidade ITMO

No início de dezembro, a meia-final do campeonato mundial de programação de estudantes do ICPC. Contaremos quais testes os participantes fizeram e quem representará a região da Eurásia do Norte na primavera, no principal torneio mundial de programadores esportivos.


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

Quinze vencedores

As competições, nas quais mais de 300 equipes participaram, ocorreram simultaneamente em quatro locais: em São Petersburgo, Barnaul, Tbilisi e Alma-Ata. A Universidade ITMO recebeu mais de cem equipes da Rússia e dos estados bálticos. Os participantes lutaram pela Copa NEERC da Eurásia do Norte e pelo direito de ir às finais do ICPC.


A equipe da Universidade Estatal de Moscou se tornou a campeã absoluta, tendo resolvido onze problemas. Ninguém conseguiu mais fazer isso. O segundo e terceiro lugares foram participantes do MIPT. O progresso das "batalhas" poderia ser visto ao vivo. Há um registro no canal do ICPC no YouTube:


No total, quinze equipes foram selecionadas na final do ICPC-2019 (a lista completa pode ser encontrada aqui ), incluindo funcionários da ITMO University. No final de março, eles irão para a cidade do Porto (Portugal) para lutar pelo título de campeões mundiais.

Como foram as meias-finais?

Os alunos usaram as linguagens de programação Java, C ++, Python ou Kotlin. Todas as tarefas exigiam atenção, concentração e conhecimento de vários algoritmos.

Por exemplo, a duas vezes ganhadora do ICPC propôs a seguinte tarefa como parte da equipe da ITMO University, Gennady Korotkevich :

Há um gráfico não ponderado não direcionado. A distância entre os dois vértices u e v é determinada pelo número de arestas no caminho mais curto. Encontre a soma d (u, v) de todos os pares de vértices desordenados.

Primeiro, dois números n e m (2 ≤ n ≤ 10 ⁵ ; n-1 ≤ m ≤ n + 42) - o número de vértices e arestas, respectivamente, são alimentados na entrada do programa. Os vértices são numerados de 1 a n . Em seguida, m linhas são inseridas com dois valores inteiros: x _i e y _i (1 ≤ x _i , y _i ≤ n; x _i ≠ y _i ) - esses são os pontos finais da i-ésima aresta. Há pelo menos uma aresta entre qualquer par de vértices.

Exemplo de programa com uma solução (proposta por um membro do júri):

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

E aqui está o código que uma das equipes participantes propôs como solução:

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

A análise da solução pode ser encontrada no documento oficial em nosso site ( página 3 ).

Outra tarefa é o "xadrez":

Elma aprende a jogar xadrez e já sabe que a torre se move horizontal ou verticalmente. A avó de Elma deu a ela um tabuleiro de xadrez 8x8 e pediu que ela encontrasse uma maneira de mover a torre da célula A1 para H8 em n movimentos. Nesse caso, todas as células nas quais a figura pára devem ser diferentes. A entrada é fornecida com o valor n (2 ≤ n ≤ 63). Os participantes precisam listar todas as células em que Elma colocou a torre.

Aqui está um exemplo da solução para este problema que foi proposta pelos membros do júri:

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

A lista completa de tarefas é publicada no site oficial da competição . Lá você pode encontrar respostas com uma análise detalhada das soluções. O código sugerido pelos participantes está em um arquivo separado e aqui você encontra todas as soluções e testes que foram usados ​​para verificação automática.

Durante a Olimpíada, os participantes encaminharam suas decisões para um servidor de teste, que "verificou" o código em um conjunto de testes pré-preparado. Em caso de conclusão bem-sucedida de todos os testes, os participantes obtinham pontos. Caso contrário, a equipe recebeu feedback sobre o erro e poderia fazer ajustes no código.

De acordo com as regras do ICPC, a equipe que resolveu a maioria das tarefas vence.

Se vários participantes marcarem o mesmo número de pontos ao mesmo tempo, sua posição na classificação é determinada pelo tempo da penalidade. O tempo de penalidade é acumulado para cada problema resolvido corretamente e é igual ao tempo decorrido desde o início da competição até o código ser aprovado em todos os testes. Além disso, para cada tentativa malsucedida de passar a tarefa, 20 minutos são adicionados à penalidade (somente se no final o problema puder ser resolvido). Nenhuma penalidade será concedida se a equipe não oferecer a solução correta para o problema.


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

Pelo que os finalistas competirão?

Como já dissemos, os campeões das meias-finais - quinze equipes - irão para Portugal, para a cidade do Porto, onde lutarão pela Copa do Mundo e US $ 15.000. As equipes que ocorrerão do primeiro ao quarto serão premiados com medalhas de ouro. Os participantes que “terminaram” nos lugares do quinto ao oitavo receberão medalhas de prata e do nono ao décimo segundo - bronze. Também são fornecidos prêmios em dinheiro.

A equipe da ITMO University se tornou campeã do ICPC por sete vezes (a última - em 2017). Este é um recorde mundial que ainda não foi batido por ninguém: em segundo lugar, o número de títulos de campeões também são compatriotas, a Universidade Estadual de São Petersburgo, com quatro xícaras, e os rivais estrangeiros mais próximos, American Stanford e Universidade Chinesa de Jao Tong - três vitórias. Por sete anos consecutivos, a equipe russa venceu as finais mundiais. Vamos torcer para que no ICPC 2019 os caras mostrem um resultado decente.

Sobre o que mais escrevemos sobre Habré:

• ITMO University Digest: Novos Estudos e Projetos Internacionais
• Como funciona o curso de programação de baixo nível da ITMO University