Google Code Jam - Round1 A 2013 - Bullseye

Problem Links:

Google Code Jam, Round1 A 2013, Problem A

Problem:

Problem Bullseye

Maria has been hired by the Ghastly Chemicals Junkies (GCJ) company to help them manufacture bullseyes. A bullseye consists of a number of concentric rings (rings that are centered at the same point), and it usually represents an archery target. GCJ is interested in manufacturing black-and-white bullseyes.



Maria starts with t millilitres of black paint, which she will use to draw rings of thickness 1cm (one centimetre). A ring of thickness 1cm is the space between two concentric circles whose radii differ by 1cm.

Maria draws the first black ring around a white circle of radius r cm. Then she repeats the following process for as long as she has enough paint to do so:

1. Maria imagines a white ring of thickness 1cm around the last black ring.
2. Then she draws a new black ring of thickness 1cm around that white ring.

Note that each "white ring" is simply the space between two black rings.

The area of a disk with radius 1cm is π cm². One millilitre of paint is required to cover area π cm². What is the maximum number of black rings that Maria can draw? Please note that:

• Maria only draws complete rings. If the remaining paint is not enough to draw a complete black ring, she stops painting immediately.
• There will always be enough paint to draw at least one black ring.

Input

The first line of the input gives the number of test cases, T. T test cases follow. Each test case consists of a line containing two space separated integers: r and t.

Output

For each test case, output one line containing "Case #x: y", where x is the case number (starting from 1) and y is the maximum number of black rings that Maria can draw.

Limits

Small dataset

1 ≤ T ≤ 1000.
1 ≤ r, t ≤ 1000.

Large dataset

1 ≤ T ≤ 6000.
1 ≤ r ≤ 10¹⁸.
1 ≤ t ≤ 2 × 10¹⁸.

Sample

Input
5 1 9 1 10 3 40 1 1000000000000000000 10000000000000000 1000000000000000000
Output
Case #1: 1 Case #2: 2 Case #3: 3 Case #4: 707106780 Case #5: 49

Solution:

At first thought, I believed this was a math problem, so I can retrieve the fomular, then from the problem statement, we can see for the ith black ring we will paint will cost us, 2*r + 4*i - 3; So if we have x rings to paint, we will have Sum(2*r + 4*i - 3), i range from 1 to x, so the total will be 2x^2 + x*(2*r-1) <= t; So we got x <= (1-2*r + SQRT((2*r-1)^2 + 8*t))/2. So we only need to check the x, x-1, and x+1 these three possible answers. but the problem is if I use this approach, none of the primitive number could represent the value when number went to big. This approach might even not pass the first small-input test sets. So for the second thought, use BigInteger would be a great idea to solve this problem, while the problem is there is no function like Math.SQRT for BigInteger. Above so, we have the situation which we have to use BigInteger to represent our numbers, while we can't just use that fomular to solve our problem, this formula might work for other languages like c or c++, but definitely not for Java. So here we go, binary search is our helper. which could find our solution with O(lgt) time, where t is the input you have.

Source Code:

/**
 * 
 */
package com.googlecodejam.yr2013.round1A;

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.PrintWriter;
import java.math.BigInteger;

/**
 * @author antonio081014
 * @time Apr 26, 2013, 5:21:43 PM
 */
public class A {

 BigInteger two = new BigInteger("2");

 public static void main(String[] args) throws Exception {
  A main = new A();
  main.run();
  System.exit(0);
 }

 private void run() throws Exception {
  BufferedReader in = new BufferedReader(new FileReader("input.in"));
  PrintWriter out = new PrintWriter(new FileWriter("output.txt"));
  int T = Integer.parseInt(in.readLine());
  for (int t = 1; t <= T; t++) {
   out.write("Case #" + t + ": ");
   String[] lines = in.readLine().split("\\s");
   long r = Long.parseLong(lines[0]);
   long amount = Long.parseLong(lines[1]);
   String ret = solve(r, amount);
   System.out.println(ret);
   out.write("" + ret + "\n");
  }
  in.close();
  out.close();
 }

 private String solve(long r, long amount) {
  BigInteger rr = new BigInteger(Long.toString(r));
  BigInteger tt = new BigInteger(Long.toString(amount));
  BigInteger left = BigInteger.ZERO;
  BigInteger right = tt;
  while (left.compareTo(right) < 0) {
   BigInteger mid = (right.add(left).add(BigInteger.ONE)).divide(two);
   if (check(mid, rr, tt)) {
    left = mid;
   } else
    right = mid.subtract(BigInteger.ONE);
  }
  return left.toString();
 }

 private boolean check(BigInteger x, BigInteger r, BigInteger amount) {
  // BigInteger two = new BigInteger("2");
  return x.multiply(
    x.multiply(two).add(
      r.multiply(two).subtract(new BigInteger("1"))))
    .compareTo(amount) <= 0;
  // return x * (2 * x + 2 * r - 1) <= amount;
 }

 // private String solve3(BigInteger r, BigInteger amount) {
 // BigInteger ret =BigInteger.ONE.subtract(two.multiply(r)).add()
 // (1.0 - 2.0 * r + Math.sqrt((2.0 * r - 1)
 // * (2.0 * r - 1) + 8.0 * amount)) / 4;
 // if (check(ret, r, amount))
 // return ret.toString();
 // return ret.subtract(BigInteger.ONE).toString();
 // }
}

HackerRank: 20130417_Coin_on_the_Table.java

Problem Links:

HackerRank: Coin on the Table

Problem:

You have a rectangular board consisting of n rows , numbered from 1 to n and m columns , numbered from 1 to m . Initially - at time 0 - there is a coin on the top-left cell of your board. Each cell of your board contains one of these letters:
    *, exactly one of your cells has letter ‘*’.
    U, If at time t, the coin is on the cell(i,j) and cell(i,j) has letter ‘U’, the coin will be on the cell(i-1,j) in time t+1 if i > 1. otherwise there is no coin on your board at time t+1.
    L, If at time t, the coin is on the cell(i,j) and cell(i,j) has letter ‘L’, the coin will be on the cell(i,j-1) in time t+1 if j > 1. otherwise there is no coin on your board at time t+1.
    D, If at time t, the coin is on the cell(i,j) and cell(i,j) has letter ‘D’, the coin will be on the cell(i+1,j) in time t+1 if i < n. otherwise there is no coin on your board at time t+1.
    R, If at time t, the coin is on the cell(i,j) and cell(i,j) has letter ‘R’, the coin will be on the cell(i,j+1) in time t+1 if j < m. otherwise there is no coin on your board at time t+1.

When the coin reaches the cell that has letter ‘*’ it will be there permanently. When you punch on your board, your timer starts and the coin moves between cells. before doing that you want to do some operation so that you could be sure that at time k the coin will be on the cell having letter ‘*’. In each operation you can select a cell with some letter other than ‘*’ and change the letter to ‘U’, ‘L’, ‘R’ or ‘D’. You want to do as few operations as possible in order to achieve your goal. Your task is to find the minimum number of operations.

Input:
The first line of input contains three integers n and m and k.
Next n lines contains m letters which describe you board.
n and m are integers less than 51.
k is less than 1001.

Output:
on the only line of the output print an integer being the answer to the test.
If you cannot achieve your goal, output -1 please.

Sample input :

2 2 3
RD
*L

Sample output :

0

Sample input :

2 2 1
RD
*L

Sample output :

1

Explanation :

In the first example you don’t have to change any letters, but in the second example you should change the letter of cell (1,1) to ‘D’.

Solution:

Obviously, the problem ask you to find the shortest path from (0, 0) to the location of '*', where there is weight 1 cost if you do not have the right corresponding direction character. Like if you goes up, it will cost you 0 if you have 'U' at the corresponding location, otherwise, you just have to pay for 1 unit cost.

Here, I use Breadth-First-Search to find the shortest path from (0, 0) to '*', and use memorization(int[][] cost) to reduce redundant calculation.

PS: the problem statement shows at K moment, the coin has to share the same cell of '*', this could also happen if the coin reach there earlier, which means the coin could just sit and wait there, this also could be the solution if this results few costs.

Source Code:

import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;

public class Solution {
 String[] board;
 int[][] cost;
 int N;
 int M;
 static final int[] dx = { 1, 0, -1, 0 };
 static final int[] dy = { 0, -1, 0, 1 };
 static final char[] ch = { 'D', 'L', 'U', 'R' };

 public static void main(String[] args) {
  Solution main = new Solution();
  main.run();
  System.exit(0);
 }

 private void run() {
  Scanner in = new Scanner(System.in);
  N = in.nextInt();
  M = in.nextInt();
  int k = in.nextInt();
  board = new String[N];
  for (int i = 0; i < N; i++) {
   board[i] = in.next();
  }

  cost = new int[N][M];
  for (int i = 0; i < N; i++)
   // for (int j = 0; j < M; j++)
   Arrays.fill(cost[i], Integer.MAX_VALUE);

  int ret = bfs(k);
  if (ret == Integer.MAX_VALUE)
   ret = -1;

  System.out.println(ret);
 }

 private int bfs(int K) {
  Queue<Node> queue = new PriorityQueue<Node>();
  queue.add(new Node(0, 0, K, 0));
  while (!queue.isEmpty()) {
   Node node = queue.poll();
   int x = node.x;
   int y = node.y;
   int k = node.k;
   int cost = node.cost;

   this.cost[x][y] = Math.min(this.cost[x][y], cost);
   if (board[x].charAt(y) == '*' && k >= 0)
    return this.cost[x][y];
   else if (k < 0)
    continue;

   for (int i = 0; i < 4; i++) {
    int xx = x + dx[i];
    int yy = y + dy[i];
    if (inBoard(xx, yy)) {
     int c = board[x].charAt(y) == ch[i] ? 0 : 1;
     if (c + cost < this.cost[xx][yy])
      queue.add(new Node(xx, yy, k - 1, c + cost));
    }
   }
  }
  return -1;
 }

 private boolean inBoard(int x, int y) {
  return x >= 0 && x < N && y >= 0 && y < M;
 }
}

class Node implements Comparable<Node> {
 public int x;
 public int y;
 public int k;
 public int cost;

 public Node(int x, int y, int k, int c) {
  this.x = x;
  this.y = y;
  this.k = k;
  this.cost = c;
 }

 public int compareTo(Node node) {
  // if (this.cost != node.cost)
  return this.cost - node.cost;
  // if (this.k != node.k)
  // return this.k - node.k;
  // return this.x + this.y - node.x - node.y;
 }
}