haitax511's blog

Interesting optimisation problem : Travelling in three ways in a nxm grid
By haitax511, history, 11 months ago, In English

Bob is playing a game on a 2D grid with $$$n$$$ rows and $$$m$$$ columns. He starts at the top-left corner, cell $$$(1, 1)$$$, and his goal is to reach the bottom-right corner, cell $$$(n, m)$$$.

Bob can move in the following ways:

  • Choose an index $$$i$$$ ($$$1 \le i \le k$$$) and:
  • Move down by $$$A[i]$$$ rows: from $$$(x, y)$$$ to $$$(x + A[i], y)$$$
  • Move right by $$$B[i]$$$ columns: from $$$(x, y)$$$ to $$$(x, y + B[i])$$$
  • Move diagonally down-right by $$$C[i]$$$ cells: from $$$(x, y)$$$ to $$$(x + C[i], y + C[i])$$$

Each such move has a cost of $$$1$$$.

You are also guaranteed that each of the arrays $$$A$$$,$$$B$$$ and $$$C$$$ contain $$$1$$$.

You are given the integers $$$n$$$, $$$m$$$, $$$k$$$ and the arrays $$$A$$$, $$$B$$$, and $$$C$$$, each of length $$$k$$$. Your task is to compute the minimum cost to reach cell $$$(n, m)$$$ starting from $$$(1, 1)$$$.

$$$n,m,k\leq 10^3$$$

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

»
11 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
11 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

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

won't just dp[i][j] work here for each operation? (in $$$O(n^2 \times m)$$$) also i guess you can model it was a graph and do BFS, there can be at most $$$n^2 \times m^2$$$ edges (which is tight but passable)

→ Reply
»
11 months ago, hide # |
← Rev. 2  
Vote: I like it +3 Vote: I do not like it

If m = 1 you basically have the coin change problem with where you are at (1, 1) and have to move to (n, 1) in minimum amount of moves using allowed moves. The better known solution for this problem is O(n*k), so I guess we can't do much better than O(n*m*k) (basically doing a dp and checking all posible transitions on every cell). One thing we can notice is that the answer is ≤ n + m — 2, so maybe a BFS would be better in the worst possible case:

const int INF = 1e9;
function<int(int,int)> coord2node = [&](int x, int y){
  return x * (n+1) + y;
};
function<pair<int,int>(int)> node2coord = [&](int u){
  return make_pair(u / (n+1), u % (n+1));
};
vector<vector<int>> queue(n + m - 1, vector<int>());
vector<bool> processed((n+1) * (m+1), false);
queue[0].push_back(coord2node(1,1));
for(int dist = 0; dist <= n + m - 2; dist++)
  for(int u : queue[dist]){
    if(processed[u]) continue;
    processed[u] = true;
    auto [x, y] = node2coord(u);
    if(x == n && y == m) return dist;
    for(int a_i : A)
      if(x + a_i <= n)
        queue[dist+1].push_back(coord2node(x + a_i, y));
    for(int b_i : B)
      if(y + b_i <= m)
        queue[dist+1].push_back(coord2node(x, y + b_i));
    for(int c_i : C)
      if(x + c_i <= n && y + c_i <= m)
        queue[dist+1].push_back(coord2node(x + c_i, y + c_i));
  }
→ Reply
  • »
    »
    11 months ago, hide # ^ |
     
    Vote: I like it +3 Vote: I do not like it

    The idea here is: if k is big the BFS will stop at an early distance (compensating the extra cost of checking a lot of transitions). If k is small than we have O(E) = O(n*m*k) which should be ok since k is small. I am not sure this actually works though LOL

    → Reply
»
11 months ago, hide # |
 
Vote: I like it +33 Vote: I do not like it

Compute the following in $$$O(n\cdot k) + O(m\cdot k) + O(min(n, m) \cdot k)$$$:

  • dp_down[i] = minimum number of operations to move i steps down
  • dp_right[i] = minimum number of operations to move i steps right
  • dp_diagonal[i] = minimum number of operations to move i steps down and right using only array C

Then the answer is the minimum of dp_diagonal[i] + dp_down[n — i] + dp_right[m — i] for $$$0 \leq i \leq min(n, m)$$$. Overall time complexity: $$$O((n + m) \cdot k)$$$.

→ Reply