Microsoft Q# Coding Contest - Summer 2018

http://codeforces.com/contest/1002

I had never study quantum computing. I acquired all the knowledge of quantum computing from only a official tutorial. I mean I am not an expert, so this article is unreliable.

Write a quantum program | Microsoft Docs

Official editorials are here:
https://assets.codeforces.com/rounds/997-998/main-contest-editorial.pdf

C1

If you don't do anything, about 750 cases will pass. So you only have to modify just a little bit. All you have to do is to increase the probability of appearing 1. It isn't difficult to devise such a rotation.

  operation Solve(q: Qubit): Int {
    body {
      Ry(0.4, q);
      if M(q) == Zero {
        return 0;
      } else {
        return 1;
      }
    }
  }

C2

The key observation is if you observe One then you can answer correctly, the given state is the plus state. For answering not only plus state but also zero state, we apply H to the given state with probability 50%. By doing so, you can distinguish states with probability 25%. To make a binary random variable, a quantum will be helpful.

  operation Solve(q: Qubit): Int {
    body {
      mutable res = -1;
      using (qs = Qubit[1]) {
        H(qs[0]);
        if M(qs[0]) == Zero {
          if M(q) == One {
            set res = 1;
          }
        } else {
          H(q);
          if M(q) == One {
            set res = 0;
          }
        }
        ResetAll(qs);
      }
      return res;
    }
  }

D1

The problem is to find the inner product of x and b. I think CNOT(x, y) corresponds to the classical xor gate, y ^= x.

  operation Solve(x: Qubit[], y: Qubit, b: Int[]): () {
    body {
      for (i in 0 .. Length(x) - 1) {
        if b[i] == 1 {
          CNOT(x[i], y);
        }
      }
    }
  }

D3

This problem is to make the oracle state representing (x ∧ y) ∨ (x ∧ z) ∨ (y ∧ z) ≡ (x ∧ y) ⊕ (x ∧ z) ⊕ (y ∧ z). I think CCNOT(x, y, z) corresponds to doing z ^= x&y classically.

  operation Solve(x: Qubit[], y: Qubit): () {
    body {
      CCNOT(x[0], x[1], y);
      CCNOT(x[0], x[2], y);
      CCNOT(x[1], x[2], y);
    }
  }

E1

This algorithm is well-known and is written in a lecture note listed in a certain article on Codeforces. I think its explanation is a little complicated, so I explain it in my own way.
Firstly, transform x such that x takes the all state with equal probability. To implement, Hadamard gates will help you. If x takes only single state, it is same as classical computing. It's meaningless, isn't it? Ok, assume that x takes all states and y takes only 0 state. We denote Uf[b] as Uf with b. In this case, states will change like the following.

For avoiding complicated notations, we omit the brackets of ket-notation and their coefficients.
The first two qubits correspond to x[0] and x[1], and the third qubit corresponds to y.
For example, if b=10, then Uf(010) = 010 because 10*01=0, and Uf( 100 ) = 101 because 10*10=1.
Note that the third qubit represents the value of the given function if the initial y is the 0 state. 
Uf is a linear function, so we can calculate the results easily by the superposition principle.

Uf[00]( 000 + 010 + 100 + 110 ) = 000 + 010 + 100 + 110
Uf[01]( 000 + 010 + 100 + 110 ) = 000 + 011 + 100 + 111
Uf[10]( 000 + 010 + 100 + 110 ) = 000 + 010 + 101 + 111
Uf[11]( 000 + 010 + 100 + 110 ) = 000 + 011 + 101 + 110

So far, we fix y to the zero state. But this strategy seem to not work (I think). For that reason, you had better fix y to the minus state (clearly, the plus state is useless).

Uf[00]( 000 - 001 + 010 - 011 + 100 - 101 + 110 - 111 ) = 
Uf[01]( 000 - 001 + 010 - 011 + 100 - 101 + 110 - 111 ) = 
Uf[10]( 000 - 001 + 010 - 011 + 100 - 101 + 110 - 111 ) = 
Uf[11]( 000 - 001 + 010 - 011 + 100 - 101 + 110 - 111 ) = 

000 - 001 + 010 - 011 + 100 - 101 + 110 - 111
000 - 001 - 010 + 011 + 100 - 101 - 110 + 111
000 - 001 + 010 - 011 - 100 + 101 - 110 + 111
000 - 001 - 010 + 011 - 100 + 101 + 110 - 111

We can factor them.
= 0(00 - 01 + 10 - 11) + 1(00 - 01 + 10 - 11) = (0+1)(00 - 01 + 10 - 11)
= 0(00 - 01 - 10 + 11) + 1(00 - 01 - 10 + 11) = (0+1)(00 - 01 - 10 + 11)
= 0(00 - 01 + 10 - 11) - 1(00 - 01 + 10 - 11) = (0-1)(00 - 01 + 10 - 11)
= 0(00 - 01 - 10 + 11) - 1(00 - 01 - 10 + 11) = (0-1)(00 - 01 - 10 + 11)

Apply H to the first qubit
= 0 (00 - 01 + 10 - 11)
= 0 (00 - 01 - 10 + 11)
= 1 (00 - 01 + 10 - 11)
= 1 (00 - 01 - 10 + 11)

Forget the first qubit for simplicity and then factor the remaining parts.
= 0(0-1) + 1(0-1)
= 0(0-1) - 1(0-1)
= 0(0-1) + 1(0-1)
= 0(0-1) - 1(0-1)

Apply H to the second qubit
= 0(0-1)
= 1(0-1)
= 0(0-1)
= 1(0-1)

Recall the first qubit
= 00(0-1)
= 01(0-1)
= 10(0-1)
= 11(0-1)

Qubit 1 and qubit 2 don't have uncertainties, so you can distinguish them definitely.

  operation Solve(N: Int, Uf: ((Qubit[], Qubit) => ())): Int[] {
    body {
      mutable res = new Int[N];
      using (qs = Qubit[N + 1]) {
        let x = qs[0 .. N - 1];
        let y = qs[N];
        X(y);
        H(y);
        for (i in 0 .. N - 1) {
          H(x[i]);
        }
        Uf(x, y);
        for (i in 0 .. N - 1) {
          H(x[i]);
        }
        for (i in 0 .. N - 1) {
          if M(x[i]) == One {
            set res[i] = 1;
          }
        }
        ResetAll(qs);
      }
      return res;
    }
  }

E2

Note that b is not unique generally. Let's try computing f(0000), f(0001), f(0010), ... with some fixed b. You would notice that the function value takes only two types. Actually, this problem can be solved by classical computer with only one query. So you needn't devise any quantum algorithm.

  operation Solve(N: Int, Uf: ((Qubit[], Qubit) => ())): Int[] {
    body {
      mutable res = new Int[N];
      using (qs = Qubit[N + 1]) {
        let x = qs[0 .. N - 1];
        let y = qs[N];
        Uf(x, y);
        if (M(y) == Zero) == (N % 2 == 1) {
          set res[0] = 1;
        }
        ResetAll(qs);
      }
      return res;
    }
  }

A4

This problem is the most difficult for me. My strategy is to make the solution of size n from the size n/2. First, you make the following state. The left factor can be obtained by solving the half size problem, and the right factor is GHZ state. The coefficients are annoying, so we omit them.

(1000 + 0100 + 0010 + 0001)(0000 + 1111)

This expression represents the superposition of the below eight states:

10000000
01000000
00100000
00010000
10001111
01001111
00101111
00011111

The aim is to transform the from 5th to 8th states into 00001000, 00000100, 00000010, 000000001 respectively. To achieve this, apply some CCNOT operations described below. It leads following changes.

You do the following operations where k += i * j means the same as CCNOT(qs[i], qs[j], qs[k])
5+=0*4, 6+=0*4, 7+=0*4, 6+=1*5, 7+=1*5, 7+=2*6

10000000
01000000
00100000
00010000
10001000
01001100
00101110
00011111

After that, apply some CNOT. Then the states will be the following.

You do the following operations where j+=i means the same as CNOT(qs[i], qs[j]):
6+=7, 5+=7, 4+=7, 5+=6, 4+=6, 4+=5

10000000
01000000
00100000
00010000
10001000
01000100
00100010
00010001

Finally, cancel 1s appeared in the first half qubits by CNOT(qs[4],qs[0]), CNOT(qs[5],qs[1]), CNOT(qs[6],qs[2]), CNOT(qs[7],qs[3]).

10000000
01000000
00100000
00010000
00001000
00000100
00000010
00000001

These are the required results. This algorithm is complete.

  operation Recur(qs: Qubit[]): () {
    body {
      if Length(qs) == 1 {
        X(qs[0]);
        return ();
      }
      let n = Length(qs) / 2;
      Recur(qs[0 .. n - 1]);
      H(qs[n]);
      for (i in n + 1 .. n * 2 - 1) {
        CNOT(qs[n], qs[i]);
      }
      for (i in n .. n * 2 - 1) {
        for (j in i + 1 .. n * 2 - 1) {
          CCNOT(qs[i - n], qs[i], qs[j]);
        }
      }
      for (i in n * 2 - 1 .. -1 .. n + 1) {
        for (j in i - 1 .. -1 .. n) {
          CNOT(qs[i], qs[j]);
        }
      }
      for (i in n .. n * 2 - 1) {
        CNOT(qs[i], qs[i - n]);
      }
    }
  }

  operation Solve(qs: Qubit[]): () {
    body {
      Recur(qs);
    }
  }

The editorial solution is sophisticated but requires advanced knowledge. As most of solutions try to solve each case N=1,2,4,8,16, brute force approach might be practical.

GCJ 2018 round2

A 問題

i 番目と i+1 番目の間をいくつのボールが通過するかを計算できると、それをそのまま。

B 問題

丁度にする必要はなくて、適当に辻褄をあわせることができる、というのが重要な考察。
(i,j) を使う、というのを n×n グリッドの (i,j) の位置に駒を置くと言い換える。駒がおいてある場所の総和が R, B 以下なら良いわけだけど、もし駒の上が空になっていたら上に動かしたほうが得である。
つまり駒の置いてある形はヤング図形のようになっている。また、ヤング図形の幅、高さは 40 程度である(これは 1+2+3+...+40 > 500 から言える)。
以上を踏まえると DP で解ける。

C 問題

値ごとにバラして考えて、変えない場所を最大化することを考える。これは単純な最大二部マッチングに帰着される。

D 問題

単なる場合分けだと思うけど通らなかった…。

April Challenge 2018

Chef 側の解説がまだ出てないので、それ読んで思うものがあったら更新します。

CHEFAT:
この制約なら SIMD O(n^2) 通る。そうは言っても 2 ケースほど TLE になってしまったので、平方分割+遅延評価で平均的に速くなるようにした。
多くの提出は $\log(1-x)=-x-x^2/2-x^3/3-...-x^{100}/100$ で近似してる。
最後に exp とったときの誤差は大丈夫なのかなと思ったけど $e^{x+\epsilon} - e^x \approx \epsilon e^x$ なので大丈夫そう。

SSPLD:
固有多項式を埋め込む(そんなに次数は大きくない)。具体値を埋め込むとコード長制限に引っかかるため実行時に計算。多項式乗算・剰余は FFT で高速にやらないと厳しい。多くの提出は hadamard transform を使ってるように見える。確かにできそう。

11 変数多項式 f(x,y0,...,y9) を FFT する感じ?f(x,y0,...,y9) にある多項式を掛けることで遷移を表現できる(下の桁から値を決めていくわけだが、遷移関数は周期的、周期は 10^k mod s に依存)。そして S×2×2×…×2 の FFT をしておけば係数の積から値の積に変換できて、解ける。(S に関して言うと 2 冪じゃないから FFT じゃないけど(高速ではない))→よく考えたらNTTなのでSでできない。いや体拡大でできるかもしれないけど、そうではないんだろう。

CodeChef March Challenge 2018

PSHTRG

Q=1 で考えてみよう。これは,数列をソートして最大 3 つを見る,それで駄目なら次の 3 つを見るというのを繰り返すことで求められる。この繰り返しが O(log max a) 回しか起きないことに気がつくと,50th max 程度まで保持するセグメント木があれば解けることがわかる。最悪ケースはフィボナッチ数列だろう。

実装:https://gist.github.com/pekempey/829c0d930e2a992a2041e8f363d2f8be

CHEFKNN

最終的な結果が K 色を含むようなものの総数は,第一種スターリング数によって S(N+1, N+1-K) と表せる。自分はこの事実に実験で気がついたが,おそらくは組合せ論的に導けるものなのだろう。この事実に気がつければ,やるべきことは第一種スターリング数の計算の高速化のみとなる。第一種スターリング数は rising factorial の展開係数として現れるので rising factorial を高速に展開すればよい。分割統治でやると O(n log2 n) だが,少し工夫すると O(n log n) になる。多分 100pts は O(n log n) のためなんだろうけど,変な O(n log2 n) が通ってるように見えるな。

実装:https://gist.github.com/pekempey/eeadc0c5306db890a8d9a742d2f433fd

ちなみに自分のコードは T=5, N=106, K=106 だと 5 sec 以上かかる。T=4 ですら 5 sec 以上掛かる。明らかに最悪ケースが入っていない。展開時の係数を求める際に,具体値を求めて係数表現に戻すという方法もあるらしい。これなら FFT 1 回でいいし速そう。

CUTTREE

与えられたスコアは,頂点 u と頂点 v が連結ならば 1 増えるようなスコアと言い換えられる。これに気がつけば部分点がとれる。満点解法はこれを高速化するだけである。高速化するには距離が等しい頂点対をまとめて計算すればよい。距離 d の頂点対の総数を計算するには重心分解と畳み込みが使える。これを求め終わった後に,もう一度畳み込みを行って最終的な答えを得る。しかしこの畳み込みは任意 mod のものである。任意 mod の畳み込みは様々な方法があって,Karatsuba 法や NTT 9 回,FFT 4 回などがある。

実装:https://gist.github.com/pekempey/4782989f6417ad6de97a6864ca33e39f

ARC091 F Strange Nim

https://arc091.contest.atcoder.jp/tasks/arc091_d

K を固定して Grundy 数 g(n) を考える。実験すると g(Kn)=n であることに気づける。g(Kn)=n ということは,その直前 n 個を見ると 0..n-1 の順列になっている。これに気がつくと漸化式が見える。


実験から漸化式まで導く方法が解説放送でされているが,自分は気づかなかった。高速化パートもそれはそれで難しいんだけど,時間を掛ければわかるタイプ。

図:https://gist.github.com/pekempey/2893024239ec6aa14e83805fa890364b