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

Created by Richard Zapor

Solve Later

{"relationships":[{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/document","targetMode":"","relationshipId":"rId1","target":"/matlab/document.xml"},{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/output","targetMode":"","relationshipId":"rId2","target":"/matlab/output.xml"}],"parts":[{"partUri":"/matlab/document.xml","relationship":[],"contentType":"application/vnd.mathworks.matlab.code.document+xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n<w:document xmlns:w=\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\"><w:body><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>This Challenge is to solve Question A of the</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"http://contest.usc.edu/index.php/Fall12/Home\"><w:r><w:t>USC ACM Fall 2012 Contest</w:t></w:r></w:hyperlink><w:r><w:t>.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>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.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Input: [ M, v ]</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Output: e, minimum number of error(flipped) bits .</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>From full</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"http://contest.usc.edu/index.php/Fall12/Home?action=download&amp;upname=codes.in.txt\"><w:r><w:t>USC data file</w:t></w:r></w:hyperlink></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Input: [0 0 0; 1 1 1; 1 1 0], [0 1 0]</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Output: 1 as [0 1 0] can convert to [0 0 0] or [1 1 0] with a single flip</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Matlab one-liner?</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>The Winning C solution - not much help:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[#include <iostream>\n#include <stdio.h>\n#include <string>\nusing namespace std;\nint main () {\n freopen(\"codes.in\", \"r\", stdin);\n int K,n,b;\n cin >> K;\n for (int i = 1; i < K + 1; ++i) {\n cin >> n >> b;\n string m[1000], r;\n for (int j = 0; j < n; ++j)\n cin >> m[j];\n cin >> r;\n% Process Start \n int f = b;\n for (int j = 0; j < n; ++j) {\n int d = b;\n for (int k = 0; k < b; ++k) {\n if (m[j][k] == r[k])\n --d;\n }\n f = ((f <= d) ? f : d);\n }\n% Process End \n printf(\"Data Set %d:\\n\", i);\n printf(\"%d\\n\\n\", f);\n }\n return 0;\n}]]></w:t></w:r></w:p></w:body></w:document>"},{"partUri":"/matlab/output.xml","contentType":"text/xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\" ?><embeddedOutputs><metaData><evaluationState>manual</evaluationState><layoutState>code</layoutState><outputStatus>ready</outputStatus></metaData><outputArray type=\"array\"/><regionArray type=\"array\"/></embeddedOutputs>"}]}

This Challenge is to solve Question A of the <a href="http://contest.usc.edu/index.php/Fall12/Home">USC ACM Fall 2012 Contest</a>.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 <a href="http://contest.usc.edu/index.php/Fall12/Home?action=download&amp;upname=codes.in.txt">USC data file</a>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 flipMatlab one-liner?The Winning C solution - not much help:<pre class="language-matlab">#include &lt;iostream>
#include &lt;stdio.h>
#include &lt;string>
using namespace std;
int main () {
	freopen("codes.in", "r", stdin);
	int K,n,b;
	cin >> K;
	for (int i = 1; i &lt; K + 1; ++i) {
		cin >> n >> b;
		string m[1000], r;
		for (int j = 0; j &lt; n; ++j)
			cin >> m[j];
		cin >> r;
% Process Start		
		int f = b;
		for (int j = 0; j &lt; n; ++j) {
			int d = b;
			for (int k = 0; k &lt; b; ++k) {
				if (m[j][k] == r[k])
					--d;
			}
			f = ((f &lt;= d) ? f : d);
		}
% Process End 
		printf("Data Set %d:\n", i);
		printf("%d\n\n", f);
	}
	return 0;
}
</pre>

Solve

Solution Stats

22 Solutions
12 Solvers

Last Solution submitted on Jun 27, 2018

Last 200 Solutions

Problem Recent Solvers12

Problem Tags

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

Solution Stats

Last 200 Solutions

Problem Recent Solvers12

Suggested Problems

More from this Author236

Problem Tags

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

Solution Stats

Last 200 Solutions

Problem Recent Solvers12

Suggested Problems

More from this Author236

Problem Tags

Players