Sunday, May 9, 2010

Code Jam 2010: Theme Park

The problem definition could be found at Code Jam web site.

Official Contest Analysis could be found at Code Jam web site.

My solution is published below.

Main functions:
  • public solve - high-level problem solving
  • private solve - low -level problem solving
  • calculateByMap - calculates euros based on ride cache

Helper classes:
  • Key - ride cache key
  • Value - ride cache value

public class ThemePark {
...
private Scanner scanner;
private PrintWriter writer;

public ThemePark(InputStream is, OutputStream os) {
scanner = new Scanner(is);
writer = new PrintWriter(os);
}
...
/**
* Solve the problem
*/

public void solve() {
int t = scanner.nextInt();

for (int i = 1; i <= t; i++) {
writer.print("Case #");
writer.print(i + ": ");

// 1 <= R <= 10^8
long r = scanner.nextInt();

// 1 <= k <= 10^9
long k = scanner.nextInt();

// 1 <= N <= 1000
int n = scanner.nextInt();

// 1 <= g[i] <= 10^7
long g[] = new long[n];
for (int j = 0; j < n; j++)
g[j] = scanner.nextInt();

writer.println(solve(r, k, g));
}
}

private String solve(long r, long k, long g[]) {
Queue<Long> queue = new LinkedList<Long>();
Queue<Long> ride = new LinkedList<Long>();

// queue, ride -> count, euros
Map<Key, Value> map = new LinkedHashMap<Key, Value>();

for (int i = 0; i < g.length; i++)
queue.add(g[i]);

BigInteger euros = new BigInteger("0");
for (int i = 0; i < r; i++) {
long sum = 0;
ride.clear();

while ((queue.size() > 0) && (sum + queue.peek() <= k)) {
ride.add(queue.peek());
sum += queue.poll();
}

// prepare key->value pair for caching...
Key key = new Key(queue.toString(), ride.toString());
Value value = new Value(ride.size(), sum);

if (!map.containsKey(key)) {
map.put(key, value);

euros = euros.add(new BigInteger(((Long) sum).toString()));
queue.addAll(ride);
} else {
// the same [ride, queue] found in cache
// so calculate euros based on cache
euros = euros.add(calculateByMap(map, key, r - i));
break;
}
}
return euros.toString();
}

private BigInteger calculateByMap(Map<Key, Value> map, Key key, long ridesLeft) {
long storedSum = 0;
boolean found = false;
int foundIndex = 0;

long remainder = 0;
long remainderSum = 0;

for (Key storedKey : map.keySet()) {
// if item found - calculate remainder
if ((!found) && (storedKey.equals(key))) {
found = true;
remainder = ridesLeft % (map.size() - foundIndex);
}
if (found) {
// calculate stored sum
storedSum += map.get(storedKey).getSum();

// calculate remainder
if (remainder > 0) {
remainderSum += map.get(storedKey).getSum();
remainder--;
}
} else
foundIndex++;
}
long storedCount = map.size() - foundIndex;
long mult = ridesLeft / (storedCount);
mult = mult * storedSum + remainderSum;
return new BigInteger(((Long) mult).toString());
}

class Key {
private String queue;
private String ride;

Key(String queue, String ride) {
this.queue = queue;
this.ride = ride;
}

public String getQueue() {
return queue;
}

public String getRide() {
return ride;
}

@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;

Key key = (Key) o;

if (!queue.equals(key.queue)) return false;
if (!ride.equals(key.ride)) return false;

return true;
}

@Override
public int hashCode() {
int result = queue.hashCode();
result = 31 * result + ride.hashCode();
return result;
}
}

class Value {
private int size;
private long sum;

Value(int size, long sum) {
this.size = size;
this.sum = sum;
}

public int getSize() {
return size;
}

public long getSum() {
return sum;
}
}
}

See also other posts in Code Jam

Code Jam 2010: Fair Warning

The problem definition could be found at Code Jam web site.

Official Contest Analysis could be found at Code Jam web site.

My solution is published below.

Main functions:
  • public solve - high-level problem solving
  • private solve - low -level problem solving

public class FairWarning {
...
private Scanner scanner;
private PrintWriter writer;

public FairWarning(InputStream is, OutputStream os) {
scanner = new Scanner(is);
writer = new PrintWriter(os);
}
...
/**
* Solve the problem
*/

public void solve() {
int c = scanner.nextInt();

for (int i = 1; i <= c; i++) {
writer.print("Case #");
writer.print(i + ": ");

// 2 <= N <= 1000
int n = scanner.nextInt();

// 1 <= t[i] <= 10^50
// collect t[i] into a TreeSet to have them sorted
NavigableSet<BigInteger> t = new TreeSet<BigInteger>();
for (int j = 0; j < n; j++)
t.add(new BigInteger(scanner.next()));

writer.println(solve(t));
}
}

private BigInteger solve(NavigableSet<BigInteger> t) {
// find GCD of all differences between
Iterator i = t.descendingIterator();
BigInteger prev = null;
BigInteger div = null;
while (i.hasNext()) {
if (prev == null)
prev = (BigInteger) i.next();
else {
BigInteger diff = prev.subtract((BigInteger) i.next()).abs();
if (diff.equals(BigInteger.ZERO))
continue;
if (div == null)
div = diff;
else
div = div.gcd(diff);
}
}

// calculate slarboseconds
BigInteger mod = prev.mod(div);
if (mod.equals(BigInteger.ZERO))
return BigInteger.ZERO;
return div.subtract(mod);
}
}

See also other posts in Code Jam

Code Jam 2010: Snapper Chain

The problem definition could be found at Code Jam web site.

Official Contest Analysis could be found at Code Jam web site.

Dynamic programming could be used:
  1. state[j] - state of j-Snapper
  2. power[j] - is j-Snapper powered
  3. power[j+1] - do we have power after j-Snapper
  4. state[i][j] - state of j-Snapper after i-snaps
  5. power[i][j] - is j-Snapper powered after i-snaps
  6. state[i][j] = (power[i-1][j]) ? !state[i-1][j] : state[i-1][j]
  7. power[i][j+1] = power[i][j] && state[i][j]

state[i][j], where i-rows, j-columns
0 0 0 0 0 0 0 0 0 0 0
1 1 0 0 0 0 0 0 0 0 0
2 0 1 0 0 0 0 0 0 0 0
3 1 1 0 0 0 0 0 0 0 0
4 0 0 1 0 0 0 0 0 0 0
5 1 0 1 0 0 0 0 0 0 0
6 0 1 1 0 0 0 0 0 0 0
7 1 1 1 0 0 0 0 0 0 0
8 0 0 0 1 0 0 0 0 0 0
9 1 0 0 1 0 0 0 0 0 0
10 0 1 0 1 0 0 0 0 0 0
11 1 1 0 1 0 0 0 0 0 0
12 0 0 1 1 0 0 0 0 0 0
13 1 0 1 1 0 0 0 0 0 0
14 0 1 1 1 0 0 0 0 0 0
15 1 1 1 1 0 0 0 0 0 0
16 0 0 0 0 1 0 0 0 0 0

power[i][j], where i-rows, j-columns
0 1 0 0 0 0 0 0 0 0 0 0
1 1 1 0 0 0 0 0 0 0 0 0
2 1 0 0 0 0 0 0 0 0 0 0
3 1 1 1 0 0 0 0 0 0 0 0
4 1 0 0 0 0 0 0 0 0 0 0
5 1 1 0 0 0 0 0 0 0 0 0
6 1 0 0 0 0 0 0 0 0 0 0
7 1 1 1 1 0 0 0 0 0 0 0
8 1 0 0 0 0 0 0 0 0 0 0
9 1 1 0 0 0 0 0 0 0 0 0
10 1 0 0 0 0 0 0 0 0 0 0
11 1 1 1 0 0 0 0 0 0 0 0
12 1 0 0 0 0 0 0 0 0 0 0
13 1 1 0 0 0 0 0 0 0 0 0
14 1 0 0 0 0 0 0 0 0 0 0
15 1 1 1 1 1 0 0 0 0 0 0
16 1 0 0 0 0 0 0 0 0 0 0

But this idea requires 30 x 10^8 array which is not possible.
If we check state[i][j] then we could find that it is just binary representation of i-number. So are not required to store it.
power[i][j+1] could be calculated only based on state[i][j].

My solution is published below.

Main functions:
  • solve - solves the problem
  • snapper - returns power after j-Snapper after i-snaps

public class SnapperChain {
...
private Scanner scanner;
private PrintWriter writer;

public SnapperChain(InputStream is, OutputStream os) {
scanner = new Scanner(is);
writer = new PrintWriter(os);
}
...
private static final int MAX_SNAPPER = 30;

/**
* Solve the problem
*/

public void solve() {
int t = scanner.nextInt();

for (int i = 1; i <= t; i++) {
writer.print("Case #");
writer.print(i + ": ");

// The light is plugged into the Nth Snapper.
// 1 <= N <= 30;
int n = scanner.nextInt();

// I have snapped my fingers K times
// 0 <= K <= 10^8;
long k = scanner.nextInt();

boolean light = snapper(n, k);
writer.println((light) ? "ON" : "OFF");
}
}

private boolean snapper(int n, long k) {
boolean[] power = new boolean[MAX_SNAPPER + 1];

power[0] = true;
for (int j = 0; j < MAX_SNAPPER; j++) {
boolean state = ((k >> j) & 0x01) == 0x01;
power[j + 1] = power[j] && state;
}
return power[n];
}
}

See also other posts in Code Jam

Code Jam 2010: Qualification Round - Solutions & Analysis

Solutions & Analysis of problems from Qualification Round of Google Code Jam 2010 could be found below
http://code.google.com/codejam/contests.html

Saturday, May 8, 2010

Code Jam 2010: Qualification Round

Today I took part in Qualification Round of Google Code Jam 2010.
Successfully solved all problems with Small datasets.
Now I'm waiting for the end of the contest to verify my solutions with Large datasets.



I plan to publish my solutions later...

Monday, May 3, 2010

Graph Search Algorithms

In this post next graph search algorithm are discussed:

Class diagram:

Main methods of a class Graph:
  • dfs - Depth-First Search
  • bfs - Breadth-First Search
  • dijkstra - Dijkstra's algorithm

Methods definition could be found below:
public class Graph {

...

public List<Node> dfs(Node node) {
clearVisited();

return dfs(node, new LinkedList<Node>());
}

private List<Node> dfs(Node node, List<Node> dfsNodes) {
if (isVisited(node))
return dfsNodes;

visit(node);
dfsNodes.add(node);

for (Edge edge : node.getEdges())
dfsNodes = dfs(edge.getNode(), dfsNodes);
return dfsNodes;
}

public List<Node> bfs(Node node) {
clearVisited();

Queue<Node> queue = new LinkedList<Node>();
queue.add(node);

return bfs(queue, new LinkedList<Node>());
}

private List<Node> bfs(Queue<Node> queue, List<Node> bfsNodes) {
while (!queue.isEmpty()) {
Node node = queue.remove();

if (!isVisited(node)) {
visit(node);
bfsNodes.add(node);

for (Edge edge : node.getEdges())
queue.add(edge.getNode());
}
}
return bfsNodes;
}

public Map<Node, Integer> dijkstra(Node current) {
Map<Node, Integer> weights = new HashMap<Node, Integer>();
for (Node node : getNodes())
weights.put(node, Integer.MAX_VALUE);
weights.put(current, 0);

clearVisited();
do {
int minWeight = Integer.MAX_VALUE;
Node minNode = null;

for (Edge edge : current.getEdges()) {
Node node = edge.getNode();
int weight = weights.get(current) + edge.getWeight();

if (weight < weights.get(node))
weights.put(node, weight);

if ((weight < minWeight) && (!isVisited(node))) {
minWeight = weight;
minNode = node;
}
}
visit(current);
current = minNode;
} while (current != null);
return weights;
}
}