“Pemrograman Langsung”: Bagaimana semifinal Regional ICPC di Universitas ITMO

Pada awal Desember, semifinal kejuaraan dunia pemrograman mahasiswa ICPC. Kami akan memberi tahu Anda apa "uji coba" yang dilakukan para peserta dan siapa yang akan mewakili wilayah Eurasia Utara pada musim semi, di turnamen dunia utama para pemrogram olahraga.


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

Lima belas pemenang

Kompetisi, di mana lebih dari 300 tim berpartisipasi, berlangsung secara bersamaan di empat tempat: di St. Petersburg, Barnaul, Tbilisi dan Alma-Ata. Universitas ITMO telah menerima lebih dari seratus tim dari Rusia dan negara-negara Baltik. Peserta berjuang untuk NEERC Northern Eurasia Cup dan hak untuk pergi ke final ICPC.


Tim dari Universitas Negeri Moskow menjadi juara mutlak, setelah memecahkan sebelas masalah. Tidak ada orang lain yang bisa melakukan ini. Tempat kedua dan ketiga adalah peserta dari MIPT. Kemajuan "pertempuran" bisa disaksikan langsung. Ada catatan di saluran YouTube ICPC:


Secara total, lima belas tim terpilih di final ICPC-2019 (seluruh daftar dapat ditemukan di sini ), termasuk orang-orang dari Universitas ITMO. Pada akhir Maret, mereka akan pergi ke kota Porto (Portugal) untuk memperjuangkan gelar juara dunia.

Bagaimana semifinal berjalan?

Siswa menggunakan bahasa pemrograman Java, C ++, Python, atau Kotlin. Semua tugas membutuhkan perhatian, konsentrasi, dan pengetahuan dari berbagai algoritma.

Sebagai contoh, tugas berikut diusulkan oleh pemenang ganda ICPC sebagai bagian dari tim Universitas ITMO Gennady Korotkevich :

Ada grafik tidak tertimbang yang tidak diarahkan. Jarak antara dua simpul u dan v ditentukan oleh jumlah tepi di jalur terpendek. Temukan jumlah d (u, v) dari semua pasangan simpul yang tidak teratur.

Pertama, dua angka n dan m (2 ≤ n ≤ 10 ⁵ ; n-1 ≤ m ≤ n + 42) - jumlah simpul dan tepi, masing-masing, diumpankan ke input program. Verteks diberi nomor dari 1 hingga n . Selanjutnya, garis m dimasukkan dengan dua nilai integer: x _i dan y _i (1 ≤ x _i , y _i ≤ n; x _i ≠ y _i ) - ini adalah titik akhir dari tepi engan. Setidaknya ada satu sisi di antara setiap pasangan simpul.

Contoh program dengan solusi (diusulkan oleh anggota juri):

Kode 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; } 

Dan inilah kode yang diusulkan salah satu tim yang berpartisipasi sebagai solusi:

Kode 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; } 

Analisis solusinya dapat ditemukan di dokumen resmi di situs web kami ( halaman 3 ).

Tugas lain adalah "catur":

Elma belajar bermain catur dan sudah tahu bahwa benteng bergerak secara horizontal atau vertikal. Nenek Elma memberinya papan catur 8x8 dan memintanya untuk menemukan cara untuk memindahkan benteng dari sel A1 ke H8 dalam gerakan. Dalam hal ini, semua sel tempat gambar berhenti harus berbeda. Input diberikan dengan nilai n (2 ≤ n ≤ 63). Peserta harus membuat daftar semua sel tempat Elma menempatkan benteng.

Berikut adalah contoh solusi untuk masalah ini yang diusulkan oleh anggota juri:

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

Daftar lengkap tugas dipublikasikan di situs resmi kompetisi . Di sana Anda dapat menemukan jawaban dengan analisis terperinci solusi. Kode yang disarankan peserta terletak di arsip terpisah , dan di sini Anda dapat menemukan semua solusi dan tes yang digunakan untuk verifikasi otomatis.

Selama Olimpiade, peserta meneruskan keputusan mereka ke server pengujian, yang “memeriksa” kode pada serangkaian tes yang telah disiapkan sebelumnya. Dalam hal berhasil menyelesaikan semua tes, peserta diberi skor poin. Kalau tidak, tim menerima umpan balik tentang kesalahan dan bisa membuat penyesuaian kode.

Menurut aturan ICPC, tim yang telah menyelesaikan sebagian besar tugas menang.

Jika beberapa peserta mencetak jumlah poin yang sama sekaligus, posisi mereka di klasemen ditentukan oleh waktu penalti. Waktu penalti dihitung untuk setiap masalah yang diselesaikan dengan benar dan sama dengan waktu yang telah berlalu sejak awal kompetisi hingga kode lulus semua tes. Selain itu, untuk setiap upaya yang gagal untuk menyelesaikan tugas, 20 menit ditambahkan ke penalti (hanya jika pada akhirnya masalah dapat diselesaikan). Tidak ada penalti yang diberikan jika tim belum menawarkan solusi yang tepat untuk masalah tersebut.


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

Untuk apa para finalis bersaing?

Seperti yang telah kami katakan, juara semi final - lima belas tim - akan pergi ke Portugal, ke kota Porto, di mana mereka akan bertarung untuk Piala Dunia dan $ 15.000. Tim yang akan berlangsung dari pertama hingga keempat akan diberikan medali emas. Peserta yang "selesai" di tempat-tempat dari kelima sampai kedelapan akan menerima medali perak, dan dari kesembilan ke kedua belas - perunggu. Hadiah uang tunai juga disediakan untuk mereka.

Tim Universitas ITMO telah menjadi juara ICPC selama tujuh kali (terakhir - pada 2017). Ini adalah rekor dunia yang belum pernah dikalahkan oleh siapa pun: di tempat kedua dalam jumlah gelar juara juga rekan senegaranya, Universitas Negeri St. Petersburg, dengan empat piala, dan rival asing terdekat, Stanford Amerika dan Universitas Cina Jao Tong - tiga kemenangan. Selama tujuh tahun berturut-turut, final dunia secara konsisten dimenangkan oleh tim-tim Rusia. Mari berharap di ICPC 2019 orang-orang akan menunjukkan hasil yang layak.

Tentang apa lagi yang kami tulis di Habré:

• Intisari Universitas ITMO: Studi Baru dan Proyek Internasional
• Bagaimana Kursus Pemrograman Tingkat Rendah di Universitas ITMO Bekerja