ABC127 F - Absolute Minima

https://atcoder.jp/contests/abc127/tasks/abc127_f

Maintain the first smallest half of a[i] and the second smallest half of a[i], call them L and R respectively. Then, the answer is sum(R)-sum(L) if L and R have the same number of elements.

To maintain them efficiently, we prepare two heaps, the one is a max-heap called L and the other is a min-heap called R. When given the input a[i] and b[i], we insert a[i] into both heaps, that is, do L.push(a[i]) and R.push(a[i]). After this operation, it might be L.top() > R.top(). If so, we swap them. After this, L.top() <= R.top() always holds. Note that L.top() <= R.top() implies L has the first smallest half of a[i] and R is also the same.

Since a[i] is counted doubly, the answer is a little different from the described above. It becomes (sum(R) - sum(L))/2. When L.top() > R.top(), two elements moves between L and R mutually. At this time, the (sum(R)-sum(L))/2 increases by x-y, where x and y are L.top() and R.top() respectively.

The following code is based on the explanation above. Clearly, we can use a balanced binary search tree or a binary indexed tree for solving this problem. BST and BIT appear in various situations. So it might be easier than the heap-based solution for experienced competitors.

By the way, as far as I know, two heap technique is written in "Cracking the Coding Interview." So it might be more well-known than many people think.

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>

using namespace std;

using ll = long long;
template<class T> using minheap = priority_queue<T, vector<T>, greater<T>>;
template<class T> using maxheap = priority_queue<T, vector<T>, less<T>>;

int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  int Q;
  cin >> Q;
  maxheap<ll> L;
  minheap<ll> R;
  ll ans = 0;
  while (Q--) {
    int type;
    cin >> type;
    if (type == 1) {
      ll a, b;
      cin >> a >> b;
      ans += b;
      L.push(a);
      R.push(a);
      if (L.top() > R.top()) {
        ll l = L.top(); L.pop();
        ll r = R.top(); R.pop();
        ans += l - r;
        L.push(r);
        R.push(l);
      }
    } else {
      cout << L.top() << ' ' << ans << '\n';
    }
  }
}

Codeforces #559 (Div. 1) A. The Party and Sweets

https://codeforces.com/contest/1158/problem/A

I didn't know the iterator has operator[] *1. I found this when I read his solution.

#include <vector>
#include <cassert>
using namespace std;
int main() {
  vector<int> a{1,2,3,4,5};
  assert(a.begin()[0] == 1);
  assert(a.begin()[1] == 2);
  assert(a.end()[-1] == 5);
  assert(a.end()[-2] == 4);
  assert(a.rbegin()[0] == 5);
  assert(a.rbegin()[1] == 4);
}

*1:According to http://www.cplusplus.com/reference/iterator/, only random access iterators have this operator. For example, if we need to find the second minimum of a set S, we cannot write S.begin()[1].

いろはちゃんコンテスト Day 1

I - リスのお仕事

Let us consider a graph whose vertices are (vertex ID, The cost used at last). If there exists a vertex having a lot of kinds of costs, it is difficult to update the distance efficiently. To perform efficiently, we prepare N special vertices (1,0),(2,0),...,(N,0) and connect (x,*) -> (x,0) with cost 1 and (x,0) -> (x,*) with cost 0. We can see that Dijkstra on this graph runs in O(N log^2 N), which is fast enough.

J - ヌクレオチド

When N is even, the inversion number is 2x(N/2-x) where x is the number of zeros in the first half. Look at two elements having different values. There are two cases. The first case is that 0 follows 1.

***0***1*** ***1***0***

In this case, the effect of two elements is exactly two. The second case is that 1 follows 0.

***1***0*** ***0***1***

Also in this case, the effect of two elements is exactly two. Thus, we can prove the first statement. We want to know the x such that 2x(N/2-x)=K. Since this is a quadratic equation, we can figure out the solutions by the quadratic formula. Once we get the x's, we just sum up C(N/2,x) for all x.

When N is odd, we can find out the answer similarly.

K - ルーレット

We do not have to compute the expectation but compute the sum of all possible patterns. It is not difficult to compute this.

L - をあ ぷろぶれむ

Fix the right end R, then the number of kinds of A[L] or ... or A[R] is at most 60. That is why, by or operation, the number of ones can increase at most 60 times. Let dp[R][X] be the number of intervals such that the right end is R and the bitwise OR of the elements is equal to X. We can compute this efficiently using std::map.

Codeforces Round #551 (Div. 2) F. Serval and Bonus Problem


https://codeforces.com/contest/1153/problem/F

Without loss of generality, we assume \(L=1\). The probability that x is covered by a single interval is \(2x(1-x)\). Let \(f(x)=2x(1-x)\), then the expectation of the length covered by exactly i intervals can be written by

\[ \int_{0}^{1} \binom{N}{i} f(x)^i (1-f(x))^{N-i} dx \]

If we have

\[ \int_{0}^{1} f(x)^i dx \]

the answer can be computed easily. The coefficients of \(f(x)^i\) can be computed by \(f(x)^{i-1}\) in O(N) time. The total time complexity is O(N^2).

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>

using namespace std;

const int MOD = 998244353;

struct mint {
    int n;
    mint(int n_ = 0) : n(n_) {}
};

mint operator+(mint a, mint b) { a.n += b.n; if (a.n >= MOD) a.n -= MOD; return a; }
mint operator-(mint a, mint b) { a.n -= b.n; if (a.n < 0) a.n += MOD; return a; }
mint operator*(mint a, mint b) { return (long long)a.n * b.n % MOD; }
mint &operator+=(mint &a, mint b) { return a = a + b; }
mint &operator-=(mint &a, mint b) { return a = a - b; }
mint &operator*=(mint &a, mint b) { return a = a * b; }

mint modpow(mint a, int b) {
  mint res = 1;
  while (b > 0) {
    if (b & 1) res *= a;
    a *= a;
    b >>= 1;
  }
  return res;
}

mint modinv(mint a) {
  return modpow(a, MOD - 2);
}

mint F[100001] = {1, 1};
mint R[100001] = {1, 1};
mint I[100001] = {0, 1};

mint C(int n, int r) {
  if (n < 0 || r < 0 || n < r) return 0;
  return F[n] * R[n - r] * R[r];
}

void init() {
  for (int i = 2; i <= 100000; i++) {
    I[i] = I[MOD % i] * (MOD - MOD / i);
    F[i] = F[i - 1] * i;
    R[i] = R[i - 1] * I[i];
  }
}

mint dp[2020][4040];
mint idp[2020];

int main() {
  init();
  int N, K, L;
  cin >> N >> K >> L;
  // P(x) = 2x(1-x) = -2x^2 + 2x
  dp[0][0] = 1;
  for (int i = 0; i < N; i++) {
    for (int j = 0; j <= 4000; j++) {
      dp[i + 1][j + 2] -= 2 * dp[i][j];
      dp[i + 1][j + 1] += 2 * dp[i][j];
    }
  }
  for (int i = 0; i <= N; i++) {
    for (int j = 0; j <= 4000; j++) {
      idp[i] += I[j + 1] * dp[i][j];
    }
  }
  mint ans = 0;
  for (int i = K; i <= N; i++) {
    // \int_0^1 C(N,i) * P(x)^i * (1-P(x))^{N-i}
    for (int j = 0; j <= N - i; j++) {
      if (j % 2 == 0) {
        ans += C(N,i) * C(N-i,j) * idp[i + j];
      } else {
        ans -= C(N,i) * C(N-i,j) * idp[i + j];
      }
    }
  }
  ans *= L;
  cout << ans.n << endl;
}

GCJ 2019 Round 1A

Pylons

If we properly take some k, (i,j) -> ((i+k)%H,j+1) -> ((i+2k)%H,j+2) -> ... is a path satisfying the given conditions. I don't have any proof, but at least under this constraints, it is correct. In addition, (H,W)=(4,4) doesn't work, so this case is treated as an exception. I couldn't come up with a randomized solution. It is really simple. Good problem.

Golf Gophers

lcm(2,3,5,7,11,13,17) is a little small, so I tried lcm(5,6,7,8,11,13,17). By Chinese remainder theorem, we can figure out the answer uniquely. Even if we don't have the library for solving equations, the answer can be found by trying the all integers from 0 to M.

Alien Rhyme

This is the easiest problem in these. Greediliy pair the strings having the longest common suffix, and do this repeatedly until such a pair doesn't exist. Though N<=1000, we should carefully implement an algorithm. Actually, some quadratic algorithms might be too slow to pass large cases. For avoiding such a trouble, so I wrote O(1000*50*17) time algorithm using std::map. Needless to say, Trie runs more quickly, but it takes a lot of time for implementation.