Borjianamin's blog

By Borjianamin, history, 7 months ago, In English,

I'm sorry. I have a question but I couldn't solve it. it doesn't belong to codeforces. In this question, we have a n * n matrix and we want to go from (1,1) to (n,n). we only can move left, right, up, down. but there is a special tag on some cells. if we are in a cell and there is a special tag around us (I mean 8 side of a cell), we can move directly to that. Question guaranteed that each row and each cell contain exactly one tag.
We want to find minimum move to go from (1,1) to (n,n).
Question give information in special way. for example:

Input 1:

1 2 3

Output 1:


Input 2:

2 3 1 4

Output 2:


in first row, n will given. in next row, n numbers will given. The i-th number mean which row in i-th column contain tag. range of n is 1 <= n <= 300000.

memory limit is 256Mb
Time limit is one second

I think solution is dynamic programming (dp). Because of memory limit , we can't construct a 2D array for out dynamic programming but because we always need just two last state, I only use 3 array for dp. It solves memory limit however time limit is one second and my dp algorithm which calculate all way, failed. it is a simple dp. it calculate 3 state (go down, right and diagonal for special tag). Is it possible to give me a better way?
I'm sorry for bad English. Thanks.

  • Vote: I like it
  • 0
  • Vote: I do not like it

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

If I correctly understand you, seems that it's a strightforward LIS problem, only you should reject tag cells with value $$$n$$$ for $$$x$$$ and $$$y$$$ coordinates (two or one tag cells). Let's denote LIS as $$$k$$$ then the answer is $$$2(n-1)-k$$$. LIS can be found in $$$O(nlogn)$$$.

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

    Thanks very much. You give me idea. It just has some boundary condition which I handle them. for example each tag in column one and row one, doesn't help me. but idea is same. Thanks a lot.