## Sunday, May 9, 2010

### 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