# Tag Info

Each $j$ contributes $1$ to all $K'(\sigma)_i$ with $j < i < \sigma_j$. Ideally you want a data structure that maintains a collection of $n$ counters $C_0, \dots, C_{n-1}$ under the following operations: Offset($j$, $\delta$): Given $j$ and $\delta$, add $\delta$ to each $C_i$ with $i \le j$. Evaluate($i$): Return the value of $C_i$ When $\sigma_j$ ...
Each element $j$ contributes $1$ to the cardinality of all sets $\{j > i \mid \sigma_j > i\}$ for which $i < \min\{\sigma_j, j\}$, and $0$ to the other sets. You can compute all $n$ values $K(\sigma)_i$ in $O(n)$ time as follows. Maintain an array $A[0, \dots, n-1]$ where each entry $A[i]$ is initialized to $0$. Then, for each $j$, increment $A[\min\... 1 You just have an arithmetic error when computing$1 - \dfrac{3\cdot4+4\cdot3+3\cdot3}{10 \choose 2} = 4 / 15$. 0 I would suggest you try to search for a coloring using a SAT solver or ILP solver. To solve with an ILP solver: use zero-or-one (boolean) variables$x_{i,j}$, where$x_{i,j}=1$means that the$i$th tile is colored with the$j$th of the 6 possibilities. This gives you$70 \times 6 = 420$variables. Next, for each colored edge pair$p\$, add a linear equality ...