Permutation Game
Contest: Lyft Level 5 Challenge 2018 - Elimination Round
Difficulty rating: 1600
Tags: brute force, dp, games

After a long day, Alice and Bob decided to play a little game. The game board consists of $$$n$$$ cells in a straight line, numbered from $$$1$$$ to $$$n$$$, where each cell contains a number $$$a_i$$$ between $$$1$$$ and $$$n$$$. Furthermore, no two cells contain the same number.

A token is placed in one of the cells. They take alternating turns of moving the token around the board, with Alice moving first. The current player can move from cell $$$i$$$ to cell $$$j$$$ only if the following two conditions are satisfied:

- the number in the new cell $$$j$$$ must be strictly larger than the number in the old cell $$$i$$$ (i.e. $$$a_j > a_i$$$), and
- the distance that the token travels during this turn must be a multiple of the number in the old cell (i.e. $$$|i-j|\bmod a_i = 0$$$).

Whoever is unable to make a move, loses. For each possible starting position, determine who wins if they both play optimally. It can be shown that the game is always finite, i.e. there always is a winning strategy for one of the players.

Input format:
The first line contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$) — the number of numbers.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$). Furthermore, there are no pair of indices $$$i \neq j$$$ such that $$$a_i = a_j$$$.

Output format:
Print $$$s$$$ — a string of $$$n$$$ characters, where the $$$i$$$-th character represents the outcome of the game if the token is initially placed in the cell $$$i$$$. If Alice wins, then $$$s_i$$$ has to be equal to "A"; otherwise, $$$s_i$$$ has to be equal to "B".

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first sample, if Bob puts the token on the number (not position):

- $$$1$$$: Alice can move to any number. She can win by picking $$$7$$$, from which Bob has no move.
- $$$2$$$: Alice can move to $$$3$$$ and $$$5$$$. Upon moving to $$$5$$$, Bob can win by moving to $$$8$$$. If she chooses $$$3$$$ instead, she wins, as Bob has only a move to $$$4$$$, from which Alice can move to $$$8$$$.
- $$$3$$$: Alice can only move to $$$4$$$, after which Bob wins by moving to $$$8$$$.
- $$$4$$$, $$$5$$$, or $$$6$$$: Alice wins by moving to $$$8$$$.
- $$$7$$$, $$$8$$$: Alice has no move, and hence she loses immediately.

Example input:
8
3 6 5 4 2 7 1 8

Example output:
BAAAABAB

Example input:
15
3 11 2 5 10 9 7 13 15 8 4 12 6 1 14

Example output:
ABAAAABBBAABAAB

Editorial:
The game is finite thanks to the first restriction on possible moves: the number on which the token lies must strictly increase with each turn. More importantly, this means that if we model the cells as vertices of a graph and create a directed edge between $$$i$$$ and $$$j$$$ if $$$i \rightarrow j$$$ is a valid move, the resulting graph will be acyclic.
For each vertex we want to know whether it is losing or winning. A vertex is winning if and only if there exists an edge to a losing state.
This is easily solved on a directed acyclic graph – we process the vertices in reverse topological ordering. Let $$$v$$$ denote the current vertex. We already know the outcome of the game for all vertices adjacent to $$$v$$$, hence it is easy to determine whether $$$v$$$ is winning.
This process needs $$$\mathcal O(n + m)$$$ time, where $$$m$$$ is the number of edges in the graph. In general, this could be quadratic in $$$n$$$, but in this particular graph it's actually much less than that! Thanks to the second restriction on possible moves, there are at most $$$\lfloor \frac{n}{a_i} \rfloor$$$ possible moves from cell with $$$a_i$$$ written in it. As $$$a_i$$$ is a permutation, we have at most $$$\sum_{i=1}^{n} \lfloor \frac{n}{i} \rfloor$$$ potential edges, which is of order $$$\mathcal O(n \log n)$$$.