HackerRank Two Robots Problem Solution

#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("%d\n", min);
    }
    return 0;
}

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <tuple>

// #include "debug.h"

using namespace std;

typedef unsigned int u32;

typedef pair<int, int> query_t;
typedef vector<query_t> query_array_t;
typedef tuple<int, int, int> tuple_t;
typedef unordered_map<int, int> memo_hash_table_t;

union _ {
    struct {
        u32 i : 10;
        u32 iRobot0 : 10;
        u32 iRobot1 : 10;
        u32 unused : 2;
    };
    u32 value;

    _(tuple_t const& t) : i(get<0>(t)), iRobot0(get<1>(t)), iRobot1(get<2>(t)), unused(0) {}
};

int recursive(const query_array_t& q, int i, int iRobot0, int iRobot1) {
    if (i >= q.size()) {
        return 0;
    }

    int distance[2];
    distance[0] = distance[1] = abs(q[i].first - q[i].second);
    if (iRobot0 > 0) {
        distance[0] += abs(q[iRobot0].second - q[i].first);
    }
    distance[1] += abs(q[iRobot1].second - q[i].first);

    distance[0] += recursive(q, i+1, i, iRobot1);
    distance[1] += recursive(q, i+1, iRobot0, i);

    return min(distance[0], distance[1]);
}

int recursive(const query_array_t& q) {
    return abs(q[1].first - q[1].second) + recursive(q, 2, 0, 1);
}

int memoize_hash_table(memo_hash_table_t& memo, const query_array_t& q, int i, int iRobot0, int iRobot1) {
    if (i >= q.size()) {
        return 0;
    }
    if (iRobot0 > iRobot1) {
        swap(iRobot0, iRobot1);
    }

    const int memoKey = _(make_tuple(i, iRobot0, iRobot1)).value;
    auto it = memo.find(memoKey);
    if (it != memo.end()) {
        return it->second;
    }

    int distance[2];
    distance[0] = distance[1] = abs(q[i].first - q[i].second);
    if (iRobot0 > 0) {
        distance[0] += abs(q[iRobot0].second - q[i].first);
    }
    distance[1] += abs(q[iRobot1].second - q[i].first);

    distance[0] += memoize_hash_table(memo, q, i+1, i, iRobot1);
    distance[1] += memoize_hash_table(memo, q, i+1, iRobot0, i);

    int minTotalDistance = min(distance[0], distance[1]);
    memo.insert({memoKey, minTotalDistance});

    return minTotalDistance;
}

int memoize_hash_table(const query_array_t& q) {
    memo_hash_table_t memo;
    memo.reserve(262144);

    return abs(q[1].first - q[1].second) + memoize_hash_table(memo, q, 2, 0, 1);
}

int dp(const query_array_t& q) {
    vector< vector<int> > memo(q.size()+1);
    memo[q.size()] = vector<int>(q.size());
    for (int j=q.size()-1; j>0; j--) {
        // init memo[j] to |Ma - Mb|
        memo[j] = vector<int>(j, abs(q[j].second - q[j].first));

        for (int i=0; i<j; i++) {
            /** iRobot0 is at q[i], and iRobot1 is at q[j-1]. Two executions can occur:
             *  1) iRobot0 executes q[j] and iRobot1 stays put at q[j-1].
             *  2) iRobot1 executes q[j] and iRobot0 stays put at q[i].
             */

            int iRobot0 = (i>0 ? abs(q[i].second - q[j].first) : 0) + memo[j+1][j-1];
            int iRobot1 = abs(q[j-1].second - q[j].first) + memo[j+1][i];
            memo[j][i] += min(iRobot0, iRobot1);
        }
    }

    return memo[1][0];
}

int main() {
    int T;
    cin >> T;

    while (T--) {
        // M number of containers
        // N number of queries
        int M, N;
        cin >> M >> N;

        query_array_t q(N+1);
        for (int i=1; i<q.size(); i++) {
            cin >> q[i].first >> q[i].second;
        }

        // cout << recursive(q) << endl;
        // cout << memoize_hash_table(q) << endl;
        cout << dp(q) << endl;
    }

    return 0;
}

using System.CodeDom.Compiler;
using System.Collections.Generic;
using System.Collections;
using System.ComponentModel;
using System.Diagnostics.CodeAnalysis;
using System.Globalization;
using System.IO;
using System.Linq;
using System.Reflection;
using System.Runtime.Serialization;
using System.Text.RegularExpressions;
using System.Text;
using System;

class Result
{

    /*
     * Complete the 'twoRobots' function below.
     *
     * The function is expected to return an INTEGER.
     * The function accepts following parameters:
     *  1. INTEGER m
     *  2. 2D_INTEGER_ARRAY queries
     */

    public static int twoRobots(int m, List<List<int>> queries)
    {
        //don't need to move to first container as stated
    var lastCon = queries.First()[0];
    //special case container naught, as machine doesn't move to first container
    //could special case at moves computation, but that would require if in loop
    var movesAtCon0 = 0;
    //store minimum required moves to leave a machine at each container visited
    var movesAtCon = new Dictionary<int, int>();

    foreach (var q in queries)
    {
        var fromCon = q[0];
        var toCon = q[1];

        var dist = Math.Abs(fromCon - toCon);
        var movesFromLast = Math.Abs(lastCon - fromCon) + dist;

        //find the minimum moves to leave machine at last
        var minMoves = movesAtCon0;
        foreach (var conToMoves in movesAtCon.ToList())
        {
            minMoves = Math.Min(minMoves, Math.Abs(conToMoves.Key - fromCon) + conToMoves.Value);

            //increase min moves to leave at this container
            movesAtCon[conToMoves.Key] += movesFromLast;
        }
        movesAtCon[lastCon] = minMoves + dist;

        //don't forget to update moves required to leave a machine at container naught
        movesAtCon0 += movesFromLast;

        lastCon = toCon;
    }
    //don't need to min with moves at con naught, it could only be tied for min
    return movesAtCon.Values.Min();
    }
}

class Solution
{
    public static void Main(string[] args)
    {
        TextWriter textWriter = new StreamWriter(@System.Environment.GetEnvironmentVariable("OUTPUT_PATH"), true);

        var testCases = Convert.ToInt32(Console.ReadLine().Trim());
        for (var t = 0; t < testCases; t++)
        {
            string[] firstMultipleInput = Console.ReadLine().TrimEnd().Split(' ');
            var m = Convert.ToInt32(firstMultipleInput[0]);
            var n = Convert.ToInt32(firstMultipleInput[1]);

            List<List<int>> queries = new List<List<int>>();
            for (int i = 0; i < n; i++)
            {
                queries.Add(Console.ReadLine().TrimEnd().Split(' ').ToList().Select(queriesTemp => Convert.ToInt32(queriesTemp)).ToList());
            }

            var result = Result.twoRobots(m, queries);
            textWriter.WriteLine(result);
        }

        textWriter.Flush();
        textWriter.Close();
    }
}

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);
        }
    }
}

'use strict';

const fs = require('fs');

process.stdin.resume();
process.stdin.setEncoding('utf-8');

let inputString = '';
let currentLine = 0;

process.stdin.on('data', function(inputStdin) {
    inputString += inputStdin;
});

process.stdin.on('end', function() {
    inputString = inputString.split('\n');

    main();
});

function readLine() {
    return inputString[currentLine++];
}

/*
 * Complete the 'twoRobots' function below.
 *
 * The function is expected to return an INTEGER.
 * The function accepts following parameters:
 *  1. INTEGER m
 *  2. 2D_INTEGER_ARRAY queries
 */

function twoRobots(m, queries) {
    // Write your code here
    /**
     * [0,1,2,3,4...m]
     * (1,5),(3,2),(4,1),(2,4)
     * 
     * this problem can be done with O(NM) time and O(N) space dynamic programming
at the end of query k, we know that one of the robots will certainly be at position query[k][1]. We want to figure out the smallest distance travelled given that the other one is at some other position x, and we want to do this for all x.

    dp[i][j] = after query i, the min price when the other robot is at j.
                 if -1, means no way for this to happen
        
    const end = query[i][1]
    for(each j) {
        at the end of prev query
        dp[i-1][j] = minDist
        From [query[i-1][1], j] 
        let query[i-1][1] = k
            move k to query[i][1] and j remains
                populate dp[i][j]
            or move j to query[i][1], k remains
                populate dp[i][k]
    }
    
     */
    const n = queries.length;
    const distOfQuery = (i) => Math.abs(queries[i][0] - queries[i][1]);
    const distToQueryFrom = (from, i) => Math.abs(from - queries[i][0]);
    const dp = Array(n).fill().map(() => Array(m+1).fill(Number.MAX_SAFE_INTEGER));
    
    for(let i=1; i<=m; i++) {
        dp[0][i] = distOfQuery(0); //after query i, the other robot can be at any position
    }
    
    for(let i=1; i<n; i++) {
        const queryCost = distOfQuery(i);
        for(let j=1; j<=m; j++) {
            const prevCost = dp[i-1][j];
            //at last query, there's no way for the other robot to be at j
            if(prevCost=== Number.MAX_SAFE_INTEGER) continue;
            
            const k = queries[i-1][1];
            //after last query, one robot at k, the other at j
            //can move from (k, j) => (end, k | j)
            
            //move k -> end
            dp[i][j] = Math.min(dp[i][j], distToQueryFrom(k, i) + queryCost + prevCost);
            
            //move j -> end
            dp[i][k] = Math.min(dp[i][k], distToQueryFrom(j, i) + queryCost + prevCost);
        }   
    }
    let ans = Number.MAX_SAFE_INTEGER;
    for(let j=1; j<=m; j++) {
        ans = Math.min(ans, dp[n-1][j]);
    }
    
    return ans;
}

function main() {
    const ws = fs.createWriteStream(process.env.OUTPUT_PATH);

    const t = parseInt(readLine().trim(), 10);
    for(let i=0; i<t; i++) {
        const firstMultipleInput = readLine().replace(/\s+$/g, '').split(' ');

        const m = parseInt(firstMultipleInput[0], 10);

        const n = parseInt(firstMultipleInput[1], 10);

        let queries = Array(n);

        for (let i = 0; i < n; i++) {
            queries[i] = readLine().replace(/\s+$/g, '').split(' ').map(queriesTemp => parseInt(queriesTemp, 10));
        }

        const result = twoRobots(m, queries);

        ws.write(result + '\n');        
    }


    ws.end();
}

#!/bin/python3

import os
import sys

''' 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()) '''
def twoRobots(m, queries):
    N = len(queries)
    DP = [[float('inf')]*(N+1) for i in range(N+1)]
    DP[-1] = [0]*len(DP[-1])
    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] = abs(q0-q1) + min(abs(r1-q0) + DP[i+1][j], abs(r2-q0) + DP[i+1][i-1])
    return min(DP[1]) +  abs(queries[0][0] - queries[0][1])

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    t = int(input())
    for case in range(t):
        mn = input().split()

        m = int(mn[0])

        n = int(mn[1])

        queries = []

        for _ in range(n):
            queries.append(list(map(int, input().rstrip().split())))

        result = twoRobots(m, queries)

        fptr.write(str(result) + '\n')

    fptr.close()