# Tag Info

The treewidth (and pathwidth) of the $k\times k$ grid is exactly $k$. (And, more generally, the treewidth and pathwidth of the $k\times\ell$ grid is exactly $\min\,\{k,\ell\}$). For the example grid $$\begin{matrix}1&-&2&-&3\\|&&|&&|\\4&-&5&-&6\\|&&|&&|\\7&-&8&-&9\end{matrix}$$ ...
Lemma. $|a|+|b|=\max(|a+b|, |a-b|)$ for any real number $a$ and $b$. Proof 1. $|x|=\max(x, -x)$ for all real number $x$. So \begin{aligned} |a|+|b| &=\max(a, -a) + \max(b, -b)\\ &=\max(a+b, a-b, -a+b, -a-b)\\ &=\max(\max(a+b, -a-b), \max(a-b, -(a-b))\\ &=\max(|a+b|, |a-b|) \end{aligned} Proof 2. There are $2 \times 2 = 4$ cases. $a\ge ... 6 The$a \times b$grid graph has the vertex set$[a] \times [b]$, and edges of two types: horizontal edges$(i,j),(i+1,j)$(of which there are$(a-1)b$) and vertical edges$(i,j),(i,j+1)$(of which there are$a(b-1)$), for a total of$ab$vertices and$(a-1)b+a(b-1)=2ab-a-b$edges. 5 In the terminology of Nikoli Puzzles this is known as "Nanbarinku" or "Numberlink". The description does not always explicitly mention all squares must be covered, but this is indeed the case in all solutions I checked. According to Wikipedia Numberlink the problem is NP complete, with reference: Kotsuma, Kouichi; Takenaga, Yasuhiko (March 2010), NP-... 5 No, your reasoning seems right. Sometimes problem setters just throw in such things in order to make the problem sound harder than it is. 2 This is the longest path problem. It's NP-hard to find the longest path in a general graph. You can try applying any standard algorithm for finding longest paths. Search on this site for "longest path" and "Hamiltonian path" to find many references. Since you're willing to accept suboptimal solutions, you might look for a heuristic or approximation ... 2 You have an unweighted, undirected graph with$N$vertices, and where each vertex has degree$K$. Then the problem of computing shortest paths can be solved in$O(KN)$time using simple breadth-first search. Why is this faster than Floyd-Warshall etc.? Because Floyd-Warshall has to handle weighted graphs. In your case you have an unweighted graph: every ... 2 Firstly you did not write the complete question, to complete it, if$S$is the maximum sum of weights in any sub-grid of lenght$ \le L$, then we have to report$S$and length of the sub-grid with smallest integral side where sum of weights inside it is$S$( hint: it won't change the complexity of the solution ). But that is slight detail which I leave to ... 2 Let$b(p, \ell)$be a boolean value denoting whether the horizontal segment whose left endpoint is$p$and whose length is$\ell$exists. Then the values of$b(p,\ell)$for all possible$p$and$\ell$can be computed in$O(n^3)$recursively using the fact that$b(p,\ell)$is true iff$b(p,\ell-1)$is true and$b(p+\ell-1,1)$is true where$p+\ell-1$... 1 Let the one-dimensional cells be$c_1, c_2, \cdots, c_{n^2}$. Assume the top-left cell is at$(1,1)$, i.e., the first row and the first column. Assume the top right cell is at$(1,n)$, i.e., the first row and the$n$-th column. Then the$i$-th cell,$c_i$is at$(i/n + 1, i \%n +1)$. Here$i/n$is the integer division and$i\%n$is the modulo operation in ... 1 Don't be so quick to reject your approach! Your approach is a great solution. On a$15\times 15$grid, you'll only have to try 225 different options. Checking each option is very fast, so it should be extremely fast to try all 225 different solutions -- I'd imagine it will finish in microseconds. As Knuth supposedly said once, "premature optimization is ... 1 I ended up using the UCT (MCTS with UCB1) algorithm but with a twist. Normally, in UCT, the simulation phase is a simulated play-through of a game with moves chosen at random. If the simulated game ends in a win, the node's score, from where the simulation was played out, and all it's parents' scores all the way back to the root, are incremented by 1. In ... 1 Travelling Sales Man is NP-complete. This problem isn't, it has an easy polynomial time solution. Don't go there. 1 Yes, there are efficient algorithms for this problem, using standard data structures for storing two-dimensional data. Here is a simple approach. Store all of the colored pixels in a quadtree. Next, for each sub-circle, compute it bounding box, so now you have a square instead of a circle. Query the quadtree data structure to find all points contained ... 1 There is a dynamic programming algorithm whose running time is$O(2^{4n})$. Suppose we have already chosen a configuration for the first$i$columns. Mark a cell in the$i$th column as "red" if the cell to its right cannot be selected (i.e., the number of selected neighbors, not counting its right neighbor, is equal to the number in that cell), or "green" ... 1 Decompose your graph into biconnected components. Since only a biconnected component can border faces (why?). This can be done in linear time. You can find the number of faces in each component by Euler's identity. This can be done in linear time per component. Pick the component with the largest number of faces and find the cycle bordering that component. ... 1 Start by counting the left edges and top edges, then add in the missing right and bottom edges. For a$m \times n$grid graph, there are$m \times n-1$left edges (a left edge for each column at each row). Similarly, there are$m-1 \times ntop edges. At this point, we are still missing the bottom edges for the last row, and the right edges for the ... 1 Let \begin{align} C&=\left\lfloor\frac WL\right\rfloor& R&=\left\lfloor\frac HL\right\rfloor \end{align} be the maximum number of rows and columns respectively. It sounds as though you're looking for the maximumL^*$such that, when$L=L^*$, we have$CR\ge N\$. Let \begin{align} L_0&=\sqrt{\frac{WH}N}\\ C_0&=\left\lceil\frac W{L_0}\...