Pedro Matias

About Archive

HackerRank Week of Code 19 (Part I)

This is the first of a series of posts I plan to write about one of the first programming contests I have competed in, HackerRank’s Week of Code 19. The set of problems was quite interesting and they were released one at a time every day throughout the week, in increasing order of difficulty.

I will skip the first problem, because it’s a warmup kind of question. The second problem is called Two Robots and goes like this:

You have a warehouse with $M$ containers filled with an infinite number of candies. The containers are arranged in a single row, equally spaced to be $1$ meter apart. You also have $2$ robots that can pick up $1$ piece of candy and transport it between any two containers.
The robots take instructions in the form of queries consisting of two integers, $M_a$ and $M_b$, respectively. To execute a query, a robot travels to container $M_a$, picks up $1$ candy, transports it to container $M_b$, and then stops at $M_b$ until it receives another query.
Calculate the minimum total distance the robots must travel to execute $N$ queries in order.

Note: For the first query a robot executes, there is no travel distance. For each subsequent query that robot executes, it must travel from the location where it completed its last query.

(For details on the problem size and input/output samples, check the original problem formulation.)

Solution

The trivial $O(2^N)$ solution would be to enumerate every possible assignment of queries to robots and then simulate their execution by the order given in the input (which is the required one). Naturally, this wasn’t enough to get AC.

One could also think of a greedy strategy to solve the problem, such as iterating over the queries (in order) and, to each of them, assign the robot which travels less to execute it, based on its current position. But the following counter-example proves it wrong.

To avoid spoils and let you think on the problem without accidentally looking through the solution, you need to press the button below to reveal it.

Partitioning the problem

A common technique to solve a problem is to break it down into a simpler ones. In this case, the problem size is directly given by $N=\text{#queries}$, so we probably need to break our problem down using this criteria. Luckily, we don’t need to worry about the order through which queries get executed, since it is fixed by the input.

Let’s use the following notation, to simplify our reasoning:

  • $S_i$ ($T_i$) is the container from (to) which candies need to be taken (delivered) in the $i$th query.

Now, imagine that we are left with $1$ query and that the robots are in positions $x$ and $y$. Can we solve the problem easily? In this case, it is trivial to see how: just pick the robot whose distance to $S_{N}$ is smaller.

Following the same reasoning, if we were to execute the $i$th query and the robots were in positions $x’$ and $y’$, then we would choose the one which minimises the distance it needs to travel to execute this query, plus the total distance needed in the remaining sub-problem (notice that the position of one of the robots has changed, as well as the next query to be executed).

Hence, each of our sub-problems can be identified by $3$ parameters and we can solve each one of them through a recurrence relation, formalised as follows:

As for base cases, we have that: $\mathcal{P}(N+1,x,y)=0 \; (\forall \; 1 \le x,y \le M)$. The optimal solution is given by $\min_{1 \le x,y \le M} \mathcal{P}(1,x,y)$.

By now, you’re probably already seeing where this is going (*cof* DP *cof*). With the above relation, we established the property of optimal substructure. It is also easy to see how we can have overlapping subproblems, so we can take advantage of memoization and, hence, dynamic programming.

Complexity

The time complexity for filling up the DP table (and thus computing the optimal solution) is $O(NM^2)$ (think about the range of all parameters). However, we can improve it to $O(N^2)$, assuming $N \ll M$, by making use of the following observation.

Observation. For every subproblem $\mathcal{P}(i,x,y)$, the positions $x$ and $y$ of each robot correspond always to some $T_k$ s.t. $1 \le k \lt i$ (already executed queries). In addition, it must be the case that one of the robots is at position $T_{i-1}$. The only exception to this rule is when no query has been executed yet, in which case the robots can be at any position.

Then, each subproblem can simply be represented by:


, where:

  • $1 \le i \le N$ denotes the next query to be executed
  • $0 \le j \lt i$ denotes the last query executed by the robot which is inactive by a longer time. If $j=0$, then it hasn’t executed any query yet.
  • the base cases and the optimal solution are both computed in a way similar to the recurrence in \eqref{dp1}

Improved complexity

The number of DP entries to be computed is directly given by the ranges of the variables $i$ and $j$. Moreover, it takes O(1) time to compute each of them. Thus, the overall time complexity is:

Code

The code is written in Python3. The input format is explained here.

def solve():
  DP = [[float('inf')]*(N+1) for i in range(N+1)]
  DP[-1] = [0] * len(DP[-1])  # base case
  for i in range(N-1, 0, -1):
    r1 = queries[i-1][1]
    q0, q1 = queries[i]
    for j in range(-1,i):
      r2 = queries[j][1] if j >= 0 else q0
      DP[i][j] = min(abs(r1-q0) + DP[i+1][j], abs(r2-q0) + DP[i+1][i-1])\
                 + abs(q0-q1)
  return min(DP[1]) + abs(queries[0][0] - queries[0][1])

if __name__ == '__main__':
  for t in range(eval(input())):
    M, N = map(int, input().split())
    queries = [[int(x) for x in input().split()] for _ in range(N)]
    print(solve())