Hello!

Traditionally AIM Tech organizes a big party for Petrozavodsk camp participants to have fun and get an opportunity to communicate with each other. Usually it comes along with a funny contest in unusual format. This year we decided to share the fun with all codeforces community!

This year we came up with a format requiring (probably) less time for preparing the contest. It is somewhat similar to an ordinary contest with a 3-hour duration. We already have some problem ideas, so it should be super easy to prepare the problems just one night before the competition. We hope everything will run smoothly!

The contest will start on Feb/03/2020 19:15 (Moscow time). It could be a bit rescheduled due to onsite delays.

It will be an unrated funny competition. Unlike usual ICPC-style contests, you'll be given an archive with several open test cases and answers for each problem. You'll have some sample test cases in the statement too, they'll be included in the archive. However, the solutions will be tested against both open and hidden tests. The open tests will be published as an encrypted zip-archive in this post. The password will be published just before the start of the contest.

The statements will be in English only because we are running out of time in preparation and have to prioritize things.

It's not 100-percent clear at the moment, but it seems the contest will be somewhat hard, so we recommend it for div. 1 participants. However, div. 2 participants are welcome as always, but we can't guarantee the contest will be a perfect match for them.

It's possible to participate both individually and in teams of maximum 3 persons.

Another point to mention is that the order of problems could be not the same as the order of their difficulties. But we'll try to do so. A bit.

The authors to blame are Kostroma, zemen, Golovanov399, mathbunnyru and ArtDitel.

As you may notice, it is just one night before the competition, so we should start preparing the problems. We hope that we'll manage not to do very stupid bugs in the tests. See you at the competition!

UPD It's still more than 4 hours before the contest, but the open tests are already prepared! You can download the archive using one of the two links: one two. The encrypted archive contains another archive containing the actual tests.

The password will be published here shortly before the start of the contest.

UPD2 We have to move contest 10 minutes forward, because we need to prepare the last problem :(

UPD3 Oops, the contest is about to start, but we still don't have correct solutions! Unfortunately, each authors' solution contains a bug (or even several bugs!). However, we decided not to cancel the competition. We give you the outputs of the model solutions on open tests in the archive. Guess all the bugs in our solutions and get OK for the code with exactly same bugs! Good luck and have fun!

The password to the archive will be published as a clarification in the contest interface.

UPD4 The password to the archive is oops_seems_that_nobody_tested_the_solutions

UPD5 The editorial is published, but it still does contain bugs, wait a bit while it is being debugged.

UPD6 Feel free to share your opinion in the comments! Were the solutions enough buggy? Was it enough hard, or we should've added a couple of hard problems? Do you want to solve such contests in future?

Thanks bmerry for posting his solutions, we gently took some of them as a base for editorial.

Problem author: VadymKa

Problem developers: riadwaw, malcolm

static class SquareInside {
        final int inf = (int) 1e9;

        public void solve(int testNumber, InputReader in, PrintWriter out) {
            int n = in.readInt(), m = in.readInt();
            char[][] s = new char[n][];
            for (int i = 0; i < n; i++) {
                s[i] = in.readWord().toCharArray();
            }
            int minX = inf, maxX = -inf, minY = inf, maxY = -inf;
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if (s[i][j] == 'B') {
                        minX = Math.min(minX, i);
                        minY = Math.min(minY, j);
                        maxX = Math.max(maxX, i);
                        maxY = Math.max(maxY, j);
                    }
                }
            }
            out.print((minX + maxX) / 2 + 1);
            out.print(' ');
            out.println((minY + maxY) / 2 + 1);
        }

    }

Problem author: VadymKa

Problem developers: riadwaw, malcolm, Kostroma, Errichto

  int len = 400;
  cout << string(len, '5') << "\n";
  cout << (string(len - 1, '4') + '5') << "\n";

Problem author: malcolm

Problem developers: yarrr, Edvard, malcolm, Errichto

static class Rectangle {
        public Point topLeft, bottomRight;

        public Rectangle(Point topLeft, Point bottomRight) {
            this.topLeft = topLeft;
            this.bottomRight = bottomRight;
        }

        public Rectangle intersect(Rectangle other) {
            if (other == null) {
                return null;
            }
            int x0 = Math.max(topLeft.x, other.topLeft.x);
            int y0 = Math.max(topLeft.y, other.topLeft.y);
            int x1 = Math.min(bottomRight.x, other.bottomRight.x);
            int y1 = Math.min(bottomRight.y, other.bottomRight.y);
            if (x0 > x1 || y0 > y1) {
                return null;
            }
            return new Rectangle(new Point(x0, y0), new Point(x1, y1));
        }
    }

    private void solve() throws IOException {
        int rectanglesCount = nextInt();
        Rectangle[] rectangles = new Rectangle[rectanglesCount];
        for (int i = 0; i < rectanglesCount; i++) {
            Point topLeft = new Point(nextInt(), nextInt());
            Point bottomRight = new Point(nextInt(), nextInt());
            rectangles[i] = new Rectangle(topLeft, bottomRight);
        }
        Rectangle[] prefixIntersection = new Rectangle[rectanglesCount + 1];
        Rectangle[] suffixIntersection = new Rectangle[rectanglesCount + 1];
        prefixIntersection[0] = suffixIntersection[0] = new Rectangle(
            new Point(Integer.MIN_VALUE, Integer.MIN_VALUE),
            new Point(Integer.MAX_VALUE, Integer.MAX_VALUE)
        );
        for (int i = 1; i <= rectanglesCount; i++) {
            prefixIntersection[i] = rectangles[i - 1].intersect(prefixIntersection[i - 1]);
            suffixIntersection[i] = rectangles[rectanglesCount - i].intersect(suffixIntersection[i - 1]);
        }

        for (int i = 0; i <= rectanglesCount; i++) {
            if (prefixIntersection[i] != null) {
                Rectangle intersection = prefixIntersection[i].intersect(suffixIntersection[rectanglesCount - i - 1]);
                if (intersection != null) {
                    out.println(intersection.topLeft);
                    return;
                }
            }
        }
        throw new AssertionError();
    }

Bonus: Solve the problem, if you need to find intersection of some n - k of n rectangles, if k ≤ 10. Without data structures.

Problem author: Errichto

Problem developers: zemen, Errichto, Kostroma, riadwaw

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;

const int mod = 1e9 + 7;

signed main() {
#ifdef LOCAL
  assert(freopen("test.in", "r", stdin));
#endif
  int n;
  cin >> n;
  map<int, int> a{{INT_MIN, 1}, {INT_MAX, 0}};
  set<int*> non0{&a.begin()->second};
  for (int i = 0; i < n; ++i) {
    string t;
    int x;
    cin >> t >> x;
    if (t == "ADD") {
      auto it = a.lower_bound(x);
      assert(it != a.begin());
      --it;
      int ways = it->second;
      auto m = a.emplace(x, ways).first;
      non0.insert(&m->second);
    } else {
      auto m = a.find(x);
      assert(m != a.end() && m != a.begin());
      auto it = prev(m);
      auto& w = it->second;
      w = (w + m->second) % mod;
      non0.insert(&it->second);
      non0.erase(&m->second);
      a.erase(m);
      for (auto it2 = non0.begin(); it2 != non0.end(); ) {
        if (*it2 == &it->second) {
          ++it2;
        } else {
          *(*it2) = 0;
          it2 = non0.erase(it2);
        }
      }
    }
  }
  int res = 0;
  for (auto p : a) {
    res = (res + p.second) % mod;
  }
  cout << res << '\n';
}

Problem author: zemen

Problem developers: yarrr, Kostroma

void solve(__attribute__((unused)) bool read) {
  int n;
  cin >> n;
  vector<int> b(n, 0);
  for (int i = 0; i < n; ++i) {
    cin >> b[i];
  }
  int mx = *max_element(all(b));
  int start_pos = -1;
  for (int i = 0; i < n; ++i) {
    if (b[i] == mx && b[(i - 1 + n) % n] != mx) {
      start_pos = i;
      break;
    }
  }
  if (start_pos == -1) {
    if (mx == 0) {
      cout << "YES\n";
      for (int i = 0; i < n; ++i) {
        cout << 1 << " \n"[i + 1 == n];
      }
      return;
    }
    cout << "NO\n";
    return;
  }
  auto a = b;
  for (int i = 1; i < n; ++i) {
    int pos = (start_pos - i + n) % n, prev_pos = (start_pos + 1 - i + n) % n;
    a[pos] += a[prev_pos];
    if (i == 1) {
      a[pos] += mx;
    }
  }
  cout << "YES\n";
  for (int x : a) {
    cout << x << " ";
  }
  cout << "\n";

}

Problem author: Errichto

Problem developers: Kostroma, malcolm

struct Point {
  int x, y;
  Point() {}
  Point(int x, int y) : x(x), y(y) {}
  void scan() {
    cin >> x >> y;
  }
  auto key() const {
    return make_pair(x, y);
  }
  bool operator < (const Point& ot) const {
    return key() < ot.key();
  }
  bool operator == (const Point& ot) const {
    return key() == ot.key();
  }
  Point operator + (const Point& ot) const {
    return Point(x + ot.x, y + ot.y);
  }
  li sqr_dist() {
    return x * 1LL * x + y * 1LL * y;
  }
  void normalize() {
    auto g = gcd(x, y);
    x /= g;
    y /= g;
  }
};

struct Hasher {
  size_t operator () (const Point& pt) const {
    return pt.x * 2352345 + pt.y;
  }
};

enum Type {
  INSERT = 1,
  REMOVE = 2,
  QUERY = 3
};

struct Query {
  Type type;
  Point pt;
  int dist_id;
  void scan() {
    int type1;
    cin >> type1;
    type = Type(type1);
    pt.scan();
  }
};

void solve(__attribute__((unused)) bool read) {
  int Q;
  cin >> Q;
  vector<Query> queries(Q);
  map<li, vector<Point>> all_points;
  vector<li> dists;
  set<Point> have;
  for (int i = 0; i < Q; ++i) {
    queries[i].scan();
    auto& pt = queries[i].pt;
    if (queries[i].type != QUERY) {
      all_points[pt.sqr_dist()].push_back(pt);
      dists.push_back(pt.sqr_dist());
    } else {
      pt.normalize();
    }
  }
  make_unique(dists);
  for (auto& q : queries) {
    q.dist_id = (int)(lower_bound(all(dists), q.pt.sqr_dist()) - dists.begin());
  }
  vector<vector<char>> has_point(dists.size());
  vector<vector<Point>> points_by_dist_id(dists.size());
  vector<vector<vector<Point>>> sum_points(dists.size());
  unordered_map<Point, pair<int, int>, Hasher> point_position;
  for (auto& item : all_points) {
    make_unique(item.second);
    int dist_id = (int)(lower_bound(all(dists), item.first) - dists.begin());
    has_point[dist_id].assign(item.second.size(), false);
    points_by_dist_id[dist_id] = item.second;
    sum_points[dist_id].assign(item.second.size(), vector<Point>(item.second.size()));
    for (int i = 0; i < item.second.size(); ++i) {
      point_position[item.second[i]] = {dist_id, i};
      for (int j = 0; j < item.second.size(); ++j) {
        sum_points[dist_id][i][j] = item.second[i] + item.second[j];
        sum_points[dist_id][i][j].normalize();
      }
    }
  }
  unordered_map<Point, int, Hasher> on_line;
  unordered_map<Point, int, Hasher> good_pairs;

  auto change_on_line = [&] (Point pt, bool add) {
    pt.normalize();
    if (add) {
      ++on_line[pt];
    } else {
      assert(on_line[pt] > 0);
      --on_line[pt];
    }
  };

  int n_points = 0;
  for (auto& cur_q : queries) {
    auto& pt = cur_q.pt;
    int dist_id = cur_q.dist_id;
    if (cur_q.type == INSERT) {
      ++n_points;
      int pos = point_position[pt].second;
      assert(!has_point[dist_id][pos]);
      change_on_line(pt, true);
      for (int i = 0; i < points_by_dist_id[dist_id].size(); ++i) {
        if (i == pos || !has_point[dist_id][i]) {
          continue;
        }
        ++good_pairs[sum_points[dist_id][i][pos]];
      }
      has_point[dist_id][pos] = true;
    } else if (cur_q.type == REMOVE) {
      --n_points;
      int pos = point_position[pt].second;
      assert(has_point[dist_id][pos]);
      change_on_line(pt, false);
      for (int i = 0; i < points_by_dist_id[dist_id].size(); ++i) {
        if (i == pos || !has_point[dist_id][i]) {
          continue;
        }
        --good_pairs[sum_points[dist_id][i][pos]];
      }
      has_point[dist_id][pos] = false;
    } else if (cur_q.type == QUERY) {
      pt.normalize();
      cout << n_points - 2 * good_pairs[pt] - on_line[pt] << "\n";
    }
  }

}

Problem author: zeliboba

Problem developers: Kostroma, riadwaw

private static final int MAX_WIDTH = 10000;
    private static final int QUERIES = 5;
    public static final long INF = 20000000000000000L;
    long[][] memo = new long[QUERIES + 1][MAX_WIDTH + 1];

    long dp(int guesses, long l) {
        if (guesses == 0) {
            return l;
        }
        if (l > MAX_WIDTH) {
            return Math.min(INF, dp(guesses, MAX_WIDTH) + l - MAX_WIDTH);
        }

        if (memo[guesses][(int) l] != 0) {
            return memo[guesses][(int) l];
        }
        long ans = l;
        for (int i = 0; i < l; ++i) {
            ans = dp(guesses - 1, ans);
            ++ans;
        }
        ans = dp(guesses - 1, ans);
        return memo[guesses][(int) l] = Math.min(ans, INF);
    }
    private void run() throws IOException {
        long l = 1;
        long r = dp(QUERIES, 1);
        for (int queriesNext = QUERIES - 1; queriesNext >= 0; --queriesNext) {
            List<Long> query = new ArrayList<>();
            long curL = l;
            for (int i = 0, e = (int)Math.min(l, MAX_WIDTH); i < e; ++i) {
                long end = dp(queriesNext, curL);
                query.add(end);
                curL = end + 1;
            }
            assert r == dp(queriesNext, curL);
            out.print(query.size());
            for (long x: query) {
                out.print(" ");
                out.print(x);
            }
            out.println();
            out.flush();
            System.out.flush();

            int ans = readInt();
            if (ans < 0) {
                return;
            }
            if (ans > 0) {
                l = query.get(ans - 1) + 1;
            }
            if (ans != query.size()) {
                r = query.get(ans);
            }

            assert dp(queriesNext, l) == r;
        }
    }

Problem author: Kostroma

Problem developers: Kostroma, riadwaw, gchebanov, malcolm

const int C = 5032107 + 1;
int lp[C];
int fred[C];
int num_primes[C];

const int MAX_DIVISORS = 7;
const int MAX_ANS = 2 * MAX_DIVISORS;

int max_left[MAX_DIVISORS + 1][C];
int max_border[MAX_ANS + 1];

vector<int> cur_primes;

vector<int> divs;

void get_divisors(int n) {
    divs = {1};
    while (n > 1) {
        int p = lp[n];
        n /= p;
        int sz = divs.size();
        for (int i = 0; i < sz; ++i) {
            divs.push_back(divs[i] * p);
        }
    }
}

void solve(bool read) {
    vector<int> pr;
    for (int i = 2; i < C; ++i) {
        if (lp[i] == 0) {
            lp[i] = i;
            pr.push_back(i);
        }
        for (int j = 0; j < pr.size() && pr[j] <= lp[i] && i * pr[j] < C; ++j) {
            lp[i * pr[j]] = pr[j];
        }
    }
    fred[1] = 1;
    for (int i = 2; i < C; ++i) {
        int p = lp[i];
        int cur = i / p;
        if (cur % p == 0) {
            fred[i] = fred[cur / p];
            num_primes[i] = num_primes[cur / p];
        } else {
            fred[i] = p * fred[cur];
            num_primes[i] = num_primes[cur] + 1;
        }
    }

    for (int i = 0; i < C; ++i) {
        for (int j = 0; j <= MAX_DIVISORS; ++j) {
            max_left[j][i] = -1;
        }
    }
    memset(max_border, -1, sizeof(max_border));

    int n;
    cin >> n;
    int Q;
    cin >> Q;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        a[i] = fred[a[i]];
    }

    vector<vector<pair<int, int>>> queries(n);

    vector<int> res(Q);
    for (int i = 0; i < Q; ++i) {
        int l, r;
        cin >> l >> r;
        --l; --r;
        queries[r].push_back({l, i});
    }

    for (int i = 0; i < n; ++i) {
        get_divisors(a[i]);
        for (int d : divs) {
            int first_add = num_primes[a[i]] - num_primes[d];
            for (int prev_ans = 0; prev_ans <= MAX_DIVISORS; ++prev_ans) {
                int cur_left = max_left[prev_ans][d];
                int cur_ans = first_add + prev_ans;
                if (cur_ans <= MAX_ANS) {
                    relax_max(max_border[cur_ans], cur_left);
                }
            }
        }
        for (int d : divs) {
            int first_add = num_primes[a[i]] - num_primes[d];
            relax_max(max_left[first_add][d], i);
        }
        for (auto q : queries[i]) {
            res[q.second] = MAX_ANS + 1;
            for (int cur_ans = 0; cur_ans <= MAX_ANS; ++cur_ans) {
                if (max_border[cur_ans] >= q.first) {
                    res[q.second] = cur_ans;
                    break;
                }
            }
            assert(res[q.second] <= MAX_ANS);
        }
    }

    int sum_ans = 0;
    for (int i = 0; i < Q; ++i) {
        cout << res[i] << '\n';
    }
}

Привет, Codeforces!

Oт лица компании AIM Tech я рад сообщить, что 24 февраля начнется HFT Battle — соревнование по написанию торговых стратегий на основе реальных биржевых данных. Мы постарались сделать это соревнование интересным и для программистов-олимпиадников, и для фанатов challenge24, и для специалистов в области машинного обучения.

Участникам предстоит погрузиться в исследование рынка на примере фьючерсов биржи CME и написать свой собственный алгоритм высокочастотной торговли. Задача алгоритма — продемонстрировать стабильно высокий результат на наборе из нескольких торговых сессий.

Для создания стратегии не требуется специальных экономических знаний и достаточно базовых навыков программирования на C++. Мы уверены, что многие участники Codeforces добьются положительных результатов!

Соревнование будет проходить с 24 февраля по 24 апреля 2016 года на платформе http://hftbattle.com.

Победитель получит в подарок поездку на двоих на любое спортивное, музыкальное или другое событие в 2016 году в любую точку мира: Олимпийские игры в Бразилии, концерт Red Hot Chili Peppers в Нидерландах, Чемпионат Европы по футболу во Франции, фестиваль Burning Man в США или любой другой ваш вариант.

Всех участников, достигших значительных результатов, мы наградим ценными призами. А победители каждого еженедельного тестирования получат памятные сувениры.

Желаем всем удачи и высоких результатов!

UPD Соревнование началось!

UPD Первый участник, набравший "плюс" в рейтинге, получит подарок на выбор: Das Keyboard 4, Sony SmartWatch 3 или Beyerdynamic DT 400!

UPD Объявлен новый конкурс: участник с наибольшим положительным результатом на контрольной выборке на момент 03:00 9 марта получит аналогичный приз! Обратите внимание на дополнительное условие: стратегия должна зарабатывать как минимум 1000$ и делать в среднем не менее 1000 сделок в день.

Привет, codeforces!

18 ноября в рамках MIPT-2015 ACM ICPC Workshop мы провели контест от нашей компании. В команду разработчиков задач вошли: zeliboba, gchebanov, Kostroma, riadwaw, yarrr, ValenKof, ArtDitel, Endagorion.

В воскресенье, 29 ноября, в 11-00 МСК будет проведена неофициальная трансляция этого соревнования на платформе Яндекс.Контест. Приглашаем поучаствовать всех желающих! Уверены, что каждый найдёт интересные для себя задачи в этом проблемсете.

P.S. Про MIPT-2015 ACM ICPC Workshop можно прочитать в блоге Rubanenko.

572A - Arrays

In this problem one need to check whether it's possible to choose k elements from array A and m elements from array B so that each of chosen element in A is less than each of chosen elements in B. If it's possible then it's possible to choose k smallest elements in A and m largest elements in B. That means that in particular, k-th smallest element of A is less than m-th largest element in B. So, if A[k] < B[n - m + 1] then the answer is "YES" and if not, then the answer is "NO".

Problem author: zeliboba.

Problem developers: riadwaw, Kostroma.

Solution code: 12873382.

572B - Order Book

First of all the problem may be solved for buy orders and sell orders separately.

The easiest soultion is to use structure like std::map or java.lang.TreeMap. To aggregate orders we just add volume to the corresponding map element: aggregated[price] += volume.

After that we should extract lowest (or largest) element from map s times (or while it's not empty).

Complexity of this solution is O(nlogn).

It is also possible to solve the problem without data structres other than an array. You should just maintain at most s best orders in sorted order and when adding another order you insert it in appropriate place and move worse elements in linear time of s. Complexity of this solution is O(sn).

Problem authors and developers: ArtDitel, yarrr.

Solution code: 12873385.

571A - Lengthening Sticks

Let's count the number of ways to form a triple which can't represent triangle sides, and then we subtract this value from — the total number of ways to increase the sticks not more than l in total. This number is obtained from partition of l into 4 summands (l_a + l_b + l_c + unused_l = l), or can be counted using a for loop.

Now we consider triples a + l_a, b + l_b, c + l_c, where l_a + l_b + l_c ≤ l, l_a, l_b, l_c ≥ 0. Fix the maximal side, for example it would be a + l_a. We'll have to do the following algo for b + l_b and c + l_c in the same way. The triple is not a triangle with maximal side a + l_a if a + l_a ≥ b + l_b + c + l_c. If we iterate over l_a between 0 and l, we have the following conditions on l_b, l_c:

l_b, l_c ≥ 0. So, non-negative integers l_b, l_c should be such that l_b + l_c ≤ min(a - b - c + l_a, l - l_a). If we denote this minimum as x than we can choose l_b, l_c in different ways (again we divide x into three summands: l_b, l_c and some unused volume). Also when we fix l_b, there are x - l_b + 1 ways to choose l_c, so the overall number of pair l_b, l_c is

so we obtain the same formula.

To sum up, we need to iterate over the maximal side and over the addition to that side, then write these formulas, and subtract the result from the total number of different additions to the sides. The complexity of the solution is O(l).

Problem author: Kostroma.

Problem developers: Kostroma, riadwaw.

Solution code: 12873406.

571B - Minimization

We can divide all indices [1;n] into groups by their remainder modulo k. While counting , we can consider each group separately and sum the distances between neighbouring numbers in each group.

Consider one group, corresponding to some remainder i modulo k, i.e. containing a_j for . Let's write down its numbers from left to right: b₁, b₂, ..., b_m. Then this group adds to the overall sum the value

We can notice that if we sort b₁, ..., b_m in non-decreasing order, this sum will not increase. So, in the optimal answer we can consider that numbers in each group don't decrease. Furthermore, in that case this sum is equal to |b_m - b₁|.

Now consider two groups b₁, ..., b_m and c₁, c₂, ..., c_l, both sorted in non-decreasing order. We claim that either b₁ ≥ c_l or b_m ≤ c₁, i.e. segments [b₁, b_m] and [c₁, c_l] can have common points only in their endpoints.

Why is this true? These groups add |b_m - b₁| + |c_l - c₁| to the overall sum. We consider the case c₁ ≥ b₁, the other is symmetric. If c₁ < b_m, then swapping c₁ and b_m will not increase the values these groups add to the answer, since the right border of b group moves to the left, and the left border of c group moves to the right. So, c₁ ≥ b_m in that case, and the assertion is proved.

Now we know that the values in each group should from a continuous segment of the sorted original array. In fact, we have groups of size (so called small groups) and groups of size (so called large groups). Consider the following dynamic programming: dp[L][S] — the minimal sum of values added to the answer by L large groups and S small groups, if we choose the elements for them from the first elements of the sorted array A. There are no more than O(k²) states, and each transition can be made in O(1): we choose large or small group to add and obtain the number it adds to the sum by subtracting two elements of the sorted array. The answer for the problem will be in .

The overall complexity of the solution is . We can note that in pretests was quite small, and some slower solutions could pass, but they failed on final tests.

Problem author: zeliboba.

Problem developers: Kostroma, riadwaw.

Solution code: 12873418.

571C - CNF 2

Firstly let's assign values to variables occurring in our fomula only with negation or only without negation. After that we can throw away the disjuncts which contained them, since they are already true, and continue the process until it is possible. To make it run in time limit, one should use dfs or bfs algorithm to eliminate these variables and disjuncts.

So now we have only variables which have both types of occurrences in disjucnts. Let's build a graph with the vertices corresponding to disjuncts, and for each varible a make an edge between the disjuncts that contain a and !a. Now we should choose the directions of edges in this graph in such a way that every vertex has at least one incoming edge.

We can notice that if some connected component of this graph is a tree, the solution is not possible: on each step we can take some leaf of this tree, and we have to orient its only edge to it, and then erase the leaf. In the end we'll have only one vertex, and it'll not have any incoming edges.

Otherwise, take some cycle in the component and orient the edges between neighbouring vertices along it. Then run dfs from every vertex of the cycle and orient each visited edge in the direction we went along it. It is easy to easy that after this process every vertex will have at least one incoming edge.

So, we should consider cases with the variables which values can be assigned at once, than construct a graph from disjuncts and variables and find whether each connected component has a cycle. If so, we also should carefully construct the answer, assigning the remaining variables their values, looking at the directions of the edges in the graph. The overall complexity is O(n + m).

Problem author: zeliboba.

Problem developers: Kostroma, zeliboba, yarrr.

Solution codes: 12873432 (linear solution), 12873446 (), 12873456 (matching solution).

571D - Campus

Let's suppose for each dormitory from Q query we already know the last raid moment.

When task will be much easier: we can throw away M and Z queries and to get right answer we should subtract two values: people count in dormitory right now and same count in a last raid moment.

On this basis, we have such plan:

1. For each Q query let's find the last raid moment using M and Z queries.
2. Find people count in two interesting moments using U and A queries.
3. Calculcates the final answer.

Let's try to solve the first part.

We want to make such queries on disjoint sets:

1. Merge two sets (M query).
2. Assign value time for all elements in particular set (Z query).
3. Get value for a particular element (Q query).

To solve this task we'll use a well-known technique: "merge smaller set to bigger".

We'll maintain such values:

• elements — set elements.
• set_id — for each element their set id.
• last_set_update_time — last moment when assign operation has occurred for each set.
• last_update_time — last moment when assign operation has occurred for each element.
• actual_time — moment of time when last_update_time was actually for the element.

Let's focus on actual_time value.

It's obvious that when we merge two sets each element can have a different last assign moment. But after first assignment all elements from any set will have the same value. So the answer for Q query for element i from set s: If last_set_update_time[s]=actual_time[i] then last_update_time[i] else last_set_update_time[s]

For each Z query you should just update last_set_update_time array.

It's easy to maintain this values when you merge two sets:

Let's suppose we want to merge set from to set to. For each element from set from we already know last assign time. So just update last_update_time with this value and actual_time is equal of last assign operation for set to.

The second part of the solution is the same as first one.

O(n * lg(n) + m) time and O(n + m) memory.

Problem author: ArtDitel.

Problem developers: yarrr, gchebanov, Kostroma.

Solution codes: 12873477 (solution, described in the editorail), 12873469 (solution with treaps).

571E - Geometric Progressions

If intersection of two geometric progressions is not empty, set of common elements indexes forms arithmetic progression in each progression or consists of not more than one element. Let's intersect first progression with each other progression. If any of these intersections are empty then total intersection is empty. If some of these intersection consist of one element, then we could check only this element. Otherwise one could intersect arithmetic progressions of first progression indexes and take minimal element of this intersection. The remaining question is how intersect two geometric progression? Let's factorise all numbers in these two progressions and find set of appropriate indexes for every prime factor in both progressions. These progressions one need intersect both by values and by indexes.

Problem author: zeliboba.

Problem developers: zeliboba, yarrr, gchebanov.

Solution code: 12873480.

Привет, codeforces!

Может ли кто-нибудь объяснить, почему в этой задаче заходит такое решение? При обработке запросов там используется обычный merge, который не создаёт новые вершины.

И да, если это кому-то поможет мне помочь, то вот ссылка на обсуждение этой задачи в топике контеста.

Div2-A

Заводим массив used на 100 элементов и заполняем его таким образом: used[i]  =  1, если хотя бы один из однокашников Алексея претендует на часть (i,  i  +  1). Далее проходимся циклом от l₁ до r₁  -  1 и находим количество тех i, для которых used[i]  =  0. Это и будет ответом.

Эту задачу можно решать и за O(nlogn), используя сортировку событий или просто сортировку и линейное решение далее. Такое решение будет находить требуемую величину сразу для всех отрезков.

Div2-B

Посчитаем, сколько раз по L мы можем взять, не превысив N. Это количество равно .

Тогда, если R·K  ≥  N, будем увеличивать какое-то из K чисел на 1, в какой-то момент у нас получится в сумме N, так в итоге будет больше. Значит ответ — YES.

В обратном случае, если мы возьмем не больше K чисел, то их сумма меньше N. Если взять больше K чисел, то сумма будет больше N. Значит ответ — NO.

Сложность ответа на 1 запрос: O(1).

Div1-A/Div2-C

Разложим все данные n чисел на простые множители. Теперь нам нужно решить задачу отдельно по каждому простому, а потом перемножить ответы для различных простых. Количество способов разбить p^k, где p — простое, на n множителей равно C(k + n - 1,  n - 1) (Это можно получить методом шаров и перегородок, подробнее здесь, выбрать combinatorics). Таким образом, получаем решение за .

Div1-B/Div2-D

Пусть для начала n  +  1  =  p — простое. Докажем по индукции, что в этом случае ответ — . При p  =  3 — очевидно. Пусть это равенство доказано для p, а q — следующее простое. Тогда ответ для q — это ответ для p плюс q  -  p одинаковых слагаемых вида , то есть , что и требовалось доказать.

Далее, воспользовавшись тем, что между любыми соседними простыми числами, не превосходящими 10⁹, разница не более нескольких сотен, находим ответ, как ответ для наибольшего (явно проверяем числа на простоту за корень) не превосходящего простого плюс . Отсюда же замечаем, что в ответе знаменатель это 2pq (или его делитель), что влазит в int64.

Div1-C/Div2-E

Запишем все вершины в порядке обхода dfs'а, тогда потомки одной вершины образуют подотрезок. Запомним также для каждой вершины расстояние от нее до корня level[v].

Заведем два дерева отрезков (ДО). При запросе на изменения в первом ДО добавим на отрезке, соответствующем потомкам вершины v, x  +  level[v]·k, а во втором ДО на том же отрезке добавим k.

Тогда, если обозначим первое ДО как st1, второе ДО как st2, то при запросе второго типа в вершине v нужно вывести st1.get(v)  -  st2.get(v)  *  level[v].

Сложность: O(qlogn)

Вместо дерева отрезков можно использовать другие структуры данных, поддерживающие добавление на отрезке и запрос в одном элементе. Также в комментариях приведен способ несколько другой реализации: http://mirror.codeforces.com/blog/entry/10961#comment-162286

Также существует решение с Heavy-Light декомпозицией.

Div1-D

Заметим полезный факт: если взять все перестановки длины k, то сумма количеств инверсий в них будет равна . Доказывается он очень просто: если в перестановке p для каждого i заменим p_i на k  +  1  -  p_i, то сумма количеств инверсий p и новой перестановки будет равна , и при этом наше преобразование является биекцией.

Далее будем считать, что все перестановки на числах от 0 до n  -  1, а не от 1 до n, как в условии. Ясно, что в этом нет никакой разницы.

Пойдем по перестановке с начала. Какие перестановки бывают меньше данной?

• Те, у которых первое число меньше, чем p₀. Пусть первое число a  <  p₀, тогда в каждой такой перестановке a инверсий вида (первый элемент, еще какой-то элемент). То есть всего во всех перестановках с первым числом a их a·(n  -  1)!. Кроме того, есть инверсии среди элементов, не содержащих первый. Их суммарно sumAll[n  -  1]. Тогда суммарно по всем a получаем инверсий: .
• Перестановки, которые начинаются на p₀: Во-первых, нужно учесть кол-во инверсий, начинающихся в начале. Их cnt·p₀, где cnt — количество перестановок, начинающихся на p₀ и не больших данной. Во-вторых, нужно учесть инверсии "не в начале". Но это такая же задача! Единственное исключение — меньше числа p₁ может быть доступно не p₁ чисел, а меньше на 1, если p₁  >  p₀. Отсюда получаем решение: итерируемся с начала, запоминаем в дереве Фенвика числа, которые уже использованы, далее решаем такую же задачу, но считаем что первое число это p_i - (кол-во уже использованных чисел, меньших чем p_i).

Осталось посчитать количество перестановок, не больших чем суффикс данной и начинающихся также. Это можно легко пересчитывать, если двигаться не вперед, а назад. В таком случае нужно делать то же самое, но минимальное число считать равным количеству уже использованных чисел, меньше данного.

Div1-E

Опишем алгоритм, а потом поймем, почему он делает то, что нужно.

Заведем для каждого простого числа список полуинтервалов. Изначально для каждого простого p_i, имеющегося в инпуте, положим туда [0;a_i). У всех остальных простых оставим список пустым.

Далее, будем итерироваться по всем простым в порядке убывания. Пусть текущее простое p. Если в его списке есть полуинтервал вида [x;y), $x < k, y > k$, разделим его на 2 полуинтервала [x;k) и [k;y).

Далее для каждого полуинтервала [x;y), x  ≥  k (на самом деле, x  >  k не бывает) добавим к ответу для p величину y  -  x, а для полуинтервалов y  ≤  k добавим к списку каждого из простых делителей числа p  -  1 полуинтервал [x  +  1,  y  +  1). В случае, если p  -  1 делится на больше чем первую степень какого-то простого, нужно добавить такой отрезок несколько раз.

После этого нужно провести операцию "объединения со смещением" для всех простых, у которых изменился список. Если в одном списке существуют 2 полуинтервала [x,  y), [z,  t) при y  ≥  z  >  x, то их нужно заменить на 1 полуинтервал [x,  y  +  t  -  z) (т.е добавить t  -  z к концу первого из них). Далее переходим к следующему (меньшему) p.

Почему это работает? Вспомним сперва, что происходит с числом n при одной итерации взятия φ. Для любого p, которое входит хотя бы 1 раз в разложение числа n, n делится на p и умножается на p  -  1 (или, что тоже самое, на все простые числа p  -  1 в соответсвующих степенях).

Теперь поймем, что полуинтервалы, которые мы поддерживали для чисел — это то, после каких по счету итераций число содержало в себе данный простой множитель. На большие простые меньшие никак не влияют, поэтому их можно рассматривать раньше. Если после i-ой итерации число содержало простой множитель p, то после i  +  1-й оно будет содержать простые делители p  -  1, поэтому мы именно таким образом передаем отрезки. Итерация с номером k — последняя, поэтому полуинтервал [k,  x) означает, что после k-ой итерации останется степень x  -  k данного простого. Отсюда понятно, почему нужно объединять отрезки со смещением, как описано выше.

Почему это работает быстро?

Потому что мы предподсчитали решетом за линию минимальный делитель каждого числа и раскладываем число на простые за кол-во простых в нем. (На самом деле это делать не обязательно)

Потому что для каждого простого отрезков одновременно, очевидно, не более чем log(MAXP) =  20, ибо для каждого [a,  b) выполняется a  ≤  log(MAXP)  +  1. Если чуть подумать, то их не более чем половина от этого, ибо 2 отрезка не начинаются в подряд идущих числах. Экспериментально, их не более 6.

Несколько другой подход к этой задаче описан в комментариях: http://mirror.codeforces.com/blog/entry/10961#comment-162236

Авторы не уверены, что в разборе все решения написаны понятно, поэтому любые вопросы по нему приветствуются!

Пост был восстановлен из кэша google, формулы были оформлены заново, поэтому, если видите ошибку в них, пожалуйста, пишите мне в личку.

Прежде чем опубликовать разбор задач сегодняшнего раунда, приношу извинения администрации и участникам за свою глупую ошибку, допущенную по криворукости и неопытности.
Несмотря на то что раунд откровенно не удался, мы, авторы, рады, что многим участникам задачи понравились. Вот, собственно, решения:

A — Вася и автобусы

Во-первых, если n = 0, то ни одного ребенка по условию нельзя провезти. Значит, если при этом m = 0, от ответ (0, 0), иначе ответ Impossible.
Теперь n > 0. Если m = 0, то ответ, очевидно, (n, n). Иначе, чем больше родителей везет с собой по ребенку, тем меньше плата за проезд. Поэтому максимальная плата будет тогда, когда всех детей везет один родитель — получаем ответ n + m - 1. Если n <  = m, то все n родителей везут детей, и ровно n детей не платят за проезд. Если же n > m, то все m детей распределяются по родителям и не платят за проезд. В обоих случаях получаем минимальный ответ max(n, m).

B — Окружение

Найдем минимальное расстояние между окружностями L. Тогда ответ к задаче равен L / 2.
- Пусть окружности лежат вне друг друга. Покажем, что L = d - R - r. Во-первых, ясно, что он достигается. Проведем отрезок соединяющий центры. Его часть, лежащая между точками пересечения с окружностями как раз имеет такую длину.

Докажем, что меньшее расстояние недостижимо, построим отрезок между двумя окружностями. Тогда R + r + L >  = d, откуда L >  = d - R - r, чтд.

• Для окружностей, лежащих внутри друг друга аналогичными рассуждениями получаем L = R - d - r, где R — радиус наружной окружности, r — внутренней.
• Для пересекающихся окружностей ответ 0.

C — STL

Пусть нам дан массив строк (s₁, s₂, ...s_n), где s_i  = pair либо int.
Рассмотрим числа bal_i = разность количества pair и int на отрезке массива от 1 до i. Тогда утверждается, что восстановить тип по данному массиву строк можно, причем однозначно  <  =  >  bal_i >  = 0 при 1 <  = i < n и bal_n =  - 1. Здесь возникает очевидная аналогия с правильными скобочными последовательностями.
Докажем это утверждение по индукции по количеству int в данном массиве. База для n = 1 очевидна. Пусть у нас есть тип pair < type1, type2 > . Тогда bal_n = 1 +  bal_ntype1+bal_ntype2  =  - 1. Также можем получить, что bal_i >  = 0 для 1 <  = i < n.
Пусть теперь у нас есть массив строк s, и в нем выполняется данное утверждение. Тогда первый элемент в нем — pair. Возьмем наименьшее i, что bal_i = 0 — оно существует по соображениям дискретной непрерывности (и не равно n, ибо bal_n =  - 1) — в этой позиции должен заканчиваться type1. Тогда на отрезке [2, i] (для него несложно проверить предположение индукции) можно расставить знаки препинания, чтобы получился тип. Аналогичное верно и для отрезка [i + 1, n]. Значит, и из всего отрезка [1, n] можно составить тип, причем тоже единственным образом.
Теперь, если мы получили, что из данного массива строк можно составить тип, заведем функцию gettype(i), которая будет строить тип, начинающийся в s_i, и возвращать индекс, следующий после того, в котором она завершила построение. Как она будет работать? Пусть сейчас запущена gettype(i). Если s_i = pair, выведем int и вернем i + 1. Иначе выведем "pair < ", запустим gettype(i + 1) — пусть он вернул нам j. Выведем ", " и запустим gettype(j), он вернул нам k, выведем " > " и вернем k. Итого, запустив gettype(0), мы построим и выведем восстановленный тип.
Можно обойтись без предварительной проверки, можно ли составить тип из данного массива. Для этого можно запустить функцию gettype и, если в ходе построения типа получаются противоречия, выводить "Error occurred".
Асимптотическая сложность решения — O(количества данных строк).

D — Несекретный шифр

Решение riadwaw: Воспользуемся методом двух указателей. Будем поддерживать для каждого элемента, сколько раз он встречается на текущем отрезке [l, r]. При фиксированном l будем увеличивать r, если элемент a[r] встречается k раз, то этот отрезок и все отрезки вида [l, t], t > r нужно добавить в ответ и увеличить l. Чтобы поддерживать кол-во элементов нужно либо сжать координаты, либо воспользоваться структурой map. Также нужно не забыть, что ответ может достигать n * (n + 1) / 2, т.е не влазить в int.
Решение Kostroma: для начала сожмем координаты, аналогично первому решению. Выпишем для каждого числа список позиций, в которых оно встречается в нашем массиве. Теперь создадим массив b, в b_i будем хранить номер позиции, в которой стоит число a_i, при этом на отрезке [i, b_i] число a_i встречается ровно k раз (если такой позиции нет, то b_i = n + 1). Это несложно сделать одним проходом по нашим спискам. Найдем, сколько отрезков с началом в i удовлетворяют условию задачи — для этого из n нужно вычесть такое минимальное j, что на отрезке [i, j] есть k одинаковых чисел (если такого отрезка нет, то j будем считать равным n + 1). Но такое минимальное j есть . Такие минимумы для всех i можно найти, пройдя массив a один раз с конца. Осталось только просуммировать ответы для всех i от 1 до n.

E — Контратака

У этой задачи много различных решений. Для начала, конечно же, сопоставим городам вершины графа, а дорогам — ребра. Теперь нам нужно найти все компоненты связности в дополнении данного графа.
Решение Gerald: будем хранить set a вершин, которые еще не были посещены, и запустим серию обходов в глубину. Предварительно отсортируем списки смежности каждой вершины — теперь мы можем за O(logn) проверять, есть ли в данном графе произвольное ребро. Пусть мы сейчас находимся в вершине v. Пройдемся по всем элементам a, пусть мы сейчас рассматриваем вершину . Если ребра (v, u) нет в данном графе, то в его дополнении оно есть  =  >  выкинем из a вершину u и добавим ее в очередь. Иначе ничего с вершиной u не делаем. Сколько же раз с вершиной u будет повторена такая операция? Заметим, что вершина u остается в set-е только тогда, когда в данном графе есть ребро (u, v), то есть не больше раз, чем степень вершины u. Значит, асимпотика такого решения равна O(M * logn). Логарифм появляется из бинарного поиска. Это решение без каких бы то ни было оптимизаций тратит чуть больше 2 секунд. Если использовать хеш-таблицы, чтобы узнавать, есть ли в графе определенное ребро, получим асимптотику O(m).
Решение Kostroma: Рассмотрим компоненты дополнения нашего графа. Рассмотрим такой набор компонент дополнения, что их суммарный размер не больше n / 2 и наиболее близок к n / 2 (если такого набора не существует, то в дополнении одна компонента) — пусть в них в сумме c вершин — назовем это множество A. Тогда все ребра между этими с вершинами и остальными n - c вершинами должны быть в данном графе, то есть c·(n - c) <  = m. Отсюда получаем, что . Если n² <  = 4·m, то n <  = 2·10³, тогда c <  = 10³. Иначе при фиксированном m для роста оценки на c нужно уменьшать n — вплоть до того, пока не выполнится n² = 4·m. Тогда . Значит, мы получили, что c <  = 10³.
Рассмотрим теперь любую другую компоненту, пусть в ней b вершин. Тогда c + b >  = n - c, так как c + b > n / 2 в силу выбора множества A, а значит, если c + b < n - c, то можно взять множество компонент, в которое входят все компоненты, кроме A и еще одной компоненты из b вершин — в нем n - c - b вершин, и c < n - c - b, n - c - b <  = n / 2. Значит, если в дополнении больше одной компоненты, то есть компонента размеров не меньше чем n - 2·c (назовем ее большой), значит, во всех остальных компонентах в сумме не больше чем 2·c вершин (причем в A ровно c вершин, значит во всех компонентах, кроме большой, не больше чем c вершин). Тогда не лежать в большой компоненте могут только вершины, степень которых в исходном графе как минимум n - c. Значит, все вершины со степенью  < n - c лежат в одной компоненте, а значит, все вершины со степенью  < n - 1000 тем более лежат в одной компоненте. Множество этих вершин назовем B. Построим новый граф из вершин, не принадлежащих множеству B и еще одной вершины: для каждой пары вершин не из B ребро будет проведено тогда и только тогда, когда в исходном графе его не было. Сопоставим множеству B вершину D, тогда ребра между D и произвольной вершиной v не будет тогда и только тогда, когда в исходном графе v соединена со всеми вершинами из B.
Сколько же в новом графе будет вершин? Количество вершин, степень которых в данном графе как минимум n - 1000, и еще вершина D, то есть не больше чем  + 1 =  . Значит, ребер в графе будет O(m). Теперь запустим серию обходов в глубину или ширину на таком графе и найдем в нем компоненты связности. Теперь нетрудно восстановить компоненты связности дополнения: для этого нужно лишь вспомнить, какие вершины попали в множество B. Получаем решение за O(m), работающее чуть меньше секунды.
Решение riadwaw:
- Посчитаем степень каждой вершины в исходном графе, выберем вершину с минимальной степенью — назовем её V. O(m)
- Заметим, что ее степень не больше средней степени вершин, т.е .
- Заметим, что все вершины, кроме соединенных с V в исходном графе, будут лежать в дополнении в той же компоненте связности, что и V — назовем это множество вершин A.
- Таким образом, можно явно построить дополнение графа, содержащего V и все вершины, соединенные с ней. Всего ребер там , так как m < n·n. Переберем все эти ребра, объединим с помощью СНМ соединенные вершины. Кроме того, объединим с компонентой, содержащей V, вершины, которые в исходном графе соединены не со всеми вершинами из A.
В асимптотике могут вылезать лишние логарифмы из СНМ или сжатия координат. Общая асимптотика от O(m) до O(mlogn), решение работает около секунды.

Здравствуйте!

Уже в который раз принимаюсь за полезное дело: сдать эту задачу с помощью декартова дерева.

Но меня постоянно преследует проблема. В первом семпле моя программа на первом шаге строит дерево из одной вершины и записывает его в root. Но уже при следующем добавлении вершины происходит нечто: root, который для первой вершины был вполне адекватен, вдруг (а именно, при считывании следующего элемента) становится какой-то рандомной хренью.

Я в упор не могу понять, как и почему это происходит. Буду рад любой помощи.

Код

P.S. Почему-то при наборе поста русские буквы отображаются кракозябрами. В предпросмотре все ок

UPD сдал, вот итоговый код, если кому интересно

Сегодня в 19:00 МСК

Странно, что никто еще не написал (С) AlexErofeev

С недавнего времени (пару недель) стал замечать баг: при переходе с одной страницы сайта на другую часто меняется язык с русского на английский.