"लाइव प्रोग्रामिंग": ITMO विश्वविद्यालय में ICPC क्षेत्रीय सेमीफाइनल कैसे हुआ

दिसंबर की शुरुआत में, ICPC छात्र प्रोग्रामिंग वर्ल्ड चैम्पियनशिप का सेमीफाइनल। हम आपको बताएंगे कि प्रतिभागियों ने "ट्रायल" क्या किया और कौन वसंत में उत्तर यूरेशिया क्षेत्र का प्रतिनिधित्व करेगा, खेल के मुख्य टूर्नामेंट के विश्वस्तरीय टूर्नामेंट में।


^{icpcnews / फ़्लिकर / सीसी बाय / फ़ाइनल ICPC-2017}

पंद्रह विजेता

प्रतियोगिताओं, जिसमें 300 से अधिक टीमों ने भाग लिया, एक साथ चार स्थानों पर हुई: सेंट पीटर्सबर्ग, बरनौल, त्बिलिसी और अल्मा-अता में। आईटीएमओ विश्वविद्यालय को रूस और बाल्टिक राज्यों से सौ से अधिक टीमें मिली हैं। प्रतिभागियों ने NEERC उत्तरी यूरेशिया कप और ICPC के फाइनल में जाने के अधिकार के लिए लड़ाई लड़ी।


मॉस्को स्टेट यूनिवर्सिटी की टीम ग्यारह समस्याओं को हल करने के लिए पूर्ण चैंपियन बन गई । कोई भी ऐसा करने में कामयाब नहीं हुआ। दूसरे और तीसरे स्थान पर MIPT के प्रतिभागी थे। "लड़ाइयों" की प्रगति को लाइव देखा जा सकता था। ICPC YouTube चैनल पर एक रिकॉर्ड है:


कुल मिलाकर, पंद्रह टीमों को ICPC-2019 के फाइनल में चुना गया था (पूरी सूची यहां पाई जा सकती है ), जिसमें ITMO विश्वविद्यालय के लोग भी शामिल हैं। मार्च के अंत में, वे विश्व चैंपियन के खिताब के लिए लड़ने के लिए पोर्टो (पुर्तगाल) शहर जाएंगे।

सेमीफाइनल में कैसे गए?

छात्रों ने जावा, सी ++, पायथन या कोटलिन प्रोग्रामिंग भाषाओं का उपयोग किया। सभी कार्यों में सावधानी, एकाग्रता और विभिन्न एल्गोरिदम के ज्ञान की आवश्यकता होती है।

उदाहरण के लिए, ITMO विश्वविद्यालय की टीम Gennady Korotkevich के हिस्से के रूप में ICPC के दो बार विजेता द्वारा निम्नलिखित कार्य प्रस्तावित किया गया था:

एक अप्रत्यक्ष रूप से अप्रकाशित ग्राफ है। दो कोने u और v के बीच की दूरी को सबसे कम पथ में किनारों की संख्या से निर्धारित किया जाता है। सभी अव्यवस्थित जोड़ियों के योग d (u, v) का पता लगाएं।

सबसे पहले, दो नंबर n और m (2 two n ; 10 ⁵ ; n-1 numbers m + n + 42) - क्रमशः कोने और किनारों की संख्या, प्रोग्राम इनपुट को खिलाया जाता है। कोने 1 से n तक गिने जाते हैं। अगला, मी लाइनें दो पूर्णांक मानों के साथ दर्ज की जाती हैं: x _i और y _i (1, x _i , y _i ≠ n; x _i x y _i ) - ये ith edge के अंतिम बिंदु हैं। किसी भी जोड़ी के बीच कम से कम एक किनारे होता है।

एक समाधान के साथ उदाहरण कार्यक्रम (एक जूरी सदस्य द्वारा प्रस्तावित):

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 )।

एक अन्य कार्य "शतरंज" है:

एल्मा शतरंज खेलना सीखता है और पहले से जानता है कि बदमाश क्षैतिज या लंबवत चलता है। एल्मा की दादी ने उसे एक 8x8 शतरंज की बिसात दी और उसे सेल ए 1 से एच 8 तक की चाल में n चाल में रास्ता खोजने के लिए कहा। इस मामले में, सभी कोशिकाएं जिन पर आंकड़ा रुकता है, उन्हें अलग होना चाहिए। इनपुट को मूल्य n (2 ≤ n supplied 63) के साथ आपूर्ति की जाती है। प्रतिभागियों को उन सभी कोशिकाओं को सूचीबद्ध करने की आवश्यकता है, जिन्हें एल्मा ने किश्ती पर रखा था।

यहाँ इस समस्या के समाधान का एक उदाहरण है जो जूरी सदस्यों द्वारा प्रस्तावित किया गया था:

जावा कोड

 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 / फ़्लिकर / सीसी बाय / फ़ाइनल ICPC-2017}

फाइनल के लिए प्रतिस्पर्धा क्या होगी?

जैसा कि हमने पहले ही कहा है, सेमीफाइनल चैंपियन - पंद्रह टीमें - पुर्तगाल में, पोर्टो शहर जाएंगी, जहां वे विश्व कप और $ 15,000 के लिए लड़ेंगे। पहली से चौथी तक होने वाली टीमों को स्वर्ण पदक से सम्मानित किया जाएगा। पांचवें से आठवें स्थान पर "समाप्त" होने वाले प्रतिभागियों को रजत पदक प्राप्त होंगे, और नौवें से बारहवें - कांस्य तक। उनके लिए नकद पुरस्कार भी प्रदान किए जाते हैं।

ITMO यूनिवर्सिटी टीम सात बार (आखिरी - 2017 में) ICPC की चैंपियन बन गई है। यह एक विश्व रिकॉर्ड है जिसे अभी तक किसी ने नहीं हराया है: चैंपियन खिताबों की संख्या में दूसरे स्थान पर भी चार कप के साथ हमवतन, सेंट पीटर्सबर्ग स्टेट यूनिवर्सिटी, और निकटतम विदेशी प्रतिद्वंद्वी, अमेरिकी स्टैनफोर्ड और चीनी विश्वविद्यालय जोओ टोंग - तीन जीत हैं। लगातार सात वर्षों तक, विश्व फाइनल लगातार रूसी टीमों द्वारा जीता गया है। आइए उम्मीद करते हैं कि ICPC 2019 में लोग एक अच्छा परिणाम दिखाएंगे।

हमरे पर और क्या लिखते हैं:

• आईटीएमओ विश्वविद्यालय डाइजेस्ट: नए अध्ययन और अंतर्राष्ट्रीय परियोजनाएं
• आईटीएमओ यूनिवर्सिटी वर्क्स में लो-लेवल प्रोग्रामिंग कोर्स कैसे करें