# Tag Info

Accepted

### Searching for rock-hard integers.

You can do much better than checking all numbers... note that any rock-hard integer is equal to a product of powers of $1,2,\ldots,9$; indeed, all rock-hard integers must be $7$-smooth. There aren't ...
• 42k

### Searching for a point on the real line

This is a partial answer. I've found a recurrence relation to calculate future moves from past moves, but am not yet able to find the optimal length of the first move. I am able to say that the first ...
• 2,671

### Graph puzzles: Constructing graphs from tiles

As a partial answer, here is how we can solve the sampling problem in cases like your first tile set: triangle-free tile sets. When lots of triangles get involved, the problem becomes much harder. A ...
• 145k
Accepted

### Prune graph to detect cycles: better than DFS?

One of the advantages of DFS is that it's a single algorithm that does lots of things. By the time you've implemented it five times, you will not think of anything else as an easier algorithm :) It ...
• 145k
Accepted

### Finding Lowest Elevation Path Between Two Points

This is an instance of a "shortest path" problem. Create a directed graph with vertex set equal to your grid points, and with a directed edge from $a$ to $b$ if $a$ and $b$ are adjacent, and give ...
• 24.5k
Accepted

### Find a unique path in a graph that's colored in red and blue

I'm assuming you can only use plain vanilla DFS and BFS, and are not allowed to make any modifications to them. Thus, to achieve what you want, you need to modify the behavior of the algorithm by ...
• 37.5k

### Algorithm wanted: Enumerate all subsets of a set in order of increasing sums

For anyone curious, I implemented Mike Spivey's answer in Python. ...

### Maximum of minimum number of moves required for hardest 8 puzzle

The wikipedia link for the 15 puzzle points to an OEIS link which points to a paper "Complete Solution of the Eight-Puzzle .." by Alexander Reinefeld. (The link in the OIES page is bad.) The ...
• 39.5k
Accepted

### Counterexample for statement about binary search tree

If the search path goes right-left-left, some node in $C$ may be smaller than the rightmost node of $P$. Concretely, let $0$ be at the root, its two children are $-1$ and $4$. The children of $4$ are ...
• 376k
Accepted

### Find an element that repeated $\frac{n}{5}$ times in sorted array

Note that the interval you're looking for is so big that it must hit one of five evenly-spaced indexes between 0 and $n$ (say $n/6,2n/6,3n/6,4n/6,5n/6$), so we have five candidate values for the ...
• 11.9k

### search for specific value out of data set

Your case 0 is known as the subset-sum problem. The others are all at least that challenging. It's known to be NP-hard, which is to say (informally) that if there are $n$ items in your dataset, pretty ...
• 94.4k
Accepted

### Prove that a connected undirected graph G is bipartite if and only if there are no edges between nodes at the same level in any BFS tree for G

I guess induction is not a good idea here. There is a rather straightforward proof. Let there be an edge between vertices $u$ and $v$ of the same level of BFS tree. Then there is obviously a cycle of ...
• 7,036
Accepted

### Partition integers into $M$ sets

Let $N=KM$. Let $S_i = A_i+\ldots +A_{i+K-1}$, $A_{N+i}=A_{i}$. Obviously, $\{A_i,\ldots ,A_{i+K-1}\}$ is positive if $S_i$ is positive, and $\{A_i,\ldots ,A_{i+K-1}\}$ is negative if $S_i$ is ...
• 7,486

### Computational complexity of Eulerian and Hamiltonian paths and cycles in (un)directed graphs

See the following theorems of a lecture “Round Trips” of our blockcourse “Algorithmic Graph Theory” by Joachim Spoerhase and Alexander Wolff. Theorem. Let $G = (V,E)$ be an undirected and connected ...
• 93.6k

### What is the best way to guess a number in a limited number of guesses?

You can work your way back from the end of the game to optimize the strategy. At each stage, you know that the number is in some interval. On the last guess, you'll just guess any number in the ...
• 239k
Accepted

### Is it possible to find something better than binary search for this problem?

If $k$ is chosen uniformly at random, you can’t do better than binary search, since the binary entropy of $k$ is $\log_2n$ and you can’t determine its value with fewer answers to binary questions (i.e....
• 239k
Accepted

### Search 2D space for optimal location to "bomb".

Let's say you have a solution. Then this solution features a single point that is closest to the border. Draw the shortest line between this border and the point, then move the circle along this line ...
• 355
1 vote

### Efficient directional nearest-neighbor search among rectangles

(If I understand the question correctly,) here is one approach. Sort for angle of rotation first. Keep offset in the list of +90 degree modulos. Use your favorite sorting algorithm here. Several of ...
• 26.1k
1 vote

### Searching/Sorting Algorithm

We can do this in linear time. In one pass, we can place the elements of $A_2$ in a hash set which has constant time access. Call the hash set $H$. Then we get ...
• 11.6k
1 vote

### Can you find an invertible submatrix?

Updated Answer: I would appreciate it if others double check this to make sure everything is correct, I would warn the reader there may be errors: Important: I just realized that there are in fact ...
• 331
1 vote

### Difficulty understanding the relation between the representation of a number and the time complexity of searching for (0, N - 1)?

i briefly read the article you directed to, its looks to me that he meant that even if you got your number, $N$, in first try, its still represented in $\log(N)$ digits, so you need to check every ...
• 482
1 vote

### Restricted query problem

Surprisingly, after one day's research, I find that the case with uniform distribution was proven to be NP-complete by this paper. It is indeed a classic question as I expected before.
1 vote

### How to apply DFS on a disconnected graph.

DFS can be used to solve the connectivity problem. You continue to run it on different components until the entire graph is "discovered". Under any case, it does not take longer than $V+E$. if none ...
• 161
1 vote

### How to apply DFS on a disconnected graph.

This link should answer your question. In fact, DFS is often used to determine whether or not a graph is disconnected or not - if we run DFS and do not reach all of the nodes in the graph, the graph ...
• 378
1 vote

### Finding Lowest Elevation Path Between Two Points

This problem can indeed be seen as shortest path problem. Let's say matrix has elevation data, a cells neighbors can be retrieved using Queen's pattern (8 of them), then code is ...
• 16.3k
1 vote

### Find a unique path in a graph that's colored in red and blue

On each node $v_i$, keep two counters for the blue and red edges it takes to go from $a$ to $v_i$. Node $a$ starts with $(0,0)$. Do a BFS. Whenever you reach a node, if the counters are undefined, use ...
• 3,424
1 vote
Accepted

### Is there an algorithm that search multiple duplicate pair combination without a loop?

It looks like all of your arrays are sorted. This means that it is very quick to search for a specific element in any array. It can be done in $O(\log n)$ using a binary search. Suppose you want ...
1 vote
Accepted

### Smart enumeration of a subset of graphs obtained from a parent graph

Note from the future; I've condensed this answer and added this answer's source code to a GitHub repo, and more content on the pages site related to graphs, because it was getting rather verbose. I'...
• 195
1 vote
Accepted

### Search algorithm to find integer input that produces the first 'True' (bool: 1) occurence of a computationally expensive boolean function

I doubt that you can do better than the logarithmic time of binary search. But if the cost of your expensive calculation depends on $n$ in some easily computable way you might be able to speed things ...
• 98.4k
1 vote

### Search algorithm to find integer input that produces the first 'True' (bool: 1) occurence of a computationally expensive boolean function

Here's some pseudocode that I would suggest. Not sure if that helps or not, though. Method int binarySearch(min, max) int x = (min + max)/2; if (max - 1 = min) $\quad$ return max if f(x) = 1 \$\...
• 2,388

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