Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Problem 1098. USC Fall 2012 ACM : Code Word Minimum Flipped Bits

Created by Richard Zapor

This Challenge is to solve Question A of the USC ACM Fall 2012 Contest.

Given an array M of Valid binary codewords(m codewords of width n) and a Received Corrupted(?) codeword of width n, determine the minimum number of flipped bits in the Received codeword to generate a valid codeword.

Input: [ M, v ]

Output: e, minimum number of error(flipped) bits .

From full USC data file

Input: [0 0 0; 1 1 1; 1 1 0], [0 1 0]

Output: 1 as [0 1 0] can convert to [0 0 0] or [1 1 0] with a single flip

Matlab one-liner?

The Winning C solution - not much help:

#include <iostream>
#include <stdio.h>
#include <string>
using namespace std;
int main () {
	freopen("codes.in", "r", stdin);
	int K,n,b;
	cin >> K;
	for (int i = 1; i < K + 1; ++i) {
		cin >> n >> b;
		string m[1000], r;
		for (int j = 0; j < n; ++j)
			cin >> m[j];
		cin >> r;
% Process Start		
		int f = b;
		for (int j = 0; j < n; ++j) {
			int d = b;
			for (int k = 0; k < b; ++k) {
				if (m[j][k] == r[k])
					--d;
			}
			f = ((f <= d) ? f : d);
		}
% Process End 
		printf("Data Set %d:\n", i);
		printf("%d\n\n", f);
	}
	return 0;
}

Tags

Problem Group

Solution Statistics

8 correct solutions 8 incorrect solutions
Last solution submitted on Nov 27, 2014

Problem Comments