416 – LED Test

A complete search problem with a confusing description.

• Take nInput sequences and store them in an integer array. We’ll represent each LED configuration by an int. 1 for 'Y' and 0 for 'N'.
• Now, we start guessing the countdown sequence by determining the first digit. So, we try the initial digits from 9 down-to nInput - 1.
• If the current digit matches the input and the burned-out LED’s –if there’s any–, we move to the previous digit, and so on. For a guess digit to match the input:
  • The guess digit should not contradict the burned segments.
  • Any difference –between a guess digit and an input– should be an input segment that’s off not vice-versa.
• If we reach the nInput^th digit, that’s a match. Otherwise, mismatch.

C++, rank 120:

#include<cstdio>
using namespace std;

int digit[10] = { 0x7E, 0x30, 0x6D, 0x79, 0x33, 0x5B, 0x5F, 0x70, 0x7F, 0x7B };
int n, input[16];
bool match;

void solve(int inputI, int digitI, int badMask) {
	// finished
	if (inputI == n)
		match = true;
	// more input
	else if (!(input[inputI] & badMask)) // matches old burns
		if (((digit[digitI] ^ input[inputI]) & input[inputI]) == 0) // new burns not revivals
			solve(inputI + 1, digitI - 1, (input[inputI] ^ digit[digitI]) | badMask);
}

char ans[2][16] = { "MISMATCH\n", "MATCH\n" };
char line[8], *p;

int main() {
	while (scanf("%d", &n) == 1 && n) {
		// input
		for (int i = 0; i < n; ++i) {
			scanf("%s", p = line);
			input[i] = 0;
			do
				input[i] |= ((*p == 'Y') << (line + 6 - p));
			while (*++p);
		}
		// solution
		match = false;
		for (int digitI = 9; digitI >= n - 1 && !match; --digitI)
			solve(0, digitI, 0);
		printf("%s", ans[match]);
	}
}

Odd Man Out

Given an odd list of couples of numbers (each number appears twice), find the number that occurs only once.
The solution is a mere xor on all the numbers as:


Also, xor is commutative:

so if we have a sample input A, B, C, A, B:

C++ implementation:

#include <iostream>
#include <fstream>
#include <iomanip>
using namespace std;

#define N 1024
typedef unsigned long long int64;

int n, g;
int64 card, cardXor;
ofstream ofile;
ifstream ifile;

int main() {
	int i, j;
	ifile.open("in.txt");
	ofile.open("out.txt");
	ifile >> n;
	for (i = 0; i < n; ++i) {
		// init
		cardXor = 0;
		// in
		ifile >> g;
		for (j = 0; j < g; cardXor ^= card, ++j)
			ifile >> card;
		// out
		ofile << "Case #" << i + 1 << ": " << cardXor << endl;
	}
	return 0;
}

11974 – Switch The Lights

A graph problem with some tweaks.
Your starting state is that all the lights are on. You can choose from different switches that trigger certain light bulbs. Clicking a switch moves you to the next state.
Lo and behold your graph! You’ve got your vertices (states), your edges (switch triggers), your start vertex (all lights are on) and your end vertex (all lights are off).
Now, what remains is implementation. Since bulbs are limited to 16, you can represent your state/vertex with an integer as a bit mask. Each ‘1’ bit corresponds to a lit bulb. From there you can see how easily switches can be implemented. Because a switch “triggers” the corresponding lights, a bit-wise xor should do the trick.
C++ implementation. Rank 37.

#include <stdio.h>
#include <cstring>
#include <queue>
using namespace std;

#define N (16)
#define M (128)

int nSwitch, switchEffect[M], nLight;
int nSteps[1 << N];

int dfs() {
	queue<int> q;
	q.push(~-(1 << nLight));
	memset(nSteps, -1, sizeof(nSteps));
	nSteps[~-(1 << nLight)] = 0;
	while (!q.empty()) {
		int p = q.front();
		q.pop();
		if (p) {
			for (int i = 0; i < nSwitch; ++i) {
				int newP = p ^ switchEffect[i];
				if (nSteps[newP] == -1) {
					nSteps[newP] = nSteps[p] + 1;
					q.push(newP);
				}
			}
		} else
			return nSteps[p];
	}
	return -1;
}

int main() {
	int nCase;
	scanf("%d", &nCase);
	for (int caseI = 0; caseI < nCase; ++caseI) {
		int t;
		// in
		scanf("%d %d", &nLight, &nSwitch);
		for (int i = 0; i < nSwitch; ++i) {
			switchEffect[i] = 0;
			for (int j = 0; j < nLight; ++j) {
				scanf("%d", &t);
				switchEffect[i] <<= 1;
				switchEffect[i] |= t;
			}
		}
		// solve
		t = dfs();
		if (t == -1)
			printf("Case %d: IMPOSSIBLE\n", caseI + 1);
		else
			printf("Case %d: %d\n", caseI + 1, t);
	}
	return 0;
}

Bitwise operations are adorable!