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

Hello, codeforces!

On the 18-th of November we held the contest made by our company at the MIPT-2015 ACM ICPC Workshop. The problemsetters of the contest are: zeliboba, gchebanov, Kostroma, riadwaw, yarrr, ValenKof, ArtDitel, Endagorion.

On Sunday, November, 29, at 11 a.m. MSK the unofficial translation of this contest will be held on the Yandex.Contest platform. We invite all of you to participate, being quite sure that everyone will find the problems interesting for them.

P.S. You can read more about the MIPT-2015 ACM ICPC Workshop in the Rubanenko blog.

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.

Div2-A

Create an array used of 100 elements. i-th element for the segment (i, i + 1).

For every student except Alexey set used[i]  =  true for each segment (i,  i  +  1) in the segment of that student. After that for each subsegment (i,  i  +  1) of Alexey's segment add 1 to result if used[i]  =  false.

Div2-B

First of all, calculate how many L's we can bring so that the result will not exceed N. It's .

Now, if R·K  ≥  N we may increase any of K numbers by 1. At some moment sum will be equal to N becase sum of K R's is greater than N. So answer in this case is YES.

If R·K  <  N, we can't get K or less numbers because their sum is less than N. But we can't get more than K numbers too, because their sum is more than N. So answer is NO.

Complexity: O(1) for every query. Overall complexity: O(t).

Div1-A/Div2-C

Let's factorize all n numbers into prime factors. Now we should solve the problem for every prime independently and multiply these answers. The number of ways to split p^k into n multipliers, where p is prime, is equal to C(k  +  n  -  1,  n  -  1) (it can be obtained using the method of stars and bars, you can read about it here, choose 'combinatorics'). So we have a solution that needs time.

Div1-B/Div2-D

First of all, let's consider n  +  1  =  p is prime. Then we can prove by induction that the answer is . Base for p  =  3 is obvious. If this equality holds for p, and q is the next prime, then answer for q is equal to answer for p plus q  -  p equal summands , that is , that's we wanted to prove.

Next using that the distance between two consecutive primes not exceeding 10⁹ does not exceed 300, we can find the answer as a sum of the answer for the maximal prime not exceeding n and several equal summands . We see that the denominator is a divisor of 2pq, which fits in long long.

Div1-C/Div2-E

We can write all vertices in the list in order of dfs, then the descendants of the vertex from a segment of this list. Let's count for every vertex its distance to the root level[v].

Let's create two segment trees st1 and st2. If we are given a query of the first type, in st1 we add x  +  level[v]·k to the segment corresponding to the vertex v, in st2 we add k to the segment corresponding to the vertex v.

If we are given a query of the second type, we write st1.get(v) - st2.get(v) * level[v].

The complexity is O(qlogn).

You can use any other data stucture that allows to add to the segment and to find a value of an arbitrary element.

Also there exists a solution using Heavy-Light decomposition.

Div1-D

Let's prove a useful fact: sum of number of invertions for all permutations of size k is equal to . The prove is simple: let's change in permutation p for every i p_i to k  +  1  -  p_i. Then the sum of number of invertions of the first and the second permutations is , and our conversion of the permutation is a biection.

Now we suppose that we are given a permutation of numbers from 0 to n  -  1.

Let's go at p from left to right. What permutations are less than p?

• Permutations having first number less than p₀. If the first number is a  <  p₀, than in every such permutation there are a inversions of form (first element, some other element). So in all permutations beginning with a there are a·(n  -  1)! inversions of this from. Moreover, there are inversions not including the first element, their sum is sumAll[n  -  1]. Then, counting sum for all a we have inversions.
• Permutations beginning with p₀. At first, we should count the number of inversions, beginning in p₀. There are cnt·p₀ of this form, where cnt is the number of permutations beginning with p₀ and not exceeding p. Then we should count the inversions not beginning in the beginning. But it is the same problem! The only exception is that if p₁  >  p₀, there are p₁  -  1 available numbers less than p₁, but not p₁. So we get a solution: go from left to right, keep already used numbers in Fenwick tree, and then solve the same problem, assuming that the first number is not p_i but p_i - (the number of used numbers less than p_i).

The last we should do is to count the number of permutations not exceeding the suffix of p and beginning the same. It can be precomputed, if we go from right to left. In this case we should do the same as in the first part of solution, but consider that the minimal number is a number of already used numbers less than current.

Div1-E

We will describe an algorithm and then understand why it works.

For every prime we will maintain a list of intervals. At the first moment for every p_i we add in its list interval [0;a_i), other primes have an empty list.

Then we go from big primes to small. Let's consider that current prime is p. If in its list there exists an interval [x;y), $x < k, y > k$, we divide it into two parts [x;k) and [k;y).

Then for every interval [x;y), x  ≥  k (in fact, in this case x  =  k) we add to the answer for p y  -  x. For intervals, where y  ≤  k, we add to list of every prime divisor of p  -  1 invterval [x  +  1,  y  +  1). If p  -  1 has some prime if more than first power, we should add this segment several times.

After that we should conduct a "union with displacement" operation for every prime which list was changed. If in one list there are 2 invervals [x,  y), [z,  t) so that y  ≤  z  >  x, we replace them with one interval [x,  y  +  t  -  z) (so we added t  -  z to the right border of the first interval). Then we go to next (lesser) p.

Why does it works? If we take function φ one time, for every prime p which divides n, n is divided by p and multiplied by p  -  1 (or, the same, by all prime divisors p  -  1 in corresponding powers).

Now we can observe that intervals in lists contains the numbers of iterations, when the number contains the corresponding prime number. Bigger primes do not affect smaller, so we can process them earlier. If after i-th iteration the number contains prime number p, after i  +  1-th iteration it contains prime divisors of p  -  1, and we add segments in accordance with this. The k-th iteration is the last, so the existence of the interval [k,  x) means that after k-th iteration we have (x  -  k)-th power of this prime. From this it is clear why we unite the intervals if that way.

Why does it work fast?

1. Because we precalculated the minimal prime divisor of each number up to MAXPRIME using linear Eratosthenes sieve. (Well, it's not necessary)

2. Because for each prime there's no more than intervals, because for each [a,  b) range . Practically there is no more than 6 segments at once.

Any questions about the editorial are welcome! Especially the English one :)

This post was restored from google cache, and I have edited formula once again. If you notice some mistake, please send be a private message.

A — Vasya and the Bus

Firstly, if n = 0, then children can't be in the bus, so if m = 0 then the answer is (0, 0), otherwise the answer is "Impossible". Now n > 0. If m =  = 0, than it is only one possible variant of passage — the answer is (n, n). Otherwise, more grown-up take some children, less the sum that people pay. So, if only one adult takes all children, than we get maximal sum — n + m - 1. Maximum min(n, m) adults can take the children with them, so the minimal answer is n + m - min(n, m) = max(n, m).

B — Surrounded

Let's find the minimum distance between two circles L. Then the answer to our problem is L / 2.
Now d is the distance between the centers of the circles, R, r — their radiuses. There are 3 possible cases:
- Circles don't intersect. Then L = d - R - r. Firstly, it's reachable: let's consider the segment, connecting the centers of the circles, and take its part, which is out of both circles — its length is exactly d - R - r.

Let's prove that lesser distance is impossible. If the segment connecting two points of distinct circles have length l, than R + l + r >  = d, so l >  = d - R - r.

- If one circle is into another, than analogically the answer is R - d - r, where R is the radius of the bigger circle.
- If the circles intersect, then the answer is 0.

C — STL

In this problem we have an array of strings (s₁, s₂, ...s_n), where s_i  = pair or int.
Let's consider bal_i = the difference between number of "pair" and "int" int the subarray (s₁, s₂, ...s_i).
Than we can prove that the type can be reestablished from the array s  <  =  >  bal_i >  = 0 for 1 <  = i < n and bal_n =  - 1. This can be proved using mathematical induction, the parameter is the number of "int"-s in the array.
And how to find the solution, if we know that is exists? Consider the function gettype(inti), which builds the type beginning in the position i and returns the index, next to the position where it finished building of type. How it works? If s_i =  "int", then the function prints "int" and returns i + 1. Else it prints "pair < ", gettype(i + 1) is launched, let it returns j. Then we print ", " and launch gettype(j) (it returns k), then we print " > " and return k.
We can not to do check if the type can be reestablished from the array in the beginning: launch gettype() and print "Error occurred" if there became some contradiction during the building of type.

D — Non-secret Cypher

First solution: Let's use the method of two pointers. For every number we will know how many times it occurs in the current segment [l, r]. For fixed l we increase r until a[r] occurs in the current segment less than k times. If a[r] occurs int the segment [l, r] k times, we add to the answer all segments [l, t] for all t >  = r and increase l (and do not forget to decrease the number of a[l] in the current segment).
To keep the number of every value in the segment we can use map or compression of the coordinates. Also it's important not to forget that the maximal answer is , which doesn't fit in int.
Second solution: firstly, let's do the compression of the coordinates. For every value X we write the list of the positions i such that a[i] = X. Now using that we fill the array b: b[i] is the minimum index that segment [i, b[i]] contains k numbers equal to a[i] (obviosly, a[b[i]] = a[i]), if this index doesn't exist, then b[i] = n + 1.
Let's find for every index i a minimal index j such that segment [i, j] contsins k equal numbers (if such j doesn't exist, we say that j = n + 1) — then we add to the answer n + 1 - j. This j is equal to . All that minimums can be found in a single pass through a from its end. Then we can sum the answers for all indexes 1 <  = i <  = n.
The complexity of these solutions is O(nlogn).

E — Counter Attack

This problem has several different solutions. Anyway, we should consider towns as the vertices of the graph, roads as its edges. Now we are to find the connected components of the complementary graph (CG) of the given graph. Let's take the vertex A with the minimal degree c: . We call the set of the vertices who are connected with A — B, that are not connected — D . All vertices which don't connect with A will be in the same connected component of the CG. Let's build the complemented graph to the subgraph including A and set B — there are vertices and  =   =  O(m) edges.
Let's build DSU for the vertices of given graph and merge components which we have found using the new-built graph. All that we should do after it is to consider vertices from B: now we look to the vertex v. We put v in the same component as A if v has edges not to all vertices of D (we do it using DSU too). The complexity of this solution is O(m) or O(mlogn).

Another solution: we keep set a, which contains vertices, which haven't been visited yet. Let's run series of bfs to find the components of CG. If we are working now with the vertex v, pass through a. Consider u is the element of a. If edge (u, v) isn't in the given graph, than u is in the same component of CG as v, so, we can erase it from a and add to queue. Otherwise, we do nothing.
What is the complexity of this solution? To understand that, we must know how many times whe consider fixed vertex u in the set a. u remains int a when we run to them from vertex v  <  =  >  edge (u, v) is in the given graph. So, every vertex u remains in a no more than its degree. So, the complexity of this algorithm is O(mlogn) (log n because of binsearch — we need use it to know, is (u, v) in the graph). If we use HashMap, we'll get O(m).