Блог пользователя ritesh_tiwary

Автор ritesh_tiwary, история, 8 лет назад, По-английски

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

  • Проголосовать: нравится
  • +7
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can you post a link to the problem

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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