The Harvard robotics club has organized a Robothon. n robots are placed along the edge of a circular area at the middle of the OAT(open air theatre). Each robot will move along arbitrary tracks inside the circle while leaving behind a heat signature along its trail. However, they have been programmed not to cross their own trail or the trail of another robot, neither will they ever move out of the circle. In case a pair of robots i and j meet at any point, they are removed from the scene and the club will pay a reward sum of M[i, j] to the owners of these robots. Note that some robots can keep moving infinitely without ever meeting another one. Given the reward matrix M where M[i, j] = M[j, i], design a polynomial time algorithm that determines the maximum money the club might potentially end up spending. For this particular problem, give a very brief justification of the recurrence. Give pseudo-code for a dynamic program which solves the recurrence efficiently You do not need to prove correctness of the pseudocode
The Harvard robotics club has organized a Robothon. n robots are placed along
the edge of a circular area at the middle of the OAT(open air theatre). Each robot will move along arbitrary tracks
inside the circle while leaving behind a heat signature along its trail. However, they have been
programmed not to cross their own trail or the trail of another robot, neither will they ever move
out of the circle. In case a pair of robots i and j meet at any point, they are removed from the scene
and the club will pay a reward sum of M[i, j] to the owners of these robots. Note that some robots
can keep moving infinitely without ever meeting another one. Given the reward matrix M where
M[i, j] = M[j, i], design a polynomial time
club might potentially end up spending. For this particular problem, give a very brief justification
of the recurrence.
Give pseudo-code for a dynamic program which solves the recurrence efficiently You
do not need to prove correctness of the pseudocode
Trending now
This is a popular solution!
Step by step
Solved in 2 steps
