В начале декабря полуфинал студенческого чемпионата мира по программированию 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 ? 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).

Другая задача — «шахматная»:

Элма учится играть в шахматы и уже знает, что ладья ходит по горизонтали или вертикали. Бабушка Элмы дала ей шахматную доску 8х8 и попросила найти способ передвинуть ладью с клетки A1 на H8 за n ходов. При этом все клетки, на которых останавливается фигура, должны быть разными. На вход программе подается значение n (2 ? n ? 63). Участникам нужно вывести список всех клеток, на которые Элма ставила ладью.

Вот пример решения этой задачи, которое было предложено членами жюри:

Код на 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 / Финал ICPC-2017}

За что поборются финалисты

Как мы уже говорили, чемпионы полуфинала — пятнадцать команд — поедут в Португалию, в город Порту, где будут бороться за кубок Чемпионата мира и 15 тыс. долларов. Команды, которые займут места с первого по четвертое, наградят золотыми медалями. Участники, «финишировавшие» на местах с пятого по восьмое, получат серебряные медали, а с девятого по двенадцатое — бронзовые. Денежные призы для них также предусмотрены.

Команда Университета ИТМО становилась чемпионом ICPC уже семь раз (последний — в 2017 году). Это мировой рекорд, который пока никем не побит: на втором месте по количеству чемпионских титулов — также соотечественники, СПбГУ, с четырьмя кубками, а у ближайших зарубежных соперников, американского Стэнфорда и китайского Университета Джао Тонг — по три победы. Семь лет подряд мировой финал неизменно выигрывают российские команды. Будем надеяться, что и на ICPC 2019 ребята покажут достойный результат.

О чем еще мы пишем на Хабре:

• Дайджест Университета ИТМО: новые исследования и международные проекты
• Как устроен курс «Низкоуровневое программирование» в Университете ИТМО?