# Tag Info

3

Using Trie Data Structure, you can solve this problem in $O(m + n)$ if we know that values are computer integers (e.g. all 32-bit or 64-bit values). Let say we know that all integers in $A$ are 32-bit values. Use the following steps: Create an empty trie. Every node of trie may contains at most two children for 0 and 1 bits. Insert all values in $A$ into ...

2

In general Warnsdorff's rule is just a heuristic that guides the search. It is still possible that the search hits a dead-end and we are forced to backtrack. So let us consider the $n \times n$ chessboard now. Warnsdorff's rule (nor any other method) won't find a solution for $n < 5$ as a solution exists precisely when $n \geq 5$. Given that $n \geq 5$, ...

2

This question can be reduced to the exact cover problem which is NP-Complete. A typical method for solving the exact cover problem is known as Algorithm X. Consider the set of choices you have: For each tetris piece of $4$ units, you can select an orientation and a location to place it on the board. For each choice, the piece will cover $4$ squares on the ...

2

Ignore recursion for the moment, and pretend that a recursive call is just like any other call. Then the solution is easy: all local variables are spilled to the stack across calls, including the recursive call. So yes, if there is deep recursion going on, most of the local variables will reside on the stack most of the time. Every platform (operating ...

1

Look at maximum interval scheduling. Assign an interval $(s_i, t_i)$ to each performer, for $i=1,\dots,N$, meaning that the performance starts at time $s_i$ and has a duration of $t_i - s_i$. Assume for now that all the intervals are sorted by their end time. Just for simplicity assume also that all times are distinct (this assumption is unnecessary). Your ...

1

This is a simple Interval Scheduling Maximization problem, which can be solved in O(n log(n)) time via a simple greedy algorithm. The trick is to sort performances according to end time and not start time. Here is the description of the solution found on the Wikipedia page I linked: Several algorithms, that may look promising at first sight, actually do ...

1

Without more details, I think it is important to precise that Pandemic is 2-4 players cooperative game. Players are allowed to discuss about strategy and share any information (even if the rules are ambigous on the possibility to share card in hand information). Moreover to achieve victory efficiently, players have to trade cards which is hard without ...

1

As it is mentioned in this paper, you can find a concave-hull of points in a 2-dimensional plate in $O(n \log n)$ (as complex as finding a convex hull).

1

Your problem is a generalization of the Longest Path problem, which is NP-hard. If the functions are constant and every conversion increases the amount of money, then there's no reason not to convert all of the money at once. At that point, you are just looking for the longest path. Your generalization, allowing partial conversions, non-constant functions,...

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