Google Kickstart Round H 2020 screencast with commentary and explanations

Блог пользователя neal

Автор neal, 4 года назад, По-английски

Hey everyone, here's my screencast of Kickstart Round H which just finished. I also added commentary and explanations for each of the problems--let me know if this is helpful!

https://www.youtube.com/watch?v=4_ndQbmDbuQ

google, kickstart, screencast

neal
4 года назад
3

Комментарии (3)

Написать комментарий?

moli2398

4 года назад, # |

I guess I'm doing the same thing in problem C as everyone and as told in Analysis. But this doesn't work. Please help! Thanks

Code

...

 public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		int t = scn.nextInt();
		int x = 1;
		while (t > 0) {
			int n = scn.nextInt();
			Point[] arr = new Point[n];
			for (int i = 0; i < n; ++i) {
				arr[i] = new Point(scn.nextInt(), scn.nextInt(), i);
			}
			System.out.println("Case #" + x + ": " + solve(n, arr));
			t--;
			x++;
		}
	}

	public static long solve(int n, Point[] arr) {
		Arrays.sort(arr, new yCom());
		int yMed = arr[n / 2].y;
		long ans = 0;
		Arrays.sort(arr, new xCom());
		int xMed = arr[n / 2].x;
		int i=n/2;
		while(i>=0) {
			int x=arr[i].x;
			int y=arr[i].y;
			ans+=Math.abs(yMed-y);
			ans+=Math.abs(xMed-x);
			xMed--;
			i--;
		}
		xMed=arr[n/2].x+1;
		i=n/2+1;
		while(i<n) {
			int x=arr[i].x;
			int y=arr[i].y;
			ans+=Math.abs(yMed-y);
			ans+=Math.abs(xMed-x);
			xMed++;
			i++;
		}
		return ans;
	}

	public static class xCom implements Comparator<Point> {

		@Override
		public int compare(Point arg0, Point arg1) {
			// TODO Auto-generated method stub
			return arg0.x - arg1.x;
		}

	}

	public static class yCom implements Comparator<Point> {

		@Override
		public int compare(Point arg0, Point arg1) {
			// TODO Auto-generated method stub
			return arg0.y - arg1.y;
		}

	}

	public static class Point {
		int x;
		int y;
		int id;

		Point(int x, int y, int id) {
			this.x = x;
			this.y = y;
			this.id = id;
		}
	}

	static Reader scn = new Reader();
	static OutputStream out = new BufferedOutputStream(System.out);