11959 – Dice

A brute-force problem.
Given two six-sided dice in a certain orientation, you have to determine whether they’re equal. The die is represented by an integer with each digit representing one face of the die as follows: top, bottom, front, left, back, right
To check whether d1 and d2 are equivalent, keep d1 in a fixed orientation and rotate d2 to all possible orientation. If they match in any orientation, they’re equal.
Now, we need to know how to get all possible orientations; If we rotate the die so that each face appears on top once, that’s 6 orientations. For each of these, we can spin the die along the y-axis to get 4 more positions. Summing up, that’s a total of 6x4 different orientations we have to check.
Time to actually implement those permutations. Here are two macros that we’ll rely on in generating the orientations. R(d): rotates the die d clockwise along the y-axis, F(d): rotates along the x-axis:

#define R(d) ( ((d) & 0x000F00) << 12 | ((d) & 0x00000F) << 16 | ((d) & 0x00F0F0) | ((d) & 0x0F0000) >> 8 | ((d) & 0xF00000) >> 20 )
#define F(d) ( ((d) & 0x0000F0) << 16 | ((d) & 0x00F000) << 4 | ((d) & 0xF00000) >> 8 | ((d) & 0x000F0F) | ((d) & 0x0F0000) >> 12 )

The rest should be easier. Coded in C++:

#include <cstdio>
using namespace std;

#define R(d) ( ((d) & 0x000F00) << 12 | ((d) & 0x00000F) << 16 | ((d) & 0x00F0F0) | ((d) & 0x0F0000) >> 8 | ((d) & 0xF00000) >> 20 )
#define F(d) ( ((d) & 0x0000F0) << 16 | ((d) & 0x00F000) << 4 | ((d) & 0xF00000) >> 8 | ((d) & 0x000F0F) | ((d) & 0x0F0000) >> 12 )

bool E(long long d1, long long d2) {
	return ((d1) == (d2) || (d1) == R((d2)) || (d1) == R(R((d2))) || (d1) == R(R(R((d2)))));
}

char ans[2][16] = { "Not Equal", "Equal" };

int main() {
	long long t, d1, d2;
	scanf("%lld", &t);
	while (t--) {
		bool out = false;
		scanf("%llx %llx", &d1, &d2);
		out = E(d1, d2) || E(d1, F(d2)) || E(d1, F(F(d2))) || E(d1, F(F(F(d2))))
				|| E(d1, F(R(d2))) || E(d1, F(R(R(R(d2)))));
		printf("%s\n", ans[out]);
	}
	return 0;
}

Rank 41.

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]);
	}
}

11933 – Splitting Numbers

A simple bit manipulation problem.
You need to split the set bits of an integer between two other integers alternatively. C++ implementation, rank 134:

#include <cstdio>

#define M (1ll << 31)
typedef unsigned long long int64;

int64 n, a, b, i, isA;

int main() {
	while (scanf("%lld", &n) == 1 && n) {
		isA = a = b = 0;
		for (i = 1; i < M; i <<= 1) {
			if (n & i) {
				isA = !isA;
				if (isA)
					a |= i;
				else
					b |= i;
			}
		}
		printf("%lld %lld\n", a, b);
	}
	return 0;
}

10718 – Bit Mask

You’re required to find the mask M that, given an integer N, maximizes N|M.
The optimal solution would be M=~N. However, you have the restriction L≤M≤R.
So, we’ll build that mask M bit-by-bit (from left to right) in a binary-search fashion keeping in mind the boundaries.
For each bit in M that we’re building we look at the corresponding bit in ~N. There are only two case where we’re allowed to place ones in M:

• M is still less than R and the corresponding bit in ~N is a one. This is as if we’re trying to approach the optimal solution but with caution.
• M is less than L. So, we increase it.

If none of those satisfy we place a zero.
C++ implementation, rank 216.

#include <cstdio>
using namespace std;

typedef unsigned long long int64;
#define I (1ll << 32)

int64 N, L, R, M, m, i;

int main() {
	while (scanf("%lld %lld %lld", &N, &L, &R) == 3) {
		M = 0;
		++L;
		++R;
		for (i = I; i > 0; i >>= 1)
			if (((m = M | i) < L) || ((m < R) && (~N & i)))
				M = m;
		printf("%lld\n", M);
	}
	return 0;
}

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;
}