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