Parvej's blog

LIS of a Grid path
By Parvej, history, 15 months ago, In English

Hello. I googled the following problem but didn't find any related article.

problem: You are given a N*M size grid of integers. Initially, you are at the leftmost top cell (1,1). You can either go right or down. There are (N+M-2) C N-1 paths in the grid. What is the Longest Increasing Subsequence's length of all the paths.

let A,
{1 2 4 3 }
{2 1 3 4 }
{1 2 4 5 }

You can go take A[1][1],A[1][2],A[2][3],A[2][4],A[3][4] from the path (1,1) -> (1,2) -> (2,2) -> (2,3) -> (2,4) -> (3,4) .

so the answer is 5.

1<=N,M<=1e3

A[i][j]<=1e9;

NB: Can we print the path under the given constraints?

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

»
15 months ago, # |
  Vote: I like it +4 Vote: I do not like it

Add the values in the grid in ascending order.

Lets say you are adding the value $$$x$$$ at position $$$(i,j)$$$ then $$$\text{lis}[i][j]=max(\text{lis}[i'][j']+1)$$$ where $$$i' \leq i$$$ and $$$j'\leq j$$$. These max queries can be done using a 2D Segment Tree.

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

    Probably better to use a persistent segment tree to avoid $$$O( (logN)^2)$$$ time, however, that could not fit ML.

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

    Hey, do you think you can elaborate on ur solution a bit? What does it mean when you say "Add the values in the grid in ascending order". What does this mean?

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

      Let $$$\text{lis}[i][j]$$$ be the LIS ending at position $$$(i,j)$$$. Then to calculate $$$\text{lis}[i][j]$$$ such that $$$a[i][j]=x$$$, we need to query all $$$(i',j')$$$ such that $$$i'\leq i$$$ and $$$j'\leq j$$$ and $$$a[i'][j']<x$$$.

      So we can find answers for $$$(i,j)$$$ by first finding LIS ending at some value $$$x'<x$$$ and doing range max queries on a 2D segment tree.

      → Reply