«Программирование в прямом эфире»: как прошел региональный полуфинал ICPC в Университете ИТМО

    В начале декабря полуфинал студенческого чемпионата мира по программированию ICPC. Расскажем, какие «испытания» прошли его участники и кто будет представлять регион Северная Евразия весной, на главном мировом турнире спортивных программистов.


    icpcnews / Flickr / CC BY / Финал ICPC-2017

    Пятнадцать победителей


    Соревнования, в которых участвовало свыше 300 команд, проходили одновременно на четырех площадках: в Санкт-Петербурге, Барнауле, Тбилиси и Алма-Ате. Университет ИТМО принял более ста команд из России и Прибалтики. Участники боролись за кубок этапа Северной Евразии NEERC и право поехать на финал ICPC.

    Что такое ICPC
    Это командные соревнования для студентов вузов и аспирантов первого года обучения. Чемпионат проводится уже более сорока лет. Каждая команда состоит из трех человек и получает один компьютер, у которого нет выхода в интернет. На этой машине они должны совместно решить около дюжины задач. Такой подход позволяет проверить не только знания студентов, но и их навыки командной работы. Победители олимпиады получают денежные призы и приглашения на работу от крупных IT-компаний.

    Абсолютным чемпионом стала команда из МГУ, решив одиннадцать задач. Больше этого сделать не удалось никому. На втором и третьем местах оказались участники из МФТИ. За ходом «баталий» можно было следить в прямом эфире. Запись есть на 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). Участникам нужно вывести список всех клеток, на которые Элма ставила ладью.

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

    Код на 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 ребята покажут достойный результат.

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

    • +18
    • 2,9k
    • 2
    Университет ИТМО
    75,00
    IT's MOre than a University
    Поделиться публикацией

    Комментарии 2

      0
      Кажется, у вас ошибка в правилах начисления штрафов:

      There is no penalty time consumed for a problem that is not solved. There is no penalty time for rejected runs after the first accepted run. There is no penalty time for runs that failed to compile.
        0
        Штрафное время начисляется за каждую правильно решенную задачу и равняется времени, прошедшему с начала соревнования до момента прохождения кодом всех тестов. Более того, за каждую неудачную попытку сдать задачу к штрафу прибавляется 20 минут (только в том случае, если в итоге задачу удается решить). Штраф не начисляется, если команда так и не предложила правильное решение задачи.

        Никаких противоречий, просто не сказано ничего про compilation error и про неудачные отправки для уже сданной успешно задачи (для правил это важно, а для статьи — лишние подробности).

      Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

      Самое читаемое