AGC034 F - RNG and XOR

https://atcoder.jp/contests/agc034/tasks/agc034_f

Let a and b be arrays with 2^n elements. a*b denotes the xor convolution of a and b.

Let x=[x[0], x[1], ... , x[2^n-1]] be the answer and p=[p[0],...,p[2^n-1]] be the probability that i-th element is taken. The following relation holds.

\[ x \ast p = x + [2^{n}-1,-1,\ldots,-1]. \]

Let's consider the reason. The sum of x*p must be x[0]+...+x[2^n-1]. Thus, the first element of the right side must be 2^n-1.
H[x] denotes the hadamard transform of x. We then have

\[ H[x] \circ H[p] = H[x] + H[ [ 2^{n-1}-1,-1,\ldots,-1 ] ] \]

where a∘b denotes the bitwise product of arrays (also known as hadamard product.) Except i=0, we can figure out H[x][i]. For i=0, we cannot determine a value because H[p][0] = 1. Actually, we can assume that H[x][0] is any value. Once we determine H[x], we can obtain x by inverted hadamard transform. If H[x][0] is a wrong value, x[0],...,x[2^n-1] are also wrong. However, we can fix them because the answer is one of [x'[0], ... , x'[2^n-1]]=[x[0]+c, ... , x[2^n-1]+c]. We already know x'[0]=0, so c must be -x[0].

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