1)
In the given problem we have to find the shortest path or the path that takes the least amount of time to reach the destination. We are given 'k' lives in the Jumanji World where each landmark acts as a vertex and there can be 'n' such landmarks (deadly) stepping upon such landmarks would kill us and reduce our lives by 1. If we have more lives left then we respawn on the landmark that we died on, which makes the landmark not deadly.
We can modify the existing Bellman-Ford algorithm that finds the shortest path using k-edges. Using these k-edges we'll find the most optimal path \(\forall\) vertices \(v\in V\) from \(u:\left(u,v\right)\in E\) such that \(k\ge0\)
There could be a path that is the shortest but has \(m\) deadly landmarks such that \(m>k\), so we need to find a path from source to destination so that \(m<k\)
Recurrence
Let's assume \(OPT\left(k,\ v,\ m\right)\) represents the path that takes the least amount of time between the source and \(v\) using at most \(m\) edges and \(k\) lives
If a vertex \(v\) is unreachable from the source vertex using at most \(m\) edges or exhausting all lives then
\(OPT\left(k,\ v,\ m\right)=\infty\)
In the given problem there is no constraint on the edges so we'll explore the entire set of edges but we'll keep track of the lives we have. In our algorithm we will fill the Memo table for each death incrementally.
Suppose we have the shortest path distances using at most \(k-1\) edges, then we can calculate all shortest path distance which use at most \(k\) edges by only extending every shortest path by one edge.
We can write the recurrence using the above statement for Bellman-Ford
\(OPT\left(k,\ v,\ m\right)\leftarrow\min\left(OPT\left(k,\ v,\ m-1\right),\ \min_{u:\left(u,v\right)\in E}\left\{OPT\left(k,\ u,\ m-1\right)+w\left(u,\ v\right)\right\}\right)\ \forall k\) .... (1)
We need to also consider paths that are using \(m-1\) edges to get to destination vertex as they could be smaller than \(OPT\left(k,\ u,\ m-1\right)+w\left(u,\ v\right)\)
ALGORITHM (Bottom-up Approach)
1) Consider total edges in the Graph. Start finding paths to all vertices incrementing edges one by one.
2) We start with the source node \(s\) and we shall find path to all vertices \(v\in V\) using edges (1, 2, 3, 4,... n-1)
3) If we explore a node that is a death trap then we continue exploring more vertices if we have more lives and Update the Memo Table
4) Else we do not relax edge and mark those edges as \(\infty\)
5) We start again by incrementing our lives by one
PSUEDOCODE
We will use a 3 dimensional matrix as a MEMO - TABLE. M[k,V,m] where m are the edges
// k = lives
// G = graph
// s = source
// t = destination
Shortest-Path(G, s, t, k)
1. n = number of nodes in G \(\left|G.V\right|\)
2. Array M[0....k,V,0.... n-1]
3. Define M[0,t,0] = 0 and M[0, v, 0]=\(\infty\)
4.
5. \(For\ all\ i\ lives\ \in k:\)
6. \(For\ j\leftarrow1,\ .\ .\ .\ ,\ n-1\) // nodes
7. \(For\ v\in V\ in\ any\ order\)
8. Compute \(M\left[i,\ v,\ j\right]\) using the recurrence given above in Eq. (1)
9. Update Memo table such that K(lives) > death traps in path and change parent of v to u
if all lives exhausts then relax rest of the nodes for that row by making them \(\infty\).
10. Now increament k by 1 and again find path for all nodes and edges.
Now from the Memo Table M[i,t, k] \(For\ i\ \in\left\{0\ to\ k-1\right\}\) find the shortest path. There will be a finite optimal path if there is a way to reach the jaguar's eye.
While we are relaxing the edges of each vertex from u we are also marking the parent of that node. We can use that to trace back the path to source.
A Naive Approach
Using DFS we can find all paths to the destination and keep track of death traps encoutered in the path and then find the shortest path amongs them that keeps us alive till the Jaguar's eye.
2.
The problem given here is the problem of finding the optimal arrangement or the Maximum Bi-Partite Matching problem. There are a few facts that are given to us as follows:
- \(n\) different cities from where the students are coming from city \(i\). \(\left(1\le i\le n\right)\)
- \(a_i\) are the amount of students coming from city \(i\).
- There are \(m\) tables.
- Each table \(T_1,\ T_2,\ T_3,\ .\ .\ .\ T_m\ \) has a capacity of \(t_1,\ t_2,\ t_3,\ .\ .\ .\ t_m\)
We can solve this problem using Network Flows
First, We need to construct a Network Flow using the following rules:
- We will first create \(n\) nodes, each representing a city. Label them as 1 through \(n\).
- Similarly we'll create \(m\) nodes for tables \(t_1\) through \(t_m\)
- Create a source node \(s\) and a sink node \(t\) in the network flow graph
- Create an edge from \(s\) to city \(i\):\(\left(s,i\right)\ \forall\ i\in n\) with edge weights or capacity as \(a_i:\ 1\le i\le n\)
- Similarly create edges from table \(T_j\) to sink node \(t:\ \left(T_j,t\right)\ \forall\ j\in m\)
- Now, to restrict the flow from each node representing a city, create edges from city \(i\) to each node that represents a table \(T_j\) such that \(i\in\left[1,...n\right]\) and \(j\in\left[1...m\right]\) with a capacity of 3.
The network would appear like this: