Given a cost matrix (may contain negative values) and a man has some non-negative initial strength, he starts from zero(start) position and complete his journey at (n-1)th position with some non-negative power. matrix[i][j]>0 denotes he lost his strength from moving city i to j and matrix[i][j]<0 denotes he gain his strength by matrix[i][j]. he has to cover all the cities from 1 to n-2 and during his journey path his power may become negative but at the (n-1)th pos(destination) his power must be non-negative. we have to find whether he able to complete his journey or not.
test case-
initial strength=1
cost matrix = [0 2 2 -1]
[4 0 2 -1]
[4 2 0 -1]
[4 2 2 0]
ans=YES
path is-
(0 -> 3 -> 1 -> 3 -> 2 -> 3)
strength during its journey
(1 -> 2 -> 0 -> 1 -> -1 ->0)
i have no idea how to solve this question please help.
It looks unsolvable (unless constraints are low enough for bruteforce). Initial strength = n — 1, there are only edges of weight n and 1. You can't use edges of weight n, because n > initial strength and there's no negative edge. You'll need to go through n — 1 edges of weight 1 because you need to cover every single vertex. If you can solve this in polynomial, you can find a hamiltonian path in polynomial time. Change the start and the finish so that every pair gets to be start/finish. This finds a hamiltonian path if it exists in O(n^2 * solution of this problem). As far as I know finding a hamiltonian path is NP complete, can someone confirm this?
yes the constraints is low,value of n is less than or equal to 8, sorry but i'm not able to clearly understand what r u saying, can u please elaborate.
You should say so from the start. In this case, it is a simple bitmask problem. If you can't understand that just google "bitmask problems codeforces" or something like that.
Try to find a negative cycle in the graph. If it exists, the answer is YES.
Make a graph with 2 states: [mask of positions where you went through][position]. Use some algorithm (maybe Bellman-Ford, it should run in O(n^4 * 2^n) for this specific graph because the length of the path is at most O(n^2) or if you prefer try to think about some other DP) to find the shortest path from [0][0] to [2^(n-1) — 1][n — 1]. If the length of this path is <= initial strength, the answer is YES else it is NO.
I won't elaborate further. If you don't understand, solve bitmask problems.
i know about bitmasking, but in this case man can move any city more than one time also, for e.g. in given test case he move to city 3 , three times. my problem is how to solve this situation. means in bitmasking we move to any city only one time. i also write code for simple bitmask but it not handle this situation.
I think you can alter the bitmasking so that it can visit one city more than one time. First, you can maintain an array dp[bitmasks of cities visited][current city]. Normally for bitmasks, you only try to transition to different bitmasks (i.e. you wouldn't transition from [110110][2] to [110110][3]), but in your case, you can alter the transitions a bit and allow such transitions to occur.
but what should be the termination condition as one city can be visited more than one time also.
If you run bellman-ford's algorithm on these states to find the shortest path, it shouldn't really matter?
thanks man, now i got it.
can anyone help me, how to approach this question.