## 219 - Department of Redundancy Department

Moderator: Board moderators

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

### 219 - Department of Redundancy Department

Lots of WAs, so I may be making a conceptual error...

Am I right that the line
If more than one sequence of FDs can be used to show another FD is redundant, any such sequence is acceptable, ...
means that we only have to print one sequence, and not all sequences separated by "--OR--", like in the sample output?

Can someone verify this I/O?

INPUT

Code: Select all

1
A->B
2
A->B
AT->B
2
AT->B
AQ->B
4
A->B
B->C
C->D
D->A
3
A->B
B->C
A->C
6
A->B
B->C
C->A
A->C
C->B
B->A
2
A->B
A->BQ
3
A->C
A->BQ
B->C
0
OUTPUT

Code: Select all

Set number 1
No redundant FDs.

Set number 2
FD 2 is redundant using FDs: 1

Set number 3
No redundant FDs.

Set number 4
No redundant FDs.

Set number 5
FD 3 is redundant using FDs: 1 2

Set number 6
FD 1 is redundant using FDs: 4 5
FD 2 is redundant using FDs: 6 4
FD 3 is redundant using FDs: 5 6
FD 4 is redundant using FDs: 1 2
FD 5 is redundant using FDs: 3 1
FD 6 is redundant using FDs: 2 3

Set number 7
FD 1 is redundant using FDs: 2

Set number 8
FD 1 is redundant using FDs: 2 3
I print a blank line after the last case.

Thanks.

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong
I not yet start coding, but wonder how to interpret:

Each FD in an acceptable proof sequence must, however, be necessary.

Does necessary mean that we must use non-redundant FS in the proof? If yes, then how should we handle the set number 6?
My signature:
We can learn much more in discussion than reading source code.
• I HATE testing account.
• Don't send me source code for debug.

stubbscroll
Experienced poster
Posts: 151
Joined: Tue Nov 16, 2004 7:23 pm
Location: Norway
Contact:

### Re: 219 - Department of the Redundancy Department

little joey wrote:Lots of WAs, so I may be making a conceptual error...

Am I right that the line
If more than one sequence of FDs can be used to show another FD is redundant, any such sequence is acceptable, ...
means that we only have to print one sequence, and not all sequences separated by "--OR--", like in the sample output?

Can someone verify this I/O?
It's correct, only one sequence should be printed. The "--OR--" example in the output is a bit misleading. Your output is correct.
.. wrote:I not yet start coding, but wonder how to interpret:

Each FD in an acceptable proof sequence must, however, be necessary.

Does necessary mean that we must use non-redundant FS in the proof? If yes, then how should we handle the set number 6?
Necessary means that if one element is taken away from the proof sequence, it no longer makes the FD in question redundant. However, your other interpretation could be valid (as the example output does not contradict this), and I didn't think of that one. The problem statement does bring an example where all the FD's are redundant, which means that redundant FD's have to be used sometimes in a proof sequence.

And here's some I/O:

Input:

Code: Select all

42
QG->UMEA
LNFDXIR->VSCGB
KFNQDU->W
NFOZVS->TKJ
REPGX->NVYS
MWCYS->QPEV
KEFM->NI
KASVW->RENZY
EFXZB->OJUVPAY
POE->L
P->NLJVR
IPY->MEHW
NQRPM->UJLOVAW
XWHMS->C
XCOKS->ZVATD
NLY->HF
XJSWNKU->ZRBM
MGQOK->T
YHNK->AUGZQ
CDIUTE->OJW
YZ->VSCMPAJ
FVGUB->A
OVLZ->NTR
DCPWS->TE
JWHDIZC->BNFLQTV
WVXHR->B
DVGYL->BUS
MBORX->LHC
M->XO
GMNKEUF->XOTBPY
NFETCU->PZSHKL
UGEK->DQZJNPV
GX->EP
SRDZJ->ULCHBFQ
KIM->ZOBWY
XDUNF->KSRTEMQ
CYZJE->UHMS
QCOZIJP->NEDS
R->AV
MTA->BDZQSOE
UVNPS->ACBZXM
0
Output:

Code: Select all

Set number 1
FD 11 is redundant using FDs: 12
FD 19 is redundant using FDs: 1 33 12 24
FD 31 is redundant using FDs: 7 30 33 36 37
FD 38 is redundant using FDs: 22 30 12 17 24 41 10

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
Thanks for the I/O. Found a silly bug (guess all bugs are silly ) and got AC.

To Lawrence:

Consider the input:

Code: Select all

7
A->D
A->X
X->D
A->B
B->C
B->Y
C->D
To prove that FD 1 is redundant, you can either have the sequence "2 3" or the sequence "4 5 7"; they are equally valid, even though the second one is longer than the first. The sequence "4 5 6 7" also proves the redundancy of FD 1, but contains the 'unnecessary' FD 6, so it is not a valid answer.

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong
Thanks all, I get AC also
My signature:
We can learn much more in discussion than reading source code.
• I HATE testing account.
• Don't send me source code for debug.

Orgi
New poster
Posts: 11
Joined: Mon Oct 29, 2001 2:00 am
Location: Bulgaria
Can anybody tell me what's wrong with my program?
It keeps getting WA..

#include <iostream.h>
struct funcdep
{ int left;
int right;
int ind;
};
int n;
funcdep funcd[110];
funcdep proof[110];
int np;
bool checkredundancy(funcdep fd, funcdep hypo[], int nh)
{ int coverage = fd.left, i;
np = 0;
do {
for (i = 0; i < nh; i++)
if (((coverage & hypo.left) == hypo.left) &&
((coverage | hypo.right) != coverage)
)
{ coverage = coverage | hypo.right;
proof[np] = hypo;
np++;
break;
}
if (i == nh) break;
} while (1);
return (coverage & fd.right) == fd.right;
}
bool checkredundancy1(funcdep fd, funcdep hypo[], int nh)
{ int coverage = fd.left, i;
do {
for (i = 0; i < nh; i++)
if (((coverage & hypo.left) == hypo.left) &&
((coverage | hypo.right) != coverage)
)
{ coverage = coverage | hypo.right;
break;
}
if (i == nh) break;
} while (1);
return (coverage & fd.right) == fd.right;
}
void solve()
{ bool suc, suc1;
int i, j;
funcdep help;
suc = false;
for (i = 0; i < n; i++)
{ help = funcd[0];
funcd[0] = funcd;
funcd[i] = help;
suc1 = checkredundancy(funcd[0],funcd+1,n-1);
suc = suc || suc1;
help = funcd[0];
funcd[0] = funcd[i];
funcd[i] = help;
if (!suc1) continue;
do {
suc1 = false;
for (j = 0; j < np; j++)
{ help = proof[0];
proof[0] = proof[j];
proof[j] = help;
suc1 = checkredundancy1(funcd[i],proof+1,np-1);
help = proof[0];
proof[0] = proof[j];
proof[j] = help;
if (suc1) break;
}
if (suc1) { proof[j] = proof[np-1]; np--; }
} while (suc1);
cout << " FD " << (i+1) << " is redundant using FDs:";
for (j = 0; j < np; j++)
cout << " " << (proof[j].ind+1);
cout << endl;
}
if (!suc) cout << " No redundant FDs." << endl;
cout << endl;
}
int main()
{ int i, j, tst = 0;
do {
tst++;
cin >> n;
if (n == 0) break;
for (i = 0; i < n; i++)
{ char s[100];
cin >> s;
funcd[i].left = funcd[i].right = 0;
funcd[i].ind = i;
for (j = 0;;j++)
{ if (s[j] == '-') break;
if (s[j] >= 'A' && s[j] <= 'Z')
funcd[i].left = funcd[i].left | (1 << (s[j]-'A'));
}
j += 2;
for(;;j++)
{ if (s[j] >= 'A' && s[j] <= 'Z')
funcd[i].right = funcd[i].right | (1 << (s[j]-'A'));
else break;
}
}
cout << "Set number " << tst << endl;
solve();
} while (1);
cout.flush();
return 0;
}

Orgi
New poster
Posts: 11
Joined: Mon Oct 29, 2001 2:00 am
Location: Bulgaria
Can anybody tell me if my answer to the above test with 42 functional dependencies is correct?
The output is:
------
Set number 1
FD 11 is redundant using FDs: 12
FD 19 is redundant using FDs: 34 30 17 16 5 15 14 12
FD 31 is redundant using FDs: 33 30 18 16 5 15 7 13 12
FD 38 is redundant using FDs: 30 22 17 4 14 6 7 13 12

------
I'd be grateful to those who got AC, if they could give me some tricky tests.