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

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

Solution Stats

25.35% Correct | 74.65% Incorrect
Last Solution submitted on May 28, 2024

Solution Comments

Show comments

Problem Recent Solvers18

Suggested Problems

More from this Author308

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!