Question

GS has hired Harsh, Rahul, Ankita and Niranjan who happen to be childhood friends. They have been sent to a new city for the onboarding process
GS has given them a choice to choose any hotel in this city
This city unlike other cities is a matrix of hotels and there are no roads. If any of the friends go through a hotel even once, the group will have to pay its full rent. From a hotel, you can go to the
hotels to its North South East, or West
Since Harsh Rahul, Ankita and Niranjan are childhood buddies, they want to meet each other. Strangely enough, all four are very particular about the direction they travel so Harsh only goes
West, Rahul only goes North Ankita only goes East, and Niranjan only goes South
Any number of friends can live in any of the hotels. Living Cost of all the hotels in the city are given, some of which may be negative Negative cost means if any of the friends lives in or goes
through this hotel, the group will get paid an amount equal to the negation of the cost. Now the aim of the four friends is to find the minimum cost for all of them to meet at a particular hotel.​

Answer 1

Answer:

All should pay 5000 each if put it

Answer 2

Answer:

USing subset sum

Explanation:

I think it is subset sum problem with few contraints