HackerRank Two Robots problem solution

In this HackerRank Two Robots problem solution, 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, Ma and Mb, respectively. To execute a query, a robot travels to container Ma, picks up 1 candy, transports it to container Mb, and then stops at Mb until it receives another query.

Calculate the minimum total distance the robots must travel to execute N queries in order.

Problem solution in Python.

def twoRobots(m, queries):
    prev_bot = queries[0][0]
    mintotal = 0
    
    containers = [0]*(m+1)

    for a,b in queries:
        distance = abs(a-b)
        traveled = abs(prev_bot-a)
        minMoves = mintotal
        for k,v in enumerate(containers):
            minMoves = min( minMoves, abs(k-a)+v)
            containers[k] += traveled+distance
        containers[prev_bot] = minMoves+distance
        mintotal += traveled+distance
        prev_bot = b
    return min(containers)
    
for t in range(int(input().strip())):
    m,n=(map(int,input().rstrip().split()))
    queries = []
    for _ in range(n):
        queries.append(tuple(map(int, input().rstrip().split())))
    print(twoRobots(m, tuple(queries)))

Problem solution in Java.

// practice with kaiboy
import java.io.*;
import java.util.*;

public class two_robots extends PrintWriter {
    two_robots() { super(System.out); }
    Scanner sc = new Scanner(System.in);
    public static void main(String[] $) {
        two_robots o = new two_robots(); o.main(); o.flush();
    }

    static final int INF = 0x3f3f3f3f;
    void main() {
        int t = sc.nextInt();
        while (t-- > 0) {
            int m = sc.nextInt();
            int n = sc.nextInt();
            int[] aa = new int[n];
            int[] bb = new int[n];
            for (int i = 0; i < n; i++) {
                aa[i] = sc.nextInt();
                bb[i] = sc.nextInt();
            }
            int[] dd = new int[n];
            dd[0] = Math.abs(aa[0] - bb[0]);
            for (int i = 1; i < n; i++)
                dd[i] = dd[i - 1] + Math.abs(bb[i - 1] - aa[i]) + Math.abs(aa[i] - bb[i]);
            int ans = dd[n - 1];
            int[][] dp = new int[n][m + 1];
            for (int i = 0; i < n; i++)
                for (int x = 1; x <= m; x++)
                    dp[i][x] = INF;
            for (int u = 1; u < n; u++)
                for (int v = 1; u + v <= n; v++) {
                    int i = u + v - 1;
                    int x = bb[u - 1];
                    dp[i][x] = Math.min(dp[i][x], dd[u + v - 1] - Math.abs(bb[u - 1] - aa[u]));
                }
            for (int i = 0; i < n - 1; i++)
                for (int x = 1; x <= m; x++) {
                    int d = dp[i][x];
                    if (d == INF)
                        continue;
                    int y = bb[i];
                    dp[i + 1][x] = Math.min(dp[i + 1][x], d + Math.abs(y - aa[i + 1]) + Math.abs(aa[i + 1] - bb[i + 1]));
                    dp[i + 1][y] = Math.min(dp[i + 1][y], d + Math.abs(x - aa[i + 1]) + Math.abs(aa[i + 1] - bb[i + 1]));
                }
            for (int x = 1; x <= m; x++)
                ans = Math.min(ans, dp[n - 1][x]);
            println(ans);
        }
    }
}

Problem solution in C++.

#define _CRT_SECURE_NO_WARNINGS

#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>

using namespace std;

const int Infinity = 1000000007;
const int NotInit = -1;

struct Query {
	int from, to, dist;

	Query(int from = 0, int to = 0, int dist = 0)
		: from(from),
		  to(to),
		  dist(dist) {}

	void scan() {
		scanf("%d%d", &from, &to);
		dist = abs(from - to);
	}
};

vector<Query> queries;
vector<vector<int>> dp;

int minDistance(int x, int y) {
	if (dp[x][y] != NotInit)
		return dp[x][y];
	int result = Infinity;
	auto queryId = max(x, y);
	auto& query = queries[queryId];
	if (min(x, y) + 1 < queryId) {
		result = x == queryId 
			? minDistance(x - 1, y) 
			: minDistance(x, y - 1);
		result += query.dist;
		result += abs(queries[queryId - 1].to - query.from);
	}
	else {
		for (int i = 0; i < queryId-1; ++i) {
			int prevDistance = x == queryId 
				? minDistance(i, y) 
				: minDistance(x, i);
			int newDistance = i == 0 ? 0 : abs(query.from - queries[i].to);
			result = min(result, prevDistance + newDistance + query.dist);
		}
	}
	dp[x][y] = result;
	return result;
}

void solve() {
	int n, m;
	scanf("%d%d", &m, &n);
	queries.resize(n+1);
	for (int i = 1; i <= n; ++i) {
		queries[i].scan();
	}

	dp.resize(n+1);
	for (int i = 0; i <= n; ++i) {
		dp[i].assign(n+1, NotInit);
	}
	dp[0][1] = queries[1].dist;
	dp[1][0] = queries[1].dist;

	int ans = Infinity;
	for (int i = 0; i <= n; ++i) {
		ans = min(ans, minDistance(i, n));
		ans = min(ans, minDistance(n, i));
	}
	printf("%dn", ans);
}

int main(void) {
	//freopen("input.txt", "rt", stdin);
	//freopen("output.txt", "wt", stdout);

	int t;
	scanf("%d", &t);
	while(t --> 0) {
		solve();
	}

	return 0;
}

Problem solution in C.

#include<stdio.h>
int main()
{
    int t, k;
    scanf("%d", &t);
    for( k = 0 ; k < t ; k++ )
    {
        int m, n, i, j, a, b;
        scanf("%d %d", &m, &n);
        int ar[m+1], r2 = 0, temp, min;
        for( j = 0 ; j <= m ; j++ )
        {
            ar[j] = 0;
        }
        for( i = 0 ; i < n ; i++ )
        {
            scanf("%d %d", &a, &b);
            min = ar[0] + abs(a-b);
            for( j = 1 ; j <= m ; j++ )
            {
                if( ar[j] == 0 )
                {
                    continue;
                }
                temp = ar[j] + abs(j-a) + abs(a-b);
                if( temp < min )
                {
                    min = temp;
                }
            }
            if( r2 == 0 )
            {
                temp = abs(a-b);
            }
            else
            {
                temp = abs(r2-a) + abs(a-b);
            }
            ar[0] += temp;
            for( j = 1 ; j <= m ; j++ )
            {
                if( ar[j] == 0 )
                {
                    continue;
                }
                ar[j] += temp;
            }
            if( ar[r2] == 0 || ar[r2] > min )
            {
                ar[r2] = min;
            }
            r2 = b;
        }
        min = ar[0];
        for( j = 1 ; j <= m ; j++ )
        {
            if( ar[j] != 0 && ar[j] < min )
            {
                min = ar[j];
            }
        }
        printf("%dn", min);
    }
    return 0;
}