### elgamalsalman's blog

By elgamalsalman, history, 37 hours ago,

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

• +4

 » 37 hours ago, # |   0 Auto comment: topic has been updated by elgamalsalman (previous revision, new revision, compare).