“实时编程”：ITMO大学的ICPC地区半决赛如何进行

12月初，ICPC学生编程世界冠军赛半决赛。 我们将告诉您参加者在春季举行的世界主要体育比赛中参加了哪些“试验”，以及谁将代表北欧亚地区。


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

十五名获奖者

共有300支队伍参加的比赛同时在四个地点举行：圣彼得堡，巴尔瑙尔，第比利斯和阿拉木图。 ITMO大学已收到来自俄罗斯和波罗的海国家的一百多个团队。 参加者为NEERC北部欧亚大陆杯和参加ICPC决赛的权利而战。


莫斯科国立大学的团队解决了11个问题， 成为绝对冠军。 没有人设法做到这一点。 第二和第三名是MIPT的参与者。 可以实时观看“战斗”的进展。 ICPC YouTube频道上有一条记录：


在ICPC-2019决赛中总共选出了15个团队（完整列表可以在此处找到），其中包括来自ITMO大学的团队。 3月下旬，他们将前往波尔图（葡萄牙）争取世界冠军头衔。

半决赛如何进行？

学生使用Java，C ++，Python或Kotlin编程语言。 所有任务都需要专心，专注和掌握各种算法。

例如，作为ITMO大学团队Gennady Korotkevich的一部分，ICPC的双赢者提出了以下任务：

有一个无向的无权图。 两个顶点u和v之间的距离由最短路径中的边数确定。 求出所有无序顶点对的和d（u，v） 。

首先，将两个数字n和m （2≤n≤10 ⁵ ； n-1≤m≤n + 42）-顶点和边的数量分别馈入程序输入。 顶点从1到n编号。 接下来，输入具有两个整数值的m行： x _i和y _i （1≤x _i ，y i≤n； x _i ≠y _i ）-这些是第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页 ）。

另一个任务是“棋”：

埃尔玛（Elma）学习下棋，并且已经知道车子可以水平或垂直移动。 Elma的祖母给了她一个8x8的棋盘，并要求她找到一种方法，可以将n-n车从A1单元移动到H8。 在这种情况下，该图停止的所有单元格都必须不同。 为输入提供值n （2≤n≤63）。 参与者需要列出Elma放置新手的所有单元。

以下是陪审团成员提出的解决此问题的示例：

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

完整的任务清单已发布在比赛的官方网站上 。 您可以在其中找到解决方案的详细分析答案 。 参与者建议的代码位于单独的存档中 ，您可以在此处找到用于自动验证的所有解决方案和测试。

奥运会期间，参与者将他们的决定转发给测试服务器，测试服务器在预先准备的一组测试中“检查”代码。 在成功完成所有测试的情况下，给参与者打分。 否则，团队将收到有关错误的反馈，并可以对代码进行调整。

根据ICPC的规则，完成大部分任务的团队将获胜。

如果几个参与者同时得分相同的分数，则他们在积分榜上的位置取决于罚球时间。 每个正确解决的问题的惩罚时间都应累积，等于从比赛开始到代码通过所有测试所经过的时间。 此外，对于每次未成功通过任务的尝试，将增加20分钟的处罚（仅在最后可以解决问题的情况下）。 如果团队没有提供正确的解决方案，则不会判罚。


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

决赛入围者将争夺什么？

正如我们已经说过的那样，半决赛冠军-15支队伍-将前往葡萄牙，前往波尔图市，在那里他们将为世界杯和15,000美元的比赛而战。 从第一名到第四名的团队将获得金牌。 从第五名到第八名“完成”的参与者将获得银牌，从第九名到第十二名将获得铜牌。 还为他们提供现金奖励。

ITMO大学团队已七次蝉联ICPC冠军（最近一次-2017年）。 这是一个尚未被任何人击败的世界纪录：在冠军头衔中排名第二的是同胞圣彼得堡国立大学，获得四次杯赛；以及最接近的外国竞争对手美国斯坦福大学和中国交通大学-三场胜利。 连续七年，世界总决赛一直由俄罗斯队赢得。 希望我们能在ICPC 2019上取得不错的成绩。

关于我们在Habré上写的其他内容：

• ITMO大学文摘：新研究和国际项目
• ITMO大学的低级编程课程如何工作