# Tag Info

6

Hint #1: Hint #2:

4

Copied from here. The mathematics Consider the group $G=S_w\times S_h$, where $S_w$ and $S_h$ are the symmetric group of the sets $W=\{1,2,3,\ldots,w\}$ and $H=\{1,2,3,\ldots,h\}$ with $w$ and $h$ elements, respectively. The group $G$ acts on the set $X=W\times H$, which we view as the set of indexes of the entries of the matrices. Each matrix is a function ...

4

The problem of finding a Hamiltonian path in a partial grid graph (that is, an arbitrary subgraph of a grid, not necessarily even induced) remains NP-complete [1]. Thus, you are likely out of luck for a polynomial-time approach. A good choice for a heuristic might depend on your instance size and further structure. However, in general, you could try say a ...

3

There is an easy reduction from the well-known NP-complete problem MAX-CLIQUE to your problem. Recall that in MAX-CLIQUE we are given a graph $G$ and an integer $k$, and have to decide whether $G$ contains a $k$-clique. We can recast this as an instance of your problem as follows: the matrix $A$ is the adjacency matrix of your graph, and the goal is to ...

3

We can imagine simulating the random walk on an infinite line, keeping track of the "extension", which is the distance between the rightmost point visited and the leftmost point visited. Let $\ell(a,b)$ denote the probability that the extension became $b-a$ due to a move to $a$, and let $r(a,b)$ denote the probability that the extension became $b-a$ due to a ...

2

Actually, grid graphs are a very specific class of input problems, and a good number of algorithms are known that can solve problems which remain hard in other instances, i.e., non-grid graphs. Even if it is not directly related to your question, I could not avoid citing the following paper: F. Keshavarz-Kohjerdi, A. Bagheri, A. Asgharian-Sardroud. A ...

2

Try building a summed area table—a table where the value in each cell is the sum of all the values above and to the left, inclusive, of the cell in the original table. See if you can figure out an $O(n^2)$ solution from that.

1

Let $U$ be the set of rows in the given matrix and $V$ the set of columns. For each $x$ at row $i$ and column $j$, add an edge between row $i$ and column $j$. You will have an (unweighted) bipartite graph $G=(U,V, E)$. The problem is to find a perfect matching, which is basically the same as find the maximum matching of $G$. There are various algorithms that ...

1

This is no different than asking for an algorithm for deciding if the entries of an array contain a nonzero. So what you describe is optimal, i.e. an adversary argument shows that any algorithm must examine each entry for otherwise you can't know for sure.

1

There is no algorithm with worst-case running time better than $O(n^2)$. There is a simple adversary argument to prove this. Consider any algorithm that is purported to be correct, and that always inspects fewer than $n^2$ entries of the matrix. Thus, there must always be some entry that is uninspected. Consider a matrix that has 1's in the entire first ...

1

If the matrix has two distinct eigenvalues, you can find them using power iteration. Let $\lambda_1,\lambda_2$ be the 2 eigenvalues, where $|\lambda_1| > |\lambda_2|$. Then you can use power iteration to find $\lambda_1$. Next, set $A' = A - \lambda_1 \text{Id}$. $A'$ is a symmetric matrix with eigenvalues $\lambda_2,0$, so power iteration on $A'$ ...

1

These are called Catalan numbers, and the term $\binom{2N}{N}$ is called a central binomial coefficient. There are several formulas for these numbers which can be used to compute them efficiently, such as the one you present, or $$C_n = \prod_{k=2}^n \frac{n+k}{k}$$ The problem with writing down the time complexity for computing these numbers is that the ...

1

One simple way is to face this problem like a state-space search. Assume that going in each of 4 directions on a node that has not been visited is one action. Make a function that is responsible for producing all the next possible states given the current state. It produces a list of all next actions (at most 4 states). As you may know, we call this function ...

1

I'm assuming that $W$ is an integer upper bound to $\sum_i w_i$, as asked by xskxzr, that all $w_i$ are positive integers, and that the values $w$ in the queries are also integers upper bounded by $W$. For $i \ge 1$, let $S[i,w]$ be the largest index $j \in \{1, \dots, i\}$ such that it is possible to select a subset of $\{w_k : j \le k \le i \}$ of weight ...

1

I won't go into the details of your specific case but try to answer the general problem. In the unrestricted case there is a mapping from each of the $n$ (=512) input states to one of 2 output states and you want to restrict the function as follows: Create a partitioning of the initial $n$ input states into subsets. Your adapted function maps each of these ...

Only top voted, non community-wiki answers of a minimum length are eligible