“Live Programming”: how did the ICPC regional semifinal go at ITMO University

In early December, the semi-final of the ICPC Student World Programming Championship. Let us tell you what "tests" passed its participants and who will represent the North Eurasia region in the spring, at the main world tournament of sports programmers.


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

Fifteen winners

Competitions, in which more than 300 teams participated, were held simultaneously at four venues: in St. Petersburg, Barnaul, Tbilisi and Almaty. ITMO University received more than a hundred teams from Russia and the Baltic States. Participants fought for the NEERC Cup of the North Eurasia stage and the right to go to the ICPC final.


The team from Moscow State University became the absolute champion , having solved eleven problems. No one else was able to do this. The second and third places were participants from MFTI. The course of the “battles” could be watched live. Record is on the ICPC YouTube channel:


In total, fifteen teams were selected for the ICPC-2019 final (the entire list can be found here ) - among them are the guys from ITMO University. At the end of March they will go to the city of Porto (Portugal) to fight for the title of world champions.

How was the semi-final

Students used the programming languages ​​Java, C ++, Python, or Kotlin. All tasks required attentiveness, concentration and knowledge of various algorithms.

For example, the following task was proposed by the two-time ICPC winner in the team of the ITMO University Gennady Korotkevich :

There is an undirected unweighted graph. The distance between two vertices u and v is determined by the number of edges in the shortest path. Find the sum d (u, v) of all unordered pairs of vertices.

First, the input of the program is given two numbers n and m (2 ≤ n ≤ 10 ⁵ ; n-1 ≤ m ≤ n + 42) - the number of vertices and edges, respectively. Vertices are numbered from 1 to n . Next, m lines are entered with two integer values: x _i and y _i (1 ≤ x _i , y _i ≤ n; x _i y _i) Are the end points of the i-th edge. There is at least one edge between any pair of vertices.

An example of a program with a decision (proposed by a jury member):

C ++ Code

#undef _GLIBCXX_DEBUG#include<bits/stdc++.h>usingnamespacestd;
intmain(){
  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);
  }
  longlong 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 += (longlong) 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';
    return0;
  }
  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<longlong>>>> edge_pref_sum(cnt, vector<vector<vector<longlong>>>(cnt));
  vector<vector<vector<vector<longlong>>>> edge_pref_sum_by_pos(cnt, vector<vector<vector<longlong>>>(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] + (longlong) edges[i][j][k][t] * t;
        }
      }
    }
  }
  auto get = [&](int i, int j, int k, int from, int to, int coeff_from, int coeff_to) -> longlong {
    if (from > to) {
      return0;
    }
    assert(0 <= from && to <= (int) edges[i][j][k].size() - 1);
    longlong 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);
      longlong 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++) {
    longlong 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++) {
          longlong 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';
  return0;
}

But the code that was proposed as a solution by one of the participating teams:

C ++ Code

#include<bits/stdc++.h>#define ll long long#define ld long doubleusingnamespacestd;
intmain(){
    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;
    }
    longlong 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;
    return0;
}

Analysis of the solution can be found in the official document on our website ( p. 3 ).

Another task is "chess":

Elma is learning to play chess and already knows that the rook is moving horizontally or vertically. Elma's grandmother gave her an 8x8 chessboard and asked her to find a way to move the rook from cell A1 to H8 in n moves. Moreover, all the cells on which the figure stops must be different. The input to the program is the value n (2 ≤ n ≤ 63). Participants need to list all the cells on which Elma put the rook.

Here is an example of solving this problem, which was proposed by the jury members:

Java code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.StringTokenizer;
publicclasseasy_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();
    }
    publicintnextInt()throws IOException {
        return Integer.parseInt(nextToken());
    }
    publicclassCell{
        int x, y;
        publicCell(int x, int y){
            this.x = x;
            this.y = y;
        }
        public String toString(){
            return (char) ('a' + x) + "" + (y + 1);
        }
    }
    publicvoidsolve()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 + " ");
        }
    }
    publicvoidrun(){
        try {
            br = new BufferedReader(new InputStreamReader(System.in));
            out = new PrintWriter(System.out);
            solve();
            out.close();
        } catch (IOException e) {
            e.printStackTrace();
        }
    }
    publicstaticvoidmain(String[] args){
        new easy_chess_va_wa().run();
    }
}

Full list of tasks published on the official website of the competition . You can also find answers with a detailed analysis of solutions. The code offered by the participants lies in a separate archive , and here you can find all the solutions and tests that were used for automatic verification.

During the competition, participants forwarded their solutions to the testing server, which “tested” the code on a previously prepared set of tests. In case of successful completion of all tests, participants were awarded points. Otherwise, the team received feedback about the error and could make corrections to the code.

According to the ICPC rules, the team that wins the most tasks wins.

If several participants score the same number of points at once, their position in the standings is determined by the penalty time. Penalty time is charged for each correctly solved problem and equals the time elapsed from the beginning of the competition to the time the code passes all the tests. Moreover, for each unsuccessful attempt to pass the task to the penalty, 20 minutes is added (only if, as a result, the task can be solved). The penalty is not charged if the team has not offered the correct solution to the problem. ^{icpcnews / Flickr / CC BY / Final ICPC-2017}

What the finalists will fight for

As we have said, the champions of the semi-finals - fifteen teams - will go to Portugal, to the city of Porto, where they will fight for the World Cup and 15 thousand dollars. Teams that will take places from the first to the fourth, will be awarded gold medals. Participants who “finished” on the ground from the fifth to the eighth, will receive silver medals, and from the ninth to the twelfth - bronze. Cash prizes are also provided for them.

The ITMO University team has already become the ICPC champion seven times (the last in 2017). This is a world record, which has not been broken by anyone yet: second place in the number of champion titles are also compatriots, St. Petersburg State University, with four cups, and the closest foreign rivals, American Stanford and Chinese University Jao Tong have three wins each. For seven years in a row, the world finals have consistently been won by Russian teams. Hopefully, the guys at ICPC 2019 will show a decent result.

What else do we write on Habré:

• ITMO University Digest: New Research and International Projects
• How the course “Low Level Programming” is organized at ITMO University