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

No comments: