elgamalsalman's blog

By elgamalsalman, history, 4 years ago, In English

So I have been banging my head on the table for hours now, I have been practicing the exercises accompanying the book Competitive Programming 3, I was doing UVa 00416 LED test, but for some reason my code is giving me a WA (Wrong Answer) verdict I am not sure why, I even found a working solution online and I have wrote a simple code to randomly generate testcases and run both (my and the solution) codes and terminate if the outputs were different but it didn't and I have been checking for a lot of testcases now. I think I have really spent more hours than I should have on this problem so if someone can spot the mistake in my code I would be really grateful for him/her. Thanks in advance.

#include<bits/stdc++.h>

using namespace std;

typedef vector<int> vi;
typedef vector<vi> vvi;

bool	isMatch;
int	N, reliabilityLimits[7];
bitset<7>	sequence[10];
vvi	digits  = {
	{1, 1, 1, 1, 1, 1, 0},
	{0, 1, 1, 0, 0, 0, 0},
	{1, 1, 0, 1, 1, 0, 1},
	{1, 1, 1, 1, 0, 0, 1},
	{0, 1, 1, 0, 0, 1, 1},
	{1, 0, 1, 1, 0, 1, 1},
	{1, 0, 1, 1, 1, 1, 1},
	{1, 1, 1, 0, 0, 0, 0},
	{1, 1, 1, 1, 1, 1, 1},
	{1, 1, 1, 1, 0, 1, 1}
};

bool canBeDigit (int sequenceIndex, int Digit) {
	//cerr << "// canBeDigit(" << sequenceIndex << ", " << Digit << ")\n";
	//
	// Can't find the test case that gives a wrong answer
	//
	for (int i = 0; i < 7; i++) {
		if (sequence[sequenceIndex][i]) {
			if (!digits[Digit][i]) return false;
		} else {
			if (digits[Digit][i] && reliabilityLimits[i] >= sequenceIndex) return false;
		}
	}
	return true;
}

void backtrack (int sequenceIndex, int Digit) {
	//cerr << "// backtrack(" << sequenceIndex << ", " << Digit << ")\n";
	//cerr << "// N : " << N << '\n';
	if (sequenceIndex == N) {
		//cerr << "// Found it!!!\n";
		isMatch = true;
		return;
	}
	if (canBeDigit(sequenceIndex, Digit)) backtrack(sequenceIndex + 1, Digit - 1);
}

int main () {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	while (cin >> N && N) {
		isMatch = false;
		fill(reliabilityLimits, reliabilityLimits + 7, -1);
		memset(sequence, 0, sizeof sequence);
		for (int i = 0; i < N; i++) {
			cin.ignore();
			for (int j = 0; j < 7; j++) {
				sequence[i][j] = (cin.get() == 'Y');
				if (sequence[i][j]) {
					reliabilityLimits[j] = i;
				}
			}
		}

		//cerr << "// sequence:-\n";
		//for (bitset<7> ele : sequence) {
		//	cerr << "// " << ele.to_string() << '\n';
		//}

		//cerr << "// reliabilityLimits :";
		//for (int i : reliabilityLimits) {
		//	cerr << ' ' << i;
		//}
		//cerr << '\n';

		for (int i = N - 1; i < 10 && !isMatch; i++) {
			if (canBeDigit(0, i)) {
				backtrack(1, i - 1);
				//cerr << "// after backtracking isMatch : " << (isMatch ? "true" : "false") << '\n';
			}
		}
		
		cout << (isMatch ? "MATCH\n" : "MISMATCH\n");
	}
}

Full text and comments »

  • Vote: I like it
  • +4
  • Vote: I do not like it