arjun95's blog

By arjun95, history, 7 years ago, In English

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.

  • Vote: I like it
  • +11
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    7 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      1. Try to find a negative cycle in the graph. If it exists, the answer is YES.

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

      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        Code
        • »
          »
          »
          »
          »
          7 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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.

          • »
            »
            »
            »
            »
            »
            7 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            but what should be the termination condition as one city can be visited more than one time also.

            • »
              »
              »
              »
              »
              »
              »
              7 years ago, # ^ |
              Rev. 2   Vote: I like it 0 Vote: I do not like it

              If you run bellman-ford's algorithm on these states to find the shortest path, it shouldn't really matter?

              • »
                »
                »
                »
                »
                »
                »
                »
                7 years ago, # ^ |
                  Vote: I like it +1 Vote: I do not like it

                thanks man, now i got it.

»
7 years ago, # |
  Vote: I like it +1 Vote: I do not like it

can anyone help me, how to approach this question.