• Member for 3 years, 1 month
• Last seen more than a month ago
• France

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

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

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

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

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

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

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

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

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

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

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

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

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

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