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
Solution Comments
Show commentsProblem Recent Solvers19
Suggested Problems
-
Make the vector [1 2 3 4 5 6 7 8 9 10]
49556 Solvers
-
Given an unsigned integer x, find the largest y by rearranging the bits in x
1831 Solvers
-
Program an exclusive OR operation with logical operators
717 Solvers
-
63 Solvers
-
Rotate input square matrix 90 degrees CCW without rot90
618 Solvers
More from this Author308
Problem Tags
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!