Editing 2016 Jan Gold Problem 2 Radio Contact

== Official Problem Statement ==

[http://www.usaco.org/index.php?page=viewproblem2&cpid=598 Radio Contact]

== Problem ==

John and Bessie are playing a game of hide-and-seek. John and Bessie are starting at different locations and will move according to a sequence of directions. Both John and Bessie have radios. The radios are old and become staticky as John and Bessie move farther apart, and the static gets worse the further they are from each other. The aim is to minimize the sum of the squares of the distances between the two at each time step.

== Solution ==

The problem can be solved using dynamic programming. Let FJ[i][j] denote the minimum static (i.e., the sum of the squares of the distances) when Farmer John is at position i and Bessie is at position j. Both John and Bessie can either stay in their positions or move to the next one. Therefore, there are four possible transitions:

* John moves, Bessie stays
* Bessie moves, John stays
* Both move
* Both stay

For every pair (i, j), compute the four possible transitions and update FJ[i][j] to the minimum value.

Let m and n be the lengths of John's and Bessie's movement sequences. Initialize the dp array FJ with dimensions (m+1) x (n+1) to infinity (as we are trying to minimize static). Set FJ[0][0] to 0, as they start at the same position and the static is 0.

Finally, the answer is the minimum of FJ[i][n] for all i between 0 and m. This is because John might finish his sequence of movements before Bessie.

The time complexity is O(mn), and the space complexity is O(mn), where m is the length of John's sequence and n is the length of Bessie's sequence.

== Code ==

=== C++ ===
<pre>
#include <iostream>
#include <vector>
#include <cstring>
#include <cstdio>
#include <map>

using namespace std;

const long long INF = 0x7FFFFFFFFFFFFFFFLL;

long long memo[1010][1010];

vector<pair<long long, long long>> F;
vector<pair<long long, long long>> B;

long long calculate_min_energy(int fi, int bi) {
  long long base_energy = (F[fi].first - B[bi].first) * (F[fi].first - B[bi].first) +
             (F[fi].second - B[bi].second) * (F[fi].second - B[bi].second);

  if (fi + 1 == F.size() && bi + 1 == B.size()) {
    return base_energy;
  }

  long long& ref = memo[fi][bi];
  if (ref != -1) return ref;

  if (fi == 0 && bi == 0) base_energy = 0;

  ref = INF;
  if (fi + 1 < F.size()) {
    ref = min(ref, base_energy + calculate_min_energy(fi + 1, bi));
  }
  if (bi + 1 < B.size()) {
    ref = min(ref, base_energy + calculate_min_energy(fi, bi + 1));
  }
  if (fi + 1 < F.size() && bi + 1 < B.size()) {
    ref = min(ref, base_energy + calculate_min_energy(fi + 1, bi + 1));
  }
  return ref;
}

int main() {
  freopen("radio.in", "r", stdin);
  freopen("radio.out", "w", stdout);

  map<char, int> dx, dy;
  dx['E'] = 1; dx['W'] = -1;
  dy['N'] = 1; dy['S'] = -1;

  int N, M;
  cin >> N >> M;
  int fx, fy, bx, by;
  cin >> fx >> fy >> bx >> by;
  string SF, SB;
  cin >> SF >> SB;

  F.push_back({fx, fy});
  for (char dir : SF) {
    fx += dx[dir];
    fy += dy[dir];
    F.push_back({fx, fy});
  }

  B.push_back({bx, by});
  for (char dir : SB) {
    bx += dx[dir];
    by += dy[dir];
    B.push_back({bx, by});
  }

  memset(memo, -1, sizeof(memo));
  cout << calculate_min_energy(0, 0) << endl;
  return 0;
}

</pre>

=== Java ===
<pre>
import java.io.*;
import java.util.*;

public class Main {
    private static final long INF = Long.MAX_VALUE;

    private static long[][] memo = new long[1010][1010];
    private static ArrayList<Pair<Long, Long>> F = new ArrayList<>();
    private static ArrayList<Pair<Long, Long>> B = new ArrayList<>();
    private static Map<Character, Integer> dx = new HashMap<>(), dy = new HashMap<>();

    static {
        for (long[] row : memo) Arrays.fill(row, -1);
        dx.put('E', 1); dx.put('W', -1);
        dy.put('N', 1); dy.put('S', -1);
    }

    private static class Pair<T, U> {
        T first;
        U second;

        Pair(T first, U second) {
            this.first = first;
            this.second = second;
        }
    }

    private static long calculateMinEnergy(int fi, int bi) {
        long baseEnergy = (F.get(fi).first - B.get(bi).first) * (F.get(fi).first - B.get(bi).first)
                + (F.get(fi).second - B.get(bi).second) * (F.get(fi).second - B.get(bi).second);

        if (fi + 1 == F.size() && bi + 1 == B.size()) {
            return baseEnergy;
        }

        if (memo[fi][bi] != -1) return memo[fi][bi];

        if (fi == 0 && bi == 0) baseEnergy = 0;

        memo[fi][bi] = INF;
        if (fi + 1 < F.size()) {
            memo[fi][bi] = Math.min(memo[fi][bi], baseEnergy + calculateMinEnergy(fi + 1, bi));
        }
        if (bi + 1 < B.size()) {
            memo[fi][bi] = Math.min(memo[fi][bi], baseEnergy + calculateMinEnergy(fi, bi + 1));
        }
        if (fi + 1 < F.size() && bi + 1 < B.size()) {
            memo[fi][bi] = Math.min(memo[fi][bi], baseEnergy + calculateMinEnergy(fi + 1, bi + 1));
        }
        return memo[fi][bi];
    }

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new FileReader("radio.in"));
        PrintWriter writer = new PrintWriter(new BufferedWriter(new FileWriter("radio.out")));

        String[] parts = reader.readLine().split("\\s+");
        int N = Integer.parseInt(parts[0]);
        int M = Integer.parseInt(parts[1]);
        long fx = Long.parseLong(parts[2]);
        long fy = Long.parseLong(parts[3]);
        long bx = Long.parseLong(parts[4]);
        long by = Long.parseLong(parts[5]);
        String SF = reader.readLine();
        String SB = reader.readLine();

        F.add(new Pair<>(fx, fy));
        for (char dir : SF.toCharArray()) {
            fx += dx.get(dir);
            fy += dy.get(dir);
            F.add(new Pair<>(fx, fy));
        }

        B.add(new Pair<>(bx, by));
        for (char dir : SB.toCharArray()) {
            bx += dx.get(dir);
            by += dy.get(dir);
            B.add(new Pair<>(bx, by));
        }

        writer.println(calculateMinEnergy(0, 0));
        writer.close();
    }
}

</pre>

=== Python ===
<pre>
INF = float('inf')

memo = [[-1 for _ in range(1010)] for _ in range(1010)]

F = []
B = []

dx = {'E': 1, 'W': -1}
dy = {'N': 1, 'S': -1}

def solve(fi, bi):
    base = (F[fi][0] - B[bi][0]) ** 2 + (F[fi][1] - B[bi][1]) ** 2
    if fi + 1 == len(F) and bi + 1 == len(B):
        return base
    if memo[fi][bi] != -1: 
        return memo[fi][bi]
    if fi == 0 and bi == 0: 
        base = 0
    memo[fi][bi] = INF
    if fi + 1 < len(F):
        memo[fi][bi] = min(memo[fi][bi], base + solve(fi + 1, bi))
    if bi + 1 < len(B):
        memo[fi][bi] = min(memo[fi][bi], base + solve(fi, bi + 1))
    if fi + 1 < len(F) and bi + 1 < len(B):
        memo[fi][bi] = min(memo[fi][bi], base + solve(fi + 1, bi + 1))
    return memo[fi][bi]

def main():
    with open('radio.in', 'r') as fin:
        N, M, fx, fy, bx, by = map(int, fin.readline().split())
        SF, SB = fin.readline().strip(), fin.readline().strip()

    F.append((fx, fy))
    for s in SF:
        fx += dx[s]
        fy += dy[s]
        F.append((fx, fy))

    B.append((bx, by))
    for s in SB:
        bx += dx[s]
        by += dy[s]
        B.append((bx, by))

    with open('radio.out', 'w') as fout:
        fout.write(str(solve(0, 0)) + '\n')

if __name__ == "__main__":
    main()

</pre>

[[Category:Yearly_2015_2016]]
[[Category:Gold]]
[[Category:Dynamic Programming]]
[[Category:Geometry]]