219 - Department of Redundancy Department

little joey · Post by **little joey** » Sun May 13, 2007 10:52 am

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.

.. · Post by .. » Sun May 13, 2007 11:10 am

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?

stubbscroll · Post by **stubbscroll** » Sun May 13, 2007 11:40 am

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
XFTL->GYPSADO
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 · Post by **little joey** » Sun May 13, 2007 12:34 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.

.. · Post by .. » Sun May 13, 2007 3:03 pm

Thanks all, I get AC also

Orgi · Post by **Orgi** » Wed Dec 05, 2007 1:35 pm

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 · Post by **Orgi** » Thu Jan 03, 2008 6:48 pm

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.

OJ Board

219 - Department of Redundancy Department

219 - Department of Redundancy Department

Re: 219 - Department of the Redundancy Department