I found an interesting solution. Most of the solutions use a linked list, but it is based on another property. The operation LxR->RxL is similar to LR->RL. LR->RL is well-known as rotation (C++ standard library contains it). Then, consider the following problem.

Given a permutation with N elements and Q queries. Each query is in the following form.

Given k, rotate k elements. That is, change a[0],...,a[k-1],a[k],...,a[n-1] to a[k],...,a[n-1],a[0],...,a[k-1].

Please print the permutation after all queries are performed. This problem is really easy because just trace the beginning position. Actually, the original problem can also be solved by a similar technique.
That is why LxR->RxL can be treated as a rotation. Appending x to the end, it becomes LxRx -> RxLx.

#include <stdio.h>

int a[100001];
int pos[100000];

int main() {
  int n, q;
  scanf("%d %d", &n, &q);
  for (int i = 0; i < n; i++) {
    scanf("%d", &a[i]);
    a[i]--;
    pos[a[i]] = i;
  }
  int k = n;
  while (q--) {
    int b;
    scanf("%d", &b);
    b--;
    a[k] = b;
    int tmp = pos[b];
    pos[b] = k;
    k = tmp;
  }
  for (int i = 0; i < n; i++) {
    if (i) putchar(' ');
    printf("%d", a[(i + k + 1) % (n + 1)] + 1);
  }
  putchar('\n');
}

2018-09-18

Knapsack and Queries

https://jag2018summer-day2.contest.atcoder.jp/tasks/jag2018summer_day2_d

It's very interesting. The key property is a queue can be simulated by two stacks. Each push query, you can compute new values of dp in O(mod). Pop query is trivial, just ignoring the last operation. Besides, push queries is at most O(Q). So entire performance requires O(Q*mod), it is amortized. It is difficult to devise this algorithm without any suggestion.

https://ideone.com/DIMvq1

I consider my solution is unsafe because the size of queue for sliding minimum is a little short (it must be 1000 but 500).

As I remember, a replacement a queue with two stacks are described in Introduction to Algorithms and Purely Functional Data Structures. I learned at the lecture of algorithms (Maybe it was an exercise or in a short exam).

If you have two stacks, you can simulate queue operations as described below:

enqueue 1: ([], []) -> ([1], [])
enqueue 2: ([1], []) -> ([1,2], [])
enqueue 3: ([1,2], []) -> ([1,2,3], [])
dequeue: ([1,2,3], []) -> ([], [3,2,1]) -> ([], [3,2])
enqueue 4: ([], [3,2]) -> ([4], [3,2])
enqueue 5: ([4], [3,2]) -> ([4,5], [3,2])
dequeue: ([4,5], [3,2]) -> ([4,5],[3])
dequeue: ([4,5], [3]) -> ([4,5],[])
dequeue: ([4,5],[]) -> ([], [5,4]) -> ([], [5])
dequeue: ([], [5]) -> ([], [])

Specifically, if the second stack has at least one element, pop query returns the last element of the second stack and remove it. Otherwise, pop the first stack repeatedly until it becomes empty and each popped element is pushed to the second stack. You can realized that this operation will reverse the order of its elements. Its time complexity is O(n), n is the number of operations. This proof is easy for you.

2018-09-17

September Challenge 2018

Official editorial: https://discuss.codechef.com/tags/sept18/

BSHUFFLE

I don't know why this is correct.
https://ideone.com/p8tq79

TABGAME

View the win-loss table diagonally and alternately. You can realize that the values almost unchange except for the both ends. So you can compute the all of values sequentially and compute the answer at an appropriate time.
https://ideone.com/uXVcpK

ANDSQR

Let's list the continuous subsequences such that the right end is R. Actually, the number of distinct values is at most 30. That is why for each adjacent values x and y, x is a proper subset of y, so at least one bit is lost.
https://ideone.com/H1eQ6R

PHOTOCOM

This is an implementation problem (I supposed).
https://ideone.com/bO9TAR

STCFOTT

My simple O(NQ) dp solution pass the all test cases. It is no wonder. 5 seconds should be enough. The key property is similar to Ant (introduced in Antbook). By this property, each ants is not necessary to be distinguished. After that, only have to do is to compute the expectation at each positions. It is achieved by standard Markov-Chain like DP.
https://ideone.com/HnoH73

FCTR

I have seen a similar problem. So I didn't feel it difficult. My solution is a little dirty. Given information about the order of the group (it's equivalent to Euler's phi), you can use Euler's theorem. It states that any element of the group raised to the power of the order of group is always equal to 1. Considering analogy of Miller-Rabin method, you can find x such that x^2=1 (mod N) and x is neither 1 or -1 with high probability, but skip the details here. If x is neither 1 nor -1, x-1 is a nontrivial divisor, so this problem is reduced to N/(x-1). Repeating this procedure, finally you can factor N. You might notice that if N is not square-free, this algorithm doesn't work properly, but this can be resolved by reducing to N to N/gcd(N,phi(N)).
https://ideone.com/YVWRnq

CHEFLST

My solution is perfectly wrong but luckily passed all test cases.
https://ideone.com/81Pi48

CHEFZERO

Is there any approximation algorithm?

2018-07-11

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:

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]).

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.

2018-05-20

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 問題

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

pekempey's blog

Pivots