Main course - the spider delivery man

(Leetcoders, enjoy this above-hard problem :))

First, please watch this.

The spider delivery man has a problem. He is responsible of all the delivery works on Main Street. The delivery app recently had a major update of its algorithm, forcing delivery people to work as efficiently as possible. The spider delivery man wants to plan the routes accordingly, so that he would not lose the job to help citizens.

The main street has a row of $N$ houses. The $i$th house has $H_i$ floors above ground. The first house is a warehouse and the spider delivery man always starts from the top floor of it. Also, the warehouse and the $N$th house at the other end of the street are the highest houses. An example is displayed as belows.

In this example, $N=5$ and $H=\{5,4,3,3,5\}$. When the spider delivery man needs to deliver a pizza to another house on the street, he will start at the top of the warehouse, plan a route to land at any floor of the target house to finish the job. He has several options in a route:

• 1 unit of time to go down one floor;
• 1 unit of time to go up one floor;
• 1 unit of time to “fly” to a building on the right on the same floor, without passing another house;
• 1 unit of time to “fly” to a building on the left on the same floor, without passing another house.

For example, if he is delivering to Carol’s house, he could choose the following route:

• Start from the 5th floor of the warehouse;
• Fly to the 5th floor of David’s house with 1 unit of time;
• Go down 2 floors with 2 units of time;
• Fly left to the 3rd floor of Carol’s house with 1 unit of time.

The total time spent is 4, and you could see that it is optimal. He could not fly from the 3rd floor of the warehouse to Carol’s house directly because it would pass Alice’s and Bob’s houses. The spider delivery man wants to compute the optimal delivery time for each house. Can you think of an algorithm given $N$ and $H_1,…,H_N$? Please aim at $\mathcal{O}(N)$ complexity.

At the first glance, it seems to be a man-made problem just for a contest. But if you are familiar with advanced data structures, you would immediately realize that it is akin to the “skip list”. The skip list is a probabilistic data structure to maintain an ordered linked list, such that each visit in the list can be expectedly done in $\mathcal{O}(\log N)$. The rough idea is to make the height of each house to be a random variable, such that it takes $\mathcal{O}(\log N)$ steps in expectation to reach any of the houses from the warehouse. The difference is that the spider delivery man is allowed to fly in both directions, while in a skip list we could only go down or right. For example, following the skip list, it takes longer to deliver to Carol. The spider delivery man could only go (down, right, down, right, right) to deliver for 5 units of time.

Back to our problem, the $\mathcal{O}(N)$ algorithm is not trivial at all. My draft had been with $\mathcal{O}(N\log N)$ until someone (if you want your name here please let me know) told me the $\log N$ factor could be reduced. To actually solve the problem, there are several important intuitions:

• In the optimal route the spider delivery man should never go up a floor;
• In the optimal route the spider delivery man always delivers to the top floor of a house;
• The time of the optimal route is the time of going down plus the time of flying, and the time of going down is fixed for each house.

For example, to deliver from the warehouse to Carol’s house, the spider delivery man should always spend $5-3=2$ units of time going down. The efficiency depends on how many times he needs to fly left or right. There are more intuitions about the problem:

• In the optimal route, when flying, the spider delivery man always lands at the top of a house;
• To land at the top of a particular house, there are at most two source houses. For example, to land at the top of Alice’s house, he could only fly from the 4th floor of the warehouse or David’s house;
• To compute the optimal route, we only need to consider $2N$ possible flying paths, 2 for each house.

Now I have almost finished the list of important arguments to solve the problem. There are two steps:

• First, we need to get the $2N$ possible flying paths. To reach the top of a house, the spider delivery man can either fly from the closest house to the left that is not lower, or fly from the closest house to the right that is not lower. To get that for all houses, we could use monotonic stacks.
• Then, we need to compute the optimal times for going left and right. We will build a graph $G(V,E)$ where each $v\in V$ represents a house, and each $e\in E$ is a flying path. For my example, $V=\{W, A, B, C, D\}$ and $E=\{W\to A,D\to A,A\to B,C\to B,B\to C,D\to C,W\to D\}$. After computing shortest distances by a single sourced BFS from $W$, we are done.

For the example, the final results are obtained as follows.

The techniques to solve the problem are not complicated. Anyone who can solve the famous “Trapping Rain Water” on Leetcode could potentially solve it. Yet very few actually did in my contest. The actual difficulty is in the important intuitions. They are correct arguments that are tedious to rigorously prove. In most research, intuitions are the sparkling lights and proofs are usually the labor works. In my opinion, they are both important, but I would not go deep for this blog post.

Another comment I want to make is about the delivery apps. Back in China, there was a famous article stating that “delivery people are trapped in the apps”. If someone’s livelihood is dependent on an app, they have handed over their life to a group of software engineers, who may care more about profits. In the US, I have witnessed the power of bargaining against big cooperates. You have to care a lot more than efficiency when developing your software. The missing parts will be eventually reflected on the ballots, which forces the technology to benefit everyone. Thus, the united power of users is important in shaping the modern tech world.