### AlexDmitriev's blog

By AlexDmitriev, history, 3 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!

• +165

 » 3 years ago, # |   +14
 » 3 years ago, # |   +22 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[0][i] = '1' else: r[i][0] = '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[0]][i] + cost[v[1]][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[0]].size())) { int first_char = bestIndices[v[0]][first_char_id]; cur_ans[first_char_id][0] = {(uint64_t)cost[v[0]][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][0].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[0].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[0].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] = '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()[0] = '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] = 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[0][(mebius[x] + 1) / 2][x]; } for (int i: range(m)) { int x; in >> x; if (mebius[x]) ++a[1][(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[2] = {0, 0}; for (int i: range(2)) { for (int j: range(2)) { for (int k: inclusiveRange(1, mx)) { ans[i ^ j ^ 1] += 1LL * s[0][i][k] * s[1][j][k] * mebius[k]; } } } out << ans[0] << ' ' << sumAnswers - ans[0] - ans[1] << ' ' << ans[1] << "\n"; } }; 

 » 3 years ago, # |   +18 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.
•  » » 3 years ago, # ^ | ← Rev. 2 →   +5 It was made to prevent solutions with complexity. Sorry if you had to spend much time optimizing your solution.
 » 3 years ago, # |   +15 Can you provide the contest link please?