Optidad
  • Member for 3 years, 1 month
  • Last seen more than a month ago
  • France
Is finding a path with more red vertices than blue vertices NP-hard?
Accepted answer
9 votes

Your solution does not work because Dijkstra and Bellman-Ford cannot interpret "simple path" feature. And they will indeed fall in any negative cycle. I think the best to show NP-completeness, is to ...

View answer
2-dimensional ranking of multiple arrays
4 votes

Here is a solution quite simple to implement, that only improves the $d$ factor. For the increasing series $[1, 2, .., n]$, get the tuple list of the coordinates to increase in your output array. For $...

View answer
Linear Path Optimization with Two Dependent Variables
4 votes

You can consider the 1D-position of the 2 runners as one 2D-position. X-coordinate and Y-coordinate for respectively runners 1 and 2. So in your instance, the starting point is (0, 100). Then all ...

View answer
Find shortest path that goes through at least 5 red edges
4 votes

What about reducing the problem first ? UPDATED with more details : Build 2 node subsets: Vs contains s and the 10 reached nodes of the red edges (called a1, a2, ..., a10 hereafter). This is a 11 ...

View answer
how to find total paths in a graph which have only one vertex common with a given path
Accepted answer
3 votes

Let say the given path crosses $K$ nodes. As $G$ is a tree, if you remove all the edges of the given path, you will get a forest of $K$ trees. Each of these tree contains exactly one of the $K$ ...

View answer
Cannibals missionaries problem - solving usings graphs
Accepted answer
3 votes

You did most of the job. Each vertex is a state $(M, K, B)$ and edges represent the possibility to pass from a state to another with one ship transport. Let say $B$ can take the values $L$ or $R$ for ...

View answer
Difference between stable marriage problem and assignment problem
Accepted answer
3 votes

The main difference is the optimization goal. In classical assignement problem, there is a fitness/cost function to maximize/minimize. Each assignement possibility has a weight and you only sum up ...

View answer
Minimum number of moves puzzle
Accepted answer
2 votes

You can determine simply if there is no solution. Case $K=2$ with the players on different and non-adjacent cities (thanks orlp to point it). Let's first assume a simpler problem where players may ...

View answer
Min path cover for a three-layer graph with all paths traversing all layers
2 votes

Let's denote: $C$, the $c$ different colors, $T$, the $t$ different tastes, $S$, the $s$ different smells, $X$, the edges of the possible color/taste combinations, $Y$, the edges of the possible ...

View answer
3SAT and directed graph
2 votes

I think you are trying to build the 2-SAT implication graph for 3-SAT. In 2-SAT, $(x_a \vee x_b)$ may indeed be considered as 2 implications, $\neg x_a \Rightarrow x_b$ and $\neg x_b \Rightarrow x_a$. ...

View answer
Efficient way to count number of intersections of line segments
Accepted answer
2 votes

Let's first assume there is no common boundaries between all segments. Create the list of tuples ($pos$, $ind$) with a value ($pos$) for each boundary of every segment (thus $2n$ values) and $ind$ the ...

View answer
Dijkstra and A* Algorithms: Why is A* faster?
2 votes

I absolutely don't understand the attached images and what you try to do on it. What I can say is that Dijkstra an A* algorithm are pathfinding methods: Dijkstra algorithm is an exploration method ...

View answer
Similarly colored paths in a DAG
2 votes

Let's take the initial graph $G=(V, E)$ and create a new graph $G'=(V', E')$ where every vertex $x$ is a state representing a pair ($i$, $j$) of vertices of $G$. So basically, for $N$ vertices in $G$, ...

View answer
Fastest algorithm for transforming points into graph
Accepted answer
2 votes

As you can imagine, evaluating every pair of points is very expansive ($O(N^2)$ for $N$ points). If your set of point is sufficiently dense with respect to $M$, a simple solution is to use a grid. ...

View answer
Pandemic board game - find all possible next 4 actions
Accepted answer
2 votes

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

View answer
Algorithm to compute sum of cost of all path between pair of unique vertices of a tree
2 votes

Let's build some recursive function. We start picking any vertex of the tree $T$ and call it $R$ as root. If $R$ was removed, you would get a forest of several sub-trees. Every subtree $T_k$ has a ...

View answer
Given a set of numbers, get the maximum 10 number average below a certain threshold
2 votes

Looking for a maximum average $m$ below a threshold $m_{max}$ is the same than looking for a maximum sum $s$ below a threshold $s_{max}$. If you have to select $k = 10$ numbers among $N$, you have: $...

View answer
Difference between greedy and work conserving scheduler for DAG
Accepted answer
2 votes

If I understand well, it is the same scheduling method with different names. I think Work-conserving Scheduler is the more "official" one. "greedy" can indeed qualify many aspects of the problem and ...

View answer
Two Minimax AIs playing against each other
Accepted answer
2 votes

First of all, note that in chess, white players plays first and it is a quite complicated game to build a AI for. The fact it exists several "draw" situations makes the evaluation function even more ...

View answer
Find an optimal ordering
2 votes

I don't know if there is actually a polynomial solution. Nevertheless based on Pål GD's comment, you can build a simplification function. The initial matrix is simplificated as you build the output ...

View answer
Algorithm : Visiting all stations in minimum time with additional constraints
2 votes

Considering the "you have to visit all stations minimizing time", this is a Travelling salesman problem (see https://en.wikipedia.org/wiki/Travelling_salesman_problem). The additional constraints on ...

View answer
MST: Is there such an example of a graph with unique mst and not unique light edge?
2 votes

If there is not a unique light edge crossing any cut, it means that every node has at least 2 edges of minimum weight. If you use Prim's algorithm to build your MST which is: Grow the tree, adding ...

View answer
Matching schedules between users and providers
Accepted answer
2 votes

I think your problem is actually not a scheduling problem but a set cover problem. Just cut the time line in the atomic time parts of providers and assign them indices. For instance, considring only ...

View answer
Either find a perfect matching, or return a witness that none exist
2 votes

I would use a degenerated version of the Hungarian algorithm (O(n^3)). In the basic version on a U, V bipartite graph, you loop on the elements of x of U to give them the best assignement y from V. ...

View answer
Problem: covering holes on a pipe
2 votes

If you see your position from left=0 to right=length(pipe), you can simply cover your holes from left to right. When adding a new tube, put the leftmost remaining hole at the leftmost covered ...

View answer
Least number of guesses needed to determine all unknown subsets of a set
Accepted answer
2 votes

A simple algorithm may be: Loop on: take the next unassigned element Ei and create a new set Si assigning Ei to it. loop on all unassigned elements Ej, testing the pair {Ei,Ej}. If it is true, ...

View answer
Finding minimum possible cost of road network between cities with distance from capital condition
1 votes

The MST indeed adresses conditions 1 and 3 but not conditions 2. The solution of the global problem (as shown by your example) is not the MST but still a tree. Let's call $T$ the solution for the ...

View answer
Are different assignments allowed for the implication graph proof of 2-SAT being in P?
1 votes

You have to understand that $a \implies b$ cannot be interpreted as $\neg a \implies \neg b$. Only the contraposition $b \implies a$ is true, but this one is already in the implication graph by ...

View answer
Maximization problem
Accepted answer
1 votes

The case $k \ge n$ is trivial as you can give different value to every variable, which satisfy all inequalities and thus is optimal. So let's consider $k < n$. This problem can be considered as ...

View answer
How to detect "tree-able" set-families?
Accepted answer
1 votes

An idea is to use a tree of set instead of a tree of indexes. One can develop it arbitrarily to a valid tree of indexes at end. An advantage is that you obtain all the valid trees with this process. ...

View answer