EvbCFfp1XB

problem and my answer.

December 2012

problem  AOJ 0530:   Pyon-Pyon River Crossing

how to solve I use dynamic programming.

source code

import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.Scanner;

public class PyonPyonRiverCrossing {
private static boolean test = !true;

public static void main(String[] args) {
if (test) {
testA();
testB();
testC();
for (;;)
testZ();
} else {
run();
}
}

private static void testA() {
test("A", "5 1\n" + "2 1 3 2 2\n" + "1 3 2\n" + "1 1 7\n" + "1 2 1\n"
+ "1 4 4\n", "17");
test("A", "5 1\n" + "1 4 4\n" + "1 2 1\n" + "1 1 7\n" + "1 3 2\n"
+ "2 1 3 2 2\n", "17");
}

private static void testB() {
test("B", "5 0\n" + "2 1 3 2 2\n" + "1 3 2\n" + "1 1 7\n" + "1 2 1\n"
+ "1 4 4\n", "40");
}

private static void testC() {
test("C", "3 2\n" + "3 342 423 267 174 165 534\n"
+ "7 913 448 858 310 763 746 320 199 389 451 859 17 859 284\n"
+ "6 364 144 172 958 542 623 7 690 852 272 479 531\n", "0");
}

private static void testZ() {
StringBuilder sb = new StringBuilder();
int n = 150;
int m = (n + 1) / 2;
sb.append(n + " " + m + "\n");
for (int i = 0; i < n; i++) {
int k = randomInt(0, 10);
sb.append(k);
HashSet<Integer> set = new HashSet<Integer>();
for (int ki = 0; ki < k; ki++) {
int x = randomInt(1, 1000);
int d = randomInt(1, 1000);
while (set.contains(x)) {
x = randomInt(1, 1000);
}
set.add(x);
sb.append(" " + x + " " + d);
}
sb.append("\n");
}
test("Z", sb.toString(), "I'm not sure.");
}

private static int randomInt(int min, int max) {
return min + (int) (((max + 1) - min) * Math.random());
}

private static void test(String id, String input, String output) {
long start = System.nanoTime();
String result = run(input);
double time = (System.nanoTime() - start) / 1e9;
System.out.format("(%s)", output.equals(result) ? id : id
+ " expected:<" + output + "> but was:<" + result + ">");
System.out.format("[%.2f]\n", time);
}

private static String run(String input) {
Scanner sc = new Scanner(input);
int n = sc.nextInt();
int m = sc.nextInt();

int[][][] map = new int[n][][];
for (int i = 0; i < n; i++) {
int k = sc.nextInt();
map[i] = new int[k][2];
for (int j = 0; j < k; j++) {
map[i][j][0] = sc.nextInt();
map[i][j][1] = sc.nextInt();
}
}

long start = System.nanoTime();
String result = solve(n, m, map);
double time = (System.nanoTime() - start) / 1e9;
System.out.format("[%.2f]", time);
start = System.nanoTime();
String result2 = solveDP(n, m, map);
time = (System.nanoTime() - start) / 1e9;
System.out.format("[%.2f]", time);
if (!result.equals(result2)) {
System.out.format("%s\n", input);
System.out.format("result : %s\n", result);
System.out.format("result2 : %s\n", result2);
System.exit(0);
}

sc.close();
return result;
}

private static void run() {
Scanner sc = new Scanner(System.in);
for (; sc.hasNext();) {
int n = sc.nextInt();
int m = sc.nextInt();
if (n == 0 && m == 0) {
break;
}

int[][][] map = new int[n][][];
for (int i = 0; i < n; i++) {
int k = sc.nextInt();
map[i] = new int[k][2];
for (int j = 0; j < k; j++) {
map[i][j][0] = sc.nextInt();
map[i][j][1] = sc.nextInt();
}
}
String result = solve(n, m, map);
System.out.print(result + "\n");
}
sc.close();
}

private static int[][][] dp;

private static String solveDP(int n, int m, int[][][] map) {
dp = new int[n + 1][][];
for (int i = 0; i < n; i++) {
dp[i] = new int[map[i].length][m + 1];
}
dp[n] = new int[1][m + 1];

for (int i = 0; i < dp.length; i++) {
for (int j = 0; j < dp[i].length; j++) {
for (int jump = 0; jump < dp[i][j].length; jump++) {
if (i == 0) {
dp[i][j][jump] = 0;
continue;
}
if (i == 1 && jump + 1 <= m) {
dp[i][j][jump] = 0;
continue;
}
if (i == n) {
int min = Integer.MAX_VALUE;
for (int j2 = 0; j2 < dp[i - 1].length; j2++) {
if (dp[i - 1][j2][jump] == Integer.MAX_VALUE) {
continue;
}
min = Math.min(min, dp[i - 1][j2][jump]);
}
if (jump + 1 <= m) {
for (int j2 = 0; j2 < dp[i - 2].length; j2++) {
if (dp[i - 2][j2][jump + 1] == Integer.MAX_VALUE) {
continue;
}
min = Math.min(min, dp[i - 2][j2][jump + 1]);
}
}
dp[i][j][jump] = min;
continue;
}
int min = Integer.MAX_VALUE;
int w = map[i][j][0];
int d = map[i][j][1];
for (int j2 = 0; j2 < map[i - 1].length; j2++) {
if (dp[i - 1][j2][jump] == Integer.MAX_VALUE) {
continue;
}
int prevj = map[i - 1][j2][0];
int prevd = map[i - 1][j2][1];
min = Math.min(min, risk(prevj, prevd, w, d)
+ dp[i - 1][j2][jump]);
}
if (jump + 1 <= m) {
for (int j2 = 0; j2 < map[i - 2].length; j2++) {
if (dp[i - 2][j2][jump + 1] == Integer.MAX_VALUE) {
continue;
}
int prevj = map[i - 2][j2][0];
int prevd = map[i - 2][j2][1];
min = Math.min(min, risk(prevj, prevd, w, d)
+ dp[i - 2][j2][jump + 1]);
}
}
dp[i][j][jump] = min;
}
}
}

int min = dp[n][0][0];

return min == Integer.MAX_VALUE ? "-1" : "" + min;
}

private static String solve(int n, int m, int[][][] map) {
return "" + priorityFirstSearch(n, m, map);
}

private static int priorityFirstSearch(int n, int m, int[][][] map) {
PriorityQueue<Data> list = new PriorityQueue<Data>();
HashSet<Data> used = new HashSet<Data>();
{
for (int j = 0; j < map[0].length; j++) {
int d = map[0][j][1];
Data data = new Data(0, j, 0, m, d);
list.add(data);
used.add(data);
}
}
if (m - 1 >= 0) {
for (int j = 0; j < map[1].length; j++) {
int d = map[1][j][1];
Data data = new Data(1, j, 0, m - 1, d);
list.add(data);
used.add(data);
}
}
for (; !list.isEmpty();) {
Data data = list.poll();
if (data.i == n) {
return data.d;
}

{
if (data.i + 1 == n) {
Data next = new Data(data.i + 1, 0, data.d, data.m, 0);
if (!used.contains(next)) {
list.add(next);
used.add(next);
}
} else {
for (int j = 0; j < map[data.i + 1].length; j++) {
int w = map[data.i + 1][j][0];
int d = map[data.i + 1][j][1];
int prevw = map[data.i][data.j][0];
Data next = new Data(data.i + 1, j, data.d
+ risk(prevw, data.prevd, w, d), data.m, d);
if (!used.contains(next)) {
list.add(next);
used.add(next);
}
}
}
}
if (data.m - 1 >= 0 && data.i + 2 <= n) {
if (data.i + 2 == n) {
Data next = new Data(data.i + 2, 0, data.d, data.m - 1, 0);
if (!used.contains(next)) {
list.add(next);
used.add(next);
}
} else {
for (int j = 0; j < map[data.i + 2].length; j++) {
int w = map[data.i + 2][j][0];
int d = map[data.i + 2][j][1];
int prevw = map[data.i][data.j][0];
Data next = new Data(data.i + 2, j, data.d
+ risk(prevw, data.prevd, w, d), data.m - 1, d);
if (!used.contains(next)) {
list.add(next);
used.add(next);
}
}
}
}
}
return -1;
}

private static class Data implements Comparable<Data> {
public int i;
public int j;
public int d;
public int m;
public int prevd;

public Data(int i, int j, int d, int m, int prevd) {
this.i = i;
this.j = j;
this.d = d;
this.m = m;
this.prevd = prevd;
final int prime = 31;
int result = 1;
result = prime * result + i;
result = prime * result + j;
result = prime * result + m;
hash = result;
}

int hash;

@Override
public int hashCode() {
return hash;
}

@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Data other = (Data) obj;
if (i != other.i)
return false;
if (j != other.j)
return false;
if (m != other.m)
return false;
if (d < other.d)
return false;
if (prevd != other.prevd)
return false;
return true;
}

@Override
public int compareTo(Data o) {
if (d < o.d) {
return -1;
}
if (d > o.d) {
return 1;
}
if (i < o.i) {
return 1;
}
if (i > o.i) {
return -1;
}
return 0;
}
}

private static int risk(int prevj, int prevd, int j, int d) {
return Math.abs(prevj - j) * (prevd + d);
}
}

problem AOJ 0520:   Lightest Mobile

how to solve I use memoized depth-first search.

source code

import java.util.HashMap;
import java.util.Scanner;

public class LightestMobile {
private static boolean test = !true;

public static void main(String[] args) {
if (test) {
testA();
testB();
for (;;)
testZ();
} else {
run();
}
}

private static void testA() {
test("A", "1\n" + "6 9 0 0\n", "5");
}

private static void testB() {
test("B",
"4\n" + "3 2 0 4\n" + "1 3 0 0\n" + "4 4 2 1\n" + "2 2 0 0\n",
"40");
}

private static void testZ() {
StringBuilder sb = new StringBuilder();
int n = 100;
sb.append(n + "\n");
for (int i = 0, next = 2; i < n; i++) {
int p = randomInt(1, 10);
int q = randomInt(1, 10);
int r = Math.random() > 0.5 ? 0 : next;
if (next == n || next == 0) {
next = 0;
} else {
next++;
}
int b = Math.random() > 0.5 ? 0 : next;
if (next == n || next == 0) {
next = 0;
} else {
next++;
}

sb.append(p + " " + q + " " + r + " " + b + "\n");
}
test("Z", sb.toString(), "I'm not sure.");
}

private static int randomInt(int min, int max) {
return min + (int) (((max + 1) - min) * Math.random());
}

private static void test(String id, String input, String output) {
System.out.format("%s\n", input.trim());
long start = System.nanoTime();
String result = run(input);
double time = (System.nanoTime() - start) / 1e9;
System.out.format("(%s)", output.equals(result) ? id : id
+ " expected:<" + output + "> but was:<" + result + ">");
System.out.format("[%.2f]\n", time);
}

private static String run(String input) {
Scanner sc = new Scanner(input);
int n = sc.nextInt();

int[][] mobile = new int[n][4];
for (int i = 0; i < mobile.length; i++) {
for (int j = 0; j < mobile[i].length; j++) {
mobile[i][j] = sc.nextInt();
}
}
String result = solve(n, mobile);
sc.close();
return result;
}

private static void run() {
Scanner sc = new Scanner(System.in);
for (; sc.hasNext();) {
int n = sc.nextInt();
if (n == 0) {
break;
}

int[][] mobile = new int[n][4];
for (int i = 0; i < mobile.length; i++) {
for (int j = 0; j < mobile[i].length; j++) {
mobile[i][j] = sc.nextInt();
}
}
String result = solve(n, mobile);
System.out.print(result + "\n");
}
sc.close();
}

private static String solve(int n, int[][] mobile) {
map.clear();
long max = 0;
for (int i = 0; i < n; i++) {
max = Math.max(max, minWeight(i, n, mobile));
}
return "" + max;
}

private static HashMap<Integer, Long> map = new HashMap<Integer, Long>();

private static long minWeight(int index, int n, int[][] mobile) {
{
Long v = map.get(index);
if (v != null) {
return v;
}
}
long redLength = mobile[index][0];
long blueLength = mobile[index][1];
int redMobile = mobile[index][2];
int blueMobile = mobile[index][3];

{
long gcd = gcd(redLength, blueLength);
redLength /= gcd;
blueLength /= gcd;
}

long redWeight;
long blueWeight;

if (redMobile == 0) {
if (blueMobile == 0) {
redWeight = 1;
blueWeight = 1;
} else {
blueWeight = minWeight(blueMobile - 1, n, mobile);
redWeight = 1;
}
} else {
if (blueMobile == 0) {
redWeight = minWeight(redMobile - 1, n, mobile);
blueWeight = 1;
} else {
redWeight = minWeight(redMobile - 1, n, mobile);
blueWeight = minWeight(blueMobile - 1, n, mobile);
}
}
long blueCoef = blueWeight * blueLength;
long redCoef = redWeight * redLength;
if (redCoef == blueCoef) {
} else {
{
long gcd = gcd(redCoef, blueCoef);
redCoef /= gcd;
blueCoef /= gcd;
}
redWeight = redWeight * blueCoef;
blueWeight = blueWeight * redCoef;
}
if (redWeight * redLength == blueWeight * blueLength) {
// System.out.format("OK %d * %d == %d * %d\n", redWeight,
// redLength,
// blueWeight, blueLength);
} else {
System.err.format("NG %d * %d == %d * %d\n", redWeight, redLength,
blueWeight, blueLength);
System.exit(0);
}
map.put(index, redWeight + blueWeight);
return redWeight + blueWeight;
}

private static long gcd(long a, long b) {
if (a < 0 || b < 0) {
System.err.println("error");
a = Math.abs(a);
b = Math.abs(b);
}
return a < b ? gcd(b, a) : (b == 0 ? a : gcd(b, a % b));
}
}

このページのトップヘ