В начале декабря полуфинал студенческого чемпионата мира по программированию ICPC. Расскажем, какие «испытания» прошли его участники и кто будет представлять регион Северная Евразия весной, на главном мировом турнире спортивных программистов.
icpcnews / Flickr / CC BY / Финал ICPC-2017
Пятнадцать победителей
Соревнования, в которых участвовало свыше 300 команд, проходили одновременно на четырех площадках: в Санкт-Петербурге, Барнауле, Тбилиси и Алма-Ате. Университет ИТМО принял более ста команд из России и Прибалтики. Участники боролись за кубок этапа Северной Евразии NEERC и право поехать на финал ICPC.
Абсолютным чемпионом стала команда из МГУ, решив одиннадцать задач. Больше этого сделать не удалось никому. На втором и третьем местах оказались участники из МФТИ. За ходом «баталий» можно было следить в прямом эфире. Запись есть на YouTube-канале ICPC:
Всего в финал ICPC-2019 отобрались пятнадцать команд (весь список можно найти здесь) — в их числе ребята из Университета ИТМО. В конце марта они отправятся в город Порту (Португалия) бороться за звание чемпионов мира.
Как проходил полуфинал
Студенты использовали языки программирования Java, C++, Python или Kotlin. Все задания требовали внимательности, концентрации и знания различных алгоритмов.
Например, следующую задачу предложил двукратный победитель ICPC в составе команды Университета ИТМО Геннадий Короткевич:
Имеется ненаправленный невзвешенный граф. Расстояние между двумя вершинами u и v определяется числом рёбер в кратчайшем пути. Найдите сумму d(u,v) всех неупорядоченных пар вершин.
Сперва на вход программы подаются два числа n и m (2 ≤ n ≤ 105; n-1 ≤ m ≤ n+42) — число вершин и ребер соответственно. Вершины пронумерованы от 1 до n. Далее, вводятся m строк с двумя целыми значениями: xi и yi (1 ≤ xi, yi ≤ n; xi ≠ yi)— это конечные точки i-того ребра. Между любой парой вершин есть хотя бы одно ребро.
Пример программы с решением (предложен членом жюри):
Код на 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; }
А вот код, который предложила в качестве решения одна из команд-участниц:
Код на 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; }
Разбор решения можно найти в официальном документе на нашем сайте (стр. 3).
Другая задача — «шахматная»:
Элма учится играть в шахматы и уже знает, что ладья ходит по горизонтали или вертикали. Бабушка Элмы дала ей шахматную доску 8х8 и попросила найти способ передвинуть ладью с клетки A1 на H8 за n ходов. При этом все клетки, на которых останавливается фигура, должны быть разными. На вход программе подается значение n (2 ≤ n ≤ 63). Участникам нужно вывести список всех клеток, на которые Элма ставила ладью.
Вот пример решения этой задачи, которое было предложено членами жюри:
Код на Javaimport 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(); } }
Полный список заданий опубликован на официальном сайте соревнования. Там же можно найти ответы с подробным разбором решений. Код, который предлагали участники лежит в отдельном архиве, а здесь вы можете найти все решения и тесты, которые использовались для автоматической проверки.
Во время олимпиады участники пересылали свои решения тестирующему серверу, который «проверял» код на заранее подготовленном наборе тестов. В случае успешного прохождения всех тестов, участникам засчитывались баллы. Иначе — команда получала обратную связь об ошибке и могла внести корректировки в код.
Количество попыток на отправку кода не ограничено, но за каждый «провал» начислялись двадцать штрафных минут. Однако штраф не засчитывался, если задача в итоге оказывалась решена. Победителем считалась та команда, которая заработала максимум баллов и меньше всех штрафов.
icpcnews / Flickr / CC BY / Финал ICPC-2017
За что поборются финалисты
Как мы уже говорили, чемпионы полуфинала — пятнадцать команд — поедут в Португалию, в город Порту, где будут бороться за кубок Чемпионата мира и 15 тыс. долларов. Команды, которые займут места с первого по четвертое, наградят золотыми медалями. Участники, «финишировавшие» на местах с пятого по восьмое, получат серебряные медали, а с девятого по двенадцатое — бронзовые. Денежные призы для них также предусмотрены.
Команда Университета ИТМО становилась чемпионом ICPC уже семь раз (последний — в 2017 году). Это мировой рекорд, который пока никем не побит: на втором месте по количеству чемпионских титулов — также соотечественники, СПбГУ, с четырьмя кубками, а у ближайших зарубежных соперников, американского Стэнфорда и китайского Университета Джао Тонг — по три победы. Семь лет подряд мировой финал неизменно выигрывают российские команды. Будем надеяться, что и на ICPC 2019 ребята покажут достойный результат.
О чем еще мы пишем на Хабре:
- Дайджест Университета ИТМО: новые исследования и международные проекты
- Как устроен курс «Низкоуровневое программирование» в Университете ИТМО
Автор: itmo
