ritesh_tiwary's blog

Help needed...
By ritesh_tiwary, history, 8 years ago, In English

Hi All,

Please help in this interesting grid problem.

There is a grid of dimension N * M (1 <= N,M <=500). Each cell contains a number K (0 <= K <= 10^5). Currently we are at cell (1,1) and we need to go to cell (N,M).We pick each number that is present in the current cell as we proceed along the path. Transitions are as follows: From position (r,c) we can go to (r+1,c) or (r,c+1) or (r+1,c+1).

We need to print the cell positions of lexicographical largest path among all possible paths. example :

1 2 3

4 5 6

7 8 9
In above matrix path [(1,1),(2,2),(3,3)] is largest.

Thanks in advance ...

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

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

Auto comment: topic has been updated by ritesh_tiwary (previous revision, new revision, compare).

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by ritesh_tiwary (previous revision, new revision, compare).

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can you post a link to the problem

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

    Actually the problem was asked in hack a Heart tie breaker round on hackerearth, Which can't be accessed now.

    → Reply
»
8 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Always greedily choose to take the largest next value you can.

The problem is, if there are several cells with that value, you can't know which one to choose. So just take all of them. What I mean is, keep a set of cells S that are currently maximal, and in each iteration consider all the cells that you can reach from any cell in S, and replace S with this new set. Also remember, for each cell, where you first reached it from, so you can reconstruct the answer later: when you finally reach (N,M), just print the entire reconstruction from (N,M) to (1,1).

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

    Got it,Thanks a lot.

    I stuck at this problem for a long time.Thank you.

    → Reply