Pivots

https://onlinejudge.u-aizu.ac.jp/beta/room.html#ACPC2018Day3/problems/B

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

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.

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?