Google Codejam KickStart 2017 Round G

Java Code:

Problem A. Huge Numbers

We need to calculate the remainder of a^(n!) mod p, where a,n,p<=10^5.

As for small (n<=10), we can use brute force, so we only consider about the large dataset.

Assume n>=5 (n<5 just calculate directly). Obviously, we can use Fermat–Euler theorem.

a^φ(n) ≡ 1 (mod n)

However, there is a condition that a and n must be coprime integers. In this problem, a and
p may not be coprime, so we cannot use the theorem directly.

Just do the prime factorization for p:

p = p1^r1*p2^r2*...*pk^rk

And then, for each pi, we consider whether a can be divided by pi:

  1. If yes, since n>=5, 5!=120, so pi^ri|a^(n!).
  2. If no, according to the Fermat–Euler theorem, we have
    a^(ri*(pi-1)) ≡ 1 (mod pi^ri)

    So we just need to calcualte the remainder of n! mod (ri*(pi-1)), which can be calculated directly.

In conclusion, for each pi, we can find the remainder of a^(n!) mod (pi^ri). What we need to do is just iterate from 0 to p-1, and find the answer which also satisfies this condition.

Problem B. Cards Game

There are n cards in the box. Each hard has a red number and a blue number on it. Each time, we may pick one card out of the box, and then choose another card in the box, and the R^B value to the total.

It’s not easy to solve directly, but we can consider this problem in a different way:

There is only one card in the box. Each time, we may put a new card into it, and add the XOR value of the red number of this card and one blue number in the box, and vice versa. Keep doing this until all cards have been put into the box.

We can use Greedy Algorithm to solve this problem:

  1. Enumerate the last one card in the box.
  2. Each time, we just iterate all the cards outside, and all the cards inside the box, find the minimal XOR value, add to the total, and put that card outside into the box.
  3. Keep doing this until all cards have been put into the box. Find the minimal sum.

Problem C. Matrix Cutting

Very simple. Just use Dynamic Programming.

Calculate the minimal value of each sub-matrix, and then use DP to calculate the maximum value of each sub-matrix.

It’s recommended to iterate from the delta value, as it guarantees that all sub-states have been calculated before.

for (int row_delta = 0; row_delta < n; row_delta++) {
    for (int top = 0; top < n - row_delta; top++) {
        int bottom = top + row_delta;
        // similar to the column