USACO 2017 Feb Gold P1

USACO analysis

---

Mark Chen | 27 Nov 2020

报告错误

如果你发现该网页中存在错误/显示异常，可以从以下两种方式向我们报告错误，我们会尽快修复：

1. 使用 CS Club 网站错误 为主题，附上错误截图或描述及网址后发送邮件到 286988023@qq.com
2. 在我们的网站代码仓库中创建一个 issue 并在 issue 中描述问题 点击链接前往Github仓库

Problem 1. Why did the Cow Cross the Road

Problem Description

Bessie the cow wants to move from the upper-left corner of field to the bottom-right corner of field. Each time it goes from one grid to the other, $T$ unit of time will be consumed. Each time Bessie pass through 3 grids, she will stop at the grid and begin eating. The time of eating in each grid is different and will be provided in the input.

$3 \leq N \leq 100, 0\leq T\leq 1\times 10^6$

Proposed Solution

The first thought on this problem is to solve by using Unified Cost Search (UCS). By maintain a fringe of Priority Queue that is sorted according to the time consumes to arrive at a specific position, it is promised that the first state we have met that arrived at the destination will be the state that consumes LEAST time to arrive at the destination.

Therefore, we can represent a State $S$ in this form

State newState = new State(Time, num, x, y);

And accordingly, the state transition function will be somehow like this

public ArrayList<State> StateTransition(State currState){
    int currTime = currState.getTime();
    int num = currState.getNum() + 1;
    int currX = currState.getX();
    int currY = currState.gety();
    
    ArrayList<State> nextStates = new ArrayList<>();
    
    Move[] validMove = this.getValidMove(x, y);
    for (Move move : validMove){
        int nextTime = currTime;
        int[] change = move.getChange();
        nextX = currX + change[0];
        nextY = currY + change[1];
        if (num % 3 == 0){ nextTime += this.Time[nextX][nextY] }
        nextStates.add(new State(nextTime, num, nextX, nextY));
    }
}

Time Complexity Analysis

Since the time that UCS iterate is not bounded explicitly and there does not has an explicit relationship between data scale and number of iteration, it is hard to calculate accurate time complexity. Below, we will try to estimate an upper bound.

First, there are $N^2$ vertexes in the graph, suppose each node is explored for $N$ time (which is an over-estimation), the time complexity of travel through the graph using UCS is $O(N^3)$. Since each state is push and pop from a priority queue that is maintained using binary heap, the time complexity of push & pop one state is $O(\log n)$. The overall time complexity should be less than $O(N^3 \log(n))$.

Since $3\leq N\leq 100$, the time complexity of $O(N^3 \log{n})$ is acceptable.

评论区