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