Google Code Jam Notes - Meet And Party - Java

Problem:

Retrieved from: https://code.google.com/codejam/contest/2929486/dashboard#s=p1

Little Sin lives in a Manhattan-grid city, a 2D plane where people can only go north, west, south or east along the grid. The distance from (x1, y1) to (x2, y2) is |x1 - x2| + |y1 - y2|.

Little Sin really likes to party and is hoping to host a house party in Manhattan this Sunday. Little Sin has collected a list of people who will attend, and now needs to decide at whose home she will host the party.

Little Sin invited all of the people in several rectangular areas, and all of those people have said yes. A rectangular area is denoted as (x1, y1, x2, y2), where x1 ≤ x2, y1 ≤ y2. People who live in a rectangular area fill all integral points inside it. So there are a total of (x2 - x1 + 1) * (y2 - y1 + 1) people in the rectangular area (x1, y1, x2, y2).

Little Sin knows the coordinates of those rectangular areas. She wants the party to be hosted at the home of one of the people who is attending, but she also doesn't want everyone else to have to travel very far: she wants to minimize the sum of all distances from all attendees' houses to the party. Can you help her?

Input

The first line of the input gives the number of test cases, T. T test cases follow. Each test case starts with a line containing a single integer: the number of rectangular areas, B. Blines follow. Each line contains 4 integers: x1, y1, x2, y2, denoting the coordinates of a rectangular area of people Little Sin has invited to her party.

Output

For each test case, output one line containing "Case #t: x y d", where t is the case number (starting from 1) and (x, y) is the coordinates of the person whose home the party should be hosted. If there are multiple positions with the same minimum total distance, choose the one with the smallest x. If there are still multiple positions, choose the one with the smallest y. The value d is the sum of the distances from all attendees' houses to the point (x, y).

Limits

1 ≤ T ≤ 10.
|x1|, |y1|, |x2|, |y2| ≤ 10⁹.
x1 ≤ x2, y1 ≤ y2.
The rectangular areas within a test case don't intersect.

Small dataset

1 ≤ B ≤ 100.
1 ≤ Total number of people in each test case ≤ 1000.

Large dataset

1 ≤ B ≤ 1000.
1 ≤ Total number of people in each test case ≤ 1000000.

Sample

Input	Output
2 1 0 0 2 2 3 -1 2 -1 2 0 0 0 0 1 3 1 3	Case #1: 1 1 12 Case #2: -1 2 6

Analysis:
Calculating the total distance can be divided to calculate the total horizontal distance and total vertical distance.

A new class Pair is created to record(x,y), and it also sort all the elements by x first, if there are multiple equal x, sort the elements by y. This pre-sort is in order to meet the problem requirement: If there are multiple positions with the same minimum total distance, choose the one with the smallest x. If there are still multiple positions, choose the one with the smallest y.

Time Complexity O(N longN), N is the total number of people.

My solution: (Your opinion is highly appreciated)

[java] view plaincopy

1. package codeJam.google.com;  
2.   
3. import java.io.File;  
4. import java.io.FileWriter;  
5. import java.io.IOException;  
6. import java.util.ArrayList;  
7. import java.util.Collections;  
8. import java.util.Scanner;  
9.   
10. /** 
11.  * @author Zhenyi 2013 Dec 26, 2013 2:17:53 PM 
12.  */  
13. class Pair implements Comparable<Pair> {  
14.     Integer first;  
15.     Integer second;  
16.   
17.     @Override  
18.     public int compareTo(Pair o) {  
19.         int compare = this.first.compareTo(o.first);  
20.         return compare != 0 ? compare : this.second.compareTo(o.second);  
21.     }  
22.   
23.     public Pair(int x, int y) {  
24.         this.first = x;  
25.         this.second = y;  
26.     }  
27.   
28. }  
29.   
30. public class MeetAndParty {  
31.     public static void main(String[] args) throws IOException {  
32.         Scanner in = new Scanner(new File(  
33.                 "C:/Users/Zhenyi/Downloads/B-small-practice.in"));  
34.         FileWriter out = new FileWriter(  
35.                 "C:/Users/Zhenyi/Downloads/B-small-practice.out");  
36.         // Scanner in = new Scanner(new  
37.         // File("C:/Users/Zhenyi/Downloads/B-large-practice.in"));  
38.         // FileWriter out = new  
39.         // FileWriter("C:/Users/Zhenyi/Downloads/B-large-practice.out");  
40.   
41.         int T = in.nextInt();  
42.   
43.         for (int cases = 1; cases <= T; cases++) {  
44.             int B = in.nextInt();  
45.             ArrayList<Integer> x = new ArrayList<Integer>();  
46.             ArrayList<Integer> y = new ArrayList<Integer>();  
47.             ArrayList<Pair> pair = new ArrayList<Pair>();  
48.             for (int i = 0; i < B; i++) {  
49.                 int x1 = in.nextInt();  
50.                 int y1 = in.nextInt();  
51.                 int x2 = in.nextInt();  
52.                 int y2 = in.nextInt();  
53.                 for (int j = x1; j <= x2; j++) {  
54.                     for (int k = y1; k <= y2; k++) {  
55.                         x.add(j);  
56.                         y.add(k);  
57.                         pair.add(new Pair(j, k));  
58.                     }  
59.                 }  
60.             }  
61.             Collections.sort(x);  
62.             Collections.sort(y);  
63.             Collections.sort(pair);  
64.   
65.             ArrayList<Long> sumx = new ArrayList<Long>();  
66.             ArrayList<Long> sumy = new ArrayList<Long>();  
67.             sumx.add((long) 0);  
68.             sumy.add((long) 0);  
69.             for (int i = 0; i < x.size(); i++) {  
70.                 Long tmp = sumx.get(sumx.size() - 1);  
71.                 sumx.add(tmp + x.get(i));  
72.             }  
73.             for (int i = 0; i < y.size(); i++) {  
74.                 Long tmp = sumy.get(sumy.size() - 1);  
75.                 sumy.add(tmp + y.get(i));  
76.             }  
77.             long bestCost = Long.MAX_VALUE;  
78.             int resultx = 0;  
79.             int resulty = 0;  
80.   
81.             for (int i = 0; i < pair.size(); i++) {  
82.                 int firstx = Collections.binarySearch(x, pair.get(i).first);  
83.                 int firsty = Collections.binarySearch(y, pair.get(i).second);  
84.                 long cost = (firstx + 1) * (long) pair.get(i).first  
85.                         - sumx.get(firstx + 1) + sumx.get(sumx.size() - 1)  
86.                         - sumx.get(firstx + 1) - (pair.size() - firstx - 1)  
87.                         * (long) pair.get(i).first + (firsty + 1)  
88.                         * (long) pair.get(i).second - sumy.get(firsty + 1)  
89.                         + sumy.get(sumy.size() - 1) - sumy.get(firsty + 1)  
90.                         - (pair.size() - firsty - 1)  
91.                         * (long) pair.get(i).second;  
92.                 if (cost < bestCost) {  
93.                     bestCost = cost;  
94.                     resultx = pair.get(i).first;  
95.                     resulty = pair.get(i).second;  
96.                 }  
97.             }  
98.             out.write("Case #" + cases + ": " + resultx + " " + resulty + " "  
99.                     + bestCost + "\n");  
100.             System.out.print("Case #" + cases + ": " + resultx + " " + resulty  
101.                     + " " + bestCost + "\n");  
102.   
103.         }  
104.         in.close();  
105.         out.flush();  
106.         out.close();  
107.     }  
108. }  

Google Code Jam Notes - Dragon Maze - Java

Problem:

Retrieved from: https://code.google.com/codejam/contest/dashboard?c=2929486#s=p3

You are the prince of Dragon Kingdom and your kingdom is in danger of running out of power. You must find power to save your kingdom and its people. An old legend states that power comes from a place known as Dragon Maze. Dragon Maze appears randomly out of nowhere without notice and suddenly disappears without warning. You know where Dragon Maze is now, so it is important you retrieve some power before it disappears.

Dragon Maze is a rectangular maze, an N x M grid of cells. The top left corner cell of the maze is (0,0) and the bottom right corner is (N-1, M-1). Each cell making up the maze can be either a dangerous place which you never escape after entering, or a safe place that contains a certain amount of power. The power in a safe cell is automatically gathered once you enter that cell, and can only be gathered once. Starting from a cell, you can walk up/down/left/right to adjacent cells with a single step.

Now you know where the entrance and exit cells are, that they are different, and that they are both safe cells. In order to get out of Dragon Maze before it disappears, you must walk from the entrance cell to the exit cell taking as few steps as possible. If there are multiple choices for the path you could take, you must choose the one on which you collect as much power as possible in order to save your kingdom.

Input

The first line of the input gives the number of test cases, T. T test cases follow.

Each test case starts with a line containing two integers N and M, which give the size of Dragon Maze as described above. The second line of each test case contains four integers en_x, en_y, ex_x, ex_y, describing the position of entrance cell (en_x, en_y) and exit cell (ex_x, ex_y). Then N lines follow and each line has M numbers, separated by spaces, describing the N x M cells of Dragon Maze from top to bottom. Each number for a cell is either -1, which indicates a cell is dangerous, or a positive integer, which indicates a safe cell containing a certain amount of power.

Output

For each test case, output one line containing "Case #x: y", where x is the case number (starting from 1). If it's possible for you to walk from the entrance to the exit, y should be the maximum total amount of power you can collect by taking the fewest steps possible. If you cannot walk from the entrance to the exit, y should be the string "Mission Impossible." (quotes for clarity). Please note that the judge requires an exact match, so any other output like "mission impossible." or "Mission Impossible" (which is missing the trailing period) will be judged incorrect.

Limits

The amount of power contained in each cell will not exceed 10,000.
1 ≤ T ≤ 30.
0 ≤ en_x, ex_x < N.
0 ≤ en_y, ex_y < M.

Small dataset

1 ≤ N, M ≤ 10.

Large dataset

1 ≤ N, M ≤ 100.

Sample

Input	Output
2 2 3 0 2 1 0 2 -1 5 3 -1 6 4 4 0 2 3 2 -1 1 1 2 1 1 1 1 2 -1 -1 1 1 1 1 1	Case #1: Mission Impossible. Case #2: 7

Analysis:
Use Breadth First Search (BFS) algorithm to solve this problem, its difference between classical BFS algorithm is to find the largest value if there are multiple shortest path, so we need to update the value matrix accordingly.

Time Complexity O(MN).

My solution: (Your opinion is highly appreciated)

[java] view plaincopy

1. package codeJam.google.com;  
2.   
3. import java.io.File;  
4. import java.io.FileWriter;  
5. import java.io.IOException;  
6. import java.util.LinkedList;  
7. import java.util.Scanner;  
8.   
9. /** 
10.  * @author Zhenyi 2013 Dec 26, 2013 3:34:07 PM 
11.  */  
12. public class DragonMaze {  
13.     public static void main(String[] args) throws IOException {  
14.         // Scanner in = new Scanner(new File(  
15.         // "C:/Users/Zhenyi/Downloads/D-small-practice.in"));  
16.         // FileWriter out = new FileWriter(  
17.         // "C:/Users/Zhenyi/Downloads/D-small-practice.out");  
18.         Scanner in = new Scanner(new File(  
19.                 "C:/Users/Zhenyi/Downloads/D-large-practice.in"));  
20.         FileWriter out = new FileWriter(  
21.                 "C:/Users/Zhenyi/Downloads/D-large-practice.out");  
22.   
23.         int T = in.nextInt();  
24.   
25.         for (int cases = 1; cases <= T; cases++) {  
26.             int N = in.nextInt();  
27.             int M = in.nextInt();  
28.             int enx = in.nextInt();  
29.             int eny = in.nextInt();  
30.             int exx = in.nextInt();  
31.             int exy = in.nextInt();  
32.             int[][] maze = new int[N][M];  
33.             int[][] value = new int[N][M];  
34.             boolean[][] mark = new boolean[N][M];  
35.             int[][] steps = new int[N][M];  
36.             for (int i = 0; i < N; i++) {  
37.                 for (int j = 0; j < M; j++) {  
38.                     maze[i][j] = in.nextInt();  
39.                     value[i][j] = maze[i][j];  
40.                 }  
41.             }  
42.   
43.             LinkedList<Integer[]> q = new LinkedList<Integer[]>();  
44.             q.add(new Integer[] { enx, eny });  
45.             boolean found = false;  
46.             int path[][] = new int[][] { { -1, 0 }, { 0, -1 }, { 1, 0 },  
47.                     { 0, 1 } };  
48.             while (q.size() > 0) {  
49.                 Integer[] a = new Integer[2];  
50.                 a = q.poll();  
51.                 int x = a[0];  
52.                 int y = a[1];  
53.                 mark[x][y] = true;  
54.                 if ((x == exx) && (y == exy)) {  
55.                     found = true;  
56.                     break;  
57.                 }  
58.                 for (int i = 0; i < 4; i++) {  
59.                     int nextx = x + path[i][0];  
60.                     int nexty = y + path[i][1];  
61.                     if ((nextx >= 0) && (nexty >= 0) && (nextx < N)  
62.                             && (nexty < M) && !mark[nextx][nexty]  
63.                             && maze[nextx][nexty] != -1) {  
64.                         if ((steps[nextx][nexty] == 0)  
65.                                 || steps[x][y] + 1 <= steps[nextx][nexty]) {  
66.                             if (steps[nextx][nexty] == 0) {  
67.                                 q.add(new Integer[] { nextx, nexty });  
68.                                 steps[nextx][nexty] = steps[x][y] + 1;  
69.                             }  
70.                             if (value[nextx][nexty] < value[x][y]  
71.                                     + maze[nextx][nexty]) {  
72.                                 value[nextx][nexty] = value[x][y]  
73.                                         + maze[nextx][nexty];  
74.                             }  
75.                         }  
76.                     }  
77.                 }  
78.             }  
79.   
80.             if (found) {  
81.                 out.write("Case #" + cases + ": " + value[exx][exy] + "\n");  
82.             } else {  
83.                 System.out.print("Case #" + cases + ": Mission Impossible.\n");  
84.             }  
85.         }  
86.         in.close();  
87.         out.flush();  
88.         out.close();  
89.     }  
90. }