Rating changes for last rounds are temporarily rolled back. They will be returned soon. ×

aeonary's blog

DP on matrix problem
By aeonary, history, 18 months ago, In English

Please help me, the statement is: Give an matrix size n * m (n * m <= 10^6), from a square, we can move to 4 square that common side. Find the longest path that increasing

example:

3 5

1 2 2 8 9

2 3 1 7 10

1 4 5 6 1

10

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

»
18 months ago, # |
  Vote: I like it +3 Vote: I do not like it

longest path on DAG

→ Reply
  • »
    »
    18 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    strictly increasing or increasing?

    what would be the answer for this testcase.

    2 2

    1 1

    1 1

    tell me?

    → Reply
    • »
      »
      »
      18 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      I suppose it would be strictly increasing. If it was increasing, the problem would probably be not possible to solve in polynomial time complexity for certain testcases

      → Reply