New answers tagged

2

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$ ...


9

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


Top 50 recent answers are included