### riadwaw's blog

By riadwaw, history, 5 years ago, Tomorrow is GP of Dolgoprudny which is prepared by my colleagues and me.

Hope, you'll like the problems which we can discuss here after the contest.

Also, we've prepared mini-tutorial which I'll post here after the contest too.

Good luck!  Comments (5)
 »
 » My solutions for problems I had solutions. A#!/usr/bin/env python3 import sys n, m = [int(x) for x in input().split()] r = [['0'] * m for i in range(n)] for i in range(min(m, n)): r[i][i] = '1' for i in range(max(m, n) - 1, min(n, m) - 1, -2): if m > n: r[i] = '1' else: r[i] = '1' for l in r: print(''.join(l))  Busing Z = Zn

; class CycleExpectation { public: void solve(std::istream& in, std::ostream& out) { int n; in >> n >> P::value; Z ans; vector reverse(n + 1, Z::rawValueOf(1)); for (int i = 1; i <= n; ++i) { reverse[i] /= i; } vector addFrom(n + 1); for (int least = 1; least <= n; ++least) { fill(addFrom.begin(), addFrom.end(), 0); Z sum = Z::valueOf(1); for (int i = least; i < n; ++i) { sum += addFrom[i]; if (i + least <= n) { addFrom[i + least] += sum * reverse[i]; } } //cerr << (sum + addFrom[n]) / n << endl; ans += (sum + addFrom[n]) * reverse[n]; } out << ans << "\n"; } };  Cclass NoPalindromesNoAlpha { public: void solve(std::istream& in, std::ostream& out) { int k; in >> k; string s; in >> s; auto n = s.size(); vector v(s.size()); for (auto i: range(s.size())) { if (s[i] >= 'a') { v[i] = s[i] - 'a'; } else { v[i] = s[i] - 'A' + 26; } } auto cost = make_vector(k, k, 0); for (auto i: range(k)) { for (auto j: range(k)) { in >> cost[i][j]; } } if (n == 1) { out << 0; return; } if (k == 1) { out << -1; return; } if (n == 2) { int ans = 2000000000; for (int i: range(k)) { for (int j: range(k)) { if (i != j) ans = min(ans, cost[v][i] + cost[v][j]); } } out << ans << "\n"; return; } if (k == 2) { out << -1; return; } auto bestIndices = make_vector(k, k, 0); for (auto i : range(k)) { for (auto j: range(k)) { bestIndices[i][j] = j; } sort(bestIndices[i], [&](int a, int b) { return cost[i][a] < cost[i][b]; }); if (bestIndices[i].size() > 5) { bestIndices[i].resize(5); } } auto cur_ans = default_answer(); for (auto first_char_id: range(bestIndices[v].size())) { int first_char = bestIndices[v][first_char_id]; cur_ans[first_char_id] = {(uint64_t)cost[v][first_char], -1}; } for (auto i: range(1, (int) n)) { auto next_ans = default_answer(); for (auto last_char_id: range(bestIndices[v[i]].size())) { int last_char = bestIndices[v[i]][last_char_id]; auto& two_answers = next_ans[last_char_id]; for (auto prev_char_id: range(bestIndices[v[i - 1]].size())) { int prev_char = bestIndices[v[i - 1]][prev_char_id]; if (last_char == prev_char) { continue; } int index = 0; if (cur_ans[prev_char_id].second == last_char) { index = 1; } if (cur_ans[prev_char_id][index].first == std::numeric_limits::max()) { continue; } int64_t ans = cur_ans[prev_char_id][index].first + cost[v[i]][last_char]; std::pair curPair = {ans, prev_char}; for (int z: range(2)) { if(curPair < two_answers[z]) { swap(curPair, two_answers[z]); } } } } cur_ans = next_ans; } uint64_t ans = std::numeric_limits::max(); for (auto& c: cur_ans) { ans = min(ans, c.first); } out << ans << "\n"; } private: std::array, 2>, 5> default_answer() const { std::array, 2>, 5> dp; memset(&dp, -1, sizeof(dp)); return dp; } };  Dpublic class JavaSol implements Runnable { long leastBit(long x) { return x ^ (x & (x - 1)); } void solve() throws IOException { int n = nextInt(); long[] a = new long[n]; long sum = 0; long xor = 0; for (int i = 0; i < n; ++i) { a[i] = nextLong(); sum += a[i]; xor ^= a[i]; } if (xor == 0) { out.println(sum); int curLeastBit = 0; for (int i = 1; i < n; ++i) { if (leastBit(a[i]) < leastBit(a[curLeastBit])) { curLeastBit = i; } } out.println((curLeastBit + 1) + " 1"); } else { long maxTurn = 0; int bestIndex = 0; for (int i = 0; i < n; ++i) { long need = a[i] ^ xor; if (need < a[i]) { if (a[i] - need > maxTurn) { maxTurn = a[i] - need; bestIndex = i; } } } out.println(sum - maxTurn + 1); out.println((bestIndex + 1) + " " + maxTurn); } } }  Eclass Matrix { public: bool ask(const std::string& s) { return ask(vector{s}); } bool ask(const std::vector& s) { cout << "Query: " << s.size() << ' ' << s.size() << "\n"; for (const std::string& x: s) { cout << x << "\n"; } cout << flush; int x; cin >> x; return (bool) x; } void solve(std::istream& in, std::ostream& out) { int n, m; cin >> n >> m; string s; while (s.size() < m) { if (ask(s + "0")) { s += '0'; } else if (ask(s + "1")) { s += '1'; } else { break; } } while (s.size() < m) { if (ask("0" + s)) { s = "0" + s; } else { s = "1" + s; } } vector v = {s}; while (v.size() < n) { vector x = v; x.push_back("1" + string(m - 1, '?')); if (ask(x)) { v = x; } else { x.back() = '0'; if (ask(x)) { v = x; } else { break; } } } while (v.size() < n) { vector x = v; x.insert(x.begin(), "0" + string(m - 1, '?')); if (ask(x)) { v = x; } else { x.front() = '1'; v = x; } } for (int i: range(n)) { for (int j: range(m)) { if (v[i][j] == '?') { v[i][j] = '0'; if (!ask(v)) { v[i][j] = '1'; } } } } cout << "Answer:\n"; for (auto z: v) { cout << z << "\n"; } return; } };  Fclass Restrooms { public: void solve() { int n, m, k; cin >> n >> m >> k; vector b(n + 1, n); vector g(n + 1, n); for (int i: range(m)) { int l, r; cin >> l >> r; --l, --r; b[l] = min(b[l], r); } for (int i: range(k)) { int l, r; cin >> l >> r; --l, --r; g[l] = min(g[l], r); } vector db(n + 2); vector dg(n + 2); for (int i: inclusiveRange(0, (int)b.size() - 1)) { db[i + 1] = (i <= dg[i]) ? b[i] : min(b[i], db[i]); dg[i + 1] = (i <= db[i]) ? g[i] : min(g[i], dg[i]); } if (db.back() < n && dg.back() < n) { printf("No\n"); return; } cout << ("Yes\n"); string ans(n, ' '); int lastB = n; int lastG = n; for (int i: downrange(n)) { if (lastB <= db[i + 1]) { ans[i] = '1'; lastG = i; } else { assert(lastG <= dg[i + 1]); ans[i] = '0'; lastB = i; } } cout << ans << "\n"; } };  Gclass Doors { public: void solve(std::istream& in, std::ostream& out) { int n; in >> n; vector a(n); vector b(n); for (int i: range(n)) { in >> a[i] >> b[i]; } double l = 0, r = 1000000000; for (int _: range(100)) { auto can_fail = [&](double m) { double best_time_up = 0; double best_time_down = numeric_limits::infinity(); for (int i: range(n)) { if (b[i] == 0) { if (a[i] < m) { return true; } } if (b[i] < 0) { if (a[i] <= m) { return true; } double time = (a[i] - m) / -b[i]; best_time_down = min(time, best_time_down); } if (b[i] > 0) { if (a[i] >= m) { continue; } double time = (a[i] - m) / -b[i]; best_time_up = max(time, best_time_up); } } // can't fail ifx // 1 / speed <= best_time_down / n // 1 / speed >= best_time_up return best_time_down < best_time_up * n; }; double m = (l + r) / 2.0; if (can_fail(m)) { r = m; } else { l = m; } } out << (l + r) / 2.0; } };  Hclass Campus { public: void solve(std::istream& in, std::ostream& out) { int n; in >> n; vector> a(n); for (int i: range(n)) { in >> a[i].first >> a[i].second; if (a[i].first > a[i].second) { swap(a[i].first, a[i].second); } } int64_t answer = 0; int m; in >> m; vector c(m + 1); for (int i: range(m)) { in >> c[i]; } c.back() = -1000000000; sort(a); sort(c); int cIndex = 0; struct Event { int64_t x; int da; }; vector events; for (int i: range(n)) { while (cIndex != c.size() && c[cIndex] < a[i].first) { ++cIndex; } answer += a[i].second - a[i].first; if (cIndex < c.size() && a[i].second >= c[cIndex]) { // ok; } else { int64_t curExtra = 0; if (cIndex == 0) { curExtra = c[cIndex] - a[i].second; } else if (cIndex == c.size()) { curExtra = a[i].first - c[cIndex - 1]; } else { curExtra = min( c[cIndex] - a[i].second, a[i].first - c[cIndex - 1] ); } answer += curExtra * 2; events.push_back({a[i].first - curExtra, 2}); events.push_back({a[i].first, -2}); events.push_back({a[i].second, -2}); events.push_back({a[i].second + curExtra, 2}); } } sort(events, [](const Event& a, const Event& b) { return a.x < b.x; }); int64_t bestDecrease = 0; int64_t curx = 0; int64_t cura = 0; int64_t curda = 0; for (auto& event: events) { cura += curda * (event.x - curx); curda += event.da; curx = event.x; bestDecrease = max(bestDecrease, cura); } out << answer - bestDecrease; } };  Jpublic class JavaSol implements Runnable { void solve() throws IOException { int n = nextInt(); long newS = nextLong(); int[] x = new int[n]; int[] y = new int[n]; for (int i = 0; i < n; ++i) { x[i] = nextInt(); y[i] = nextInt(); } double P = 0; double S = 0; for (int i = 0; i < n; ++i) { double len = Math.sqrt(sqr(x[(i + 1) % n] - x[i]) + sqr(y[(i + 1) % n] - y[i])); P += len; S += ((long) x[(i + 1) % n] * y[i] - (long) x[i] * y[(i + 1) % n]) / 2.0; } S = Math.abs(S); if (S >= newS) { out.println(0); return; } double A = Math.PI; double B = P; double C = S - newS; double D = B * B - 4 * A * C; out.print((-B + Math.sqrt(D)) / 2 / A); } long sqr(long x) { return x * x; } }  Kclass CrossMebius { public: void solve(std::istream& in, std::ostream& out) { int n, m; in >> n >> m; int64_t sumAnswers = n * 1LL * m; int mx = 1000000; auto lp = linearSieve(mx); vector mebius(mx + 1); mebius = 1; for (int i: inclusiveRange(2, mx)) { if (lp[i] == lp[i / lp[i]]) { mebius[i] = 0; } else { mebius[i] = -mebius[i / lp[i]]; } } auto a = make_vector(2, 2, mx + 1, 0); for (int i: range(n)) { int x; in >> x; if (mebius[x]) ++a[(mebius[x] + 1) / 2][x]; } for (int i: range(m)) { int x; in >> x; if (mebius[x]) ++a[(mebius[x] + 1) / 2][x]; } auto& s = a; for (int k: range(2)) { for (int l: range(2)) { for (int i: inclusiveRange(1, mx)) { for (int j = i * 2; j <= mx; j += i) { s[k][l][i] += a[k][l][j]; } } } } int64_t ans = {0, 0}; for (int i: range(2)) { for (int j: range(2)) { for (int k: inclusiveRange(1, mx)) { ans[i ^ j ^ 1] += 1LL * s[i][k] * s[j][k] * mebius[k]; } } } out << ans << ' ' << sumAnswers - ans - ans << ' ' << ans << "\n"; } }; 

 » Nice problem set. May I ask why do you make B with n = 104? I think it's more fair to have n = 5, 000 for O(n2) solution.With n = 104, we should be extremely careful with the constant involved in the computation.
•  » » 5 years ago, # ^ | ← Rev. 2 →   It was made to prevent solutions with complexity. Sorry if you had to spend much time optimizing your solution.
 » Can you provide the contest link please?