3 (N1 = # "good" pairings <= 100,000) A B G L J K 2 (N2 = # "bad" pairings <= 100,000) D F D G 4 (N3 = # paired groups <= 100,000) A C G B D F E H I J K L |
Solution steps
Read and store "good" pairing (size: ~ 200,000)
Read and store "bad" pairing (size: ~ 200,000)
Read and store pairing groups (size: ~ 300,000)
NViolations = 0;
for each "good" pair:
if pair not found in pair group: NViolations++
for each "bad" pair:
if pair found in pair group: NViolations++
|
How do we store the groups ?
3
A B
G L
J K
2
D F
D G
4
A C G
B D F
E H I
J K L
|
Use an (2 dimensional) array
3 A B GoodPair[0][0] = "A" GoodPair[0][1] = "B" G L ^ ^ J K | | 2 +----- 1st pair -----+ D F D G 4 A C G B D F E H I J K L |
Result:
3 A B GoodPair[0][0] = "A" GoodPair[0][1] = "B" G L GoodPair[1][0] = "G" GoodPair[1][1] = "L" J K GoodPair[2][0] = "J" GoodPair[2][1] = "K" 2 D F BadPair[0][0] = "D" BadPair[0][1] = "F" D G BadPair[1][0] = "D" BadPair[1][1] = "G" 4 A C G B D F E H I J K L |
How to store the pairings ???
3
A B GoodPair[0][0] = "A" GoodPair[0][1] = "B"
G L GoodPair[1][0] = "G" GoodPair[1][1] = "L"
J K GoodPair[2][0] = "J" GoodPair[2][1] = "K"
2
D F BadPair[0][0] = "D" BadPair[0][1] = "F"
D G BadPair[1][0] = "D" BadPair[1][1] = "G"
4
A C G
B D F
E H I
J K L
|
Let's also use a (2-dimensional) array:
3 A B GoodPair[0][0] = "A" GoodPair[0][1] = "B" G L GoodPair[1][0] = "G" GoodPair[1][1] = "L" J K GoodPair[2][0] = "J" GoodPair[2][1] = "K" 2 D F BadPair[0][0] = "D" BadPair[0][1] = "F" D G BadPair[1][0] = "D" BadPair[1][1] = "G" 4 A C G Grp[0][0] = "A" Grp[0][1] = "C" Grp[0][2] = "G" B D F E H I J K L |
Result:
3 A B GoodPair[0][0] = "A" GoodPair[0][1] = "B" G L GoodPair[1][0] = "G" GoodPair[1][1] = "L" J K GoodPair[2][0] = "J" GoodPair[2][1] = "K" 2 D F BadPair[0][0] = "D" BadPair[0][1] = "F" D G BadPair[1][0] = "D" BadPair[1][1] = "G" 4 A C G Grp[0][0] = "A" Grp[0][1] = "C" Grp[0][2] = "G" B D F Grp[1][0] = "B" Grp[1][1] = "D" Grp[1][2] = "F" E H I Grp[2][0] = "E" Grp[2][1] = "H" Grp[2][2] = "I" J K L Grp[3][0] = "J" Grp[3][1] = "K" Grp[3][2] = "L" |
Next: write the program using the data structure than we have chosen :
3
A B GoodPair[0][0] = "A" GoodPair[0][1] = "B"
G L GoodPair[1][0] = "G" GoodPair[1][1] = "L"
J K GoodPair[2][0] = "J" GoodPair[2][1] = "K"
2
D F BadPair[0][0] = "D" BadPair[0][1] = "F"
D G BadPair[1][0] = "D" BadPair[1][1] = "G"
4
A C G Grp[0][0] = "A" Grp[0][1] = "C" Grp[0][2] = "G"
B D F Grp[1][0] = "B" Grp[1][1] = "D" Grp[1][2] = "F"
E H I Grp[2][0] = "E" Grp[2][1] = "H" Grp[2][2] = "I"
J K L Grp[3][0] = "J" Grp[3][1] = "K" Grp[3][2] = "L"
for each "good" pair:
if pair not found in pair group: NViolations++
|
Next: write the program using the data structure than we have chosen :
3
A B GoodPair[0][0] = "A" GoodPair[0][1] = "B"
G L GoodPair[1][0] = "G" GoodPair[1][1] = "L"
J K GoodPair[2][0] = "J" GoodPair[2][1] = "K"
2
D F BadPair[0][0] = "D" BadPair[0][1] = "F"
D G BadPair[1][0] = "D" BadPair[1][1] = "G"
4
A C G Grp[0][0] = "A" Grp[0][1] = "C" Grp[0][2] = "G"
B D F Grp[1][0] = "B" Grp[1][1] = "D" Grp[1][2] = "F"
E H I Grp[2][0] = "E" Grp[2][1] = "H" Grp[2][2] = "I"
J K L Grp[3][0] = "J" Grp[3][1] = "K" Grp[3][2] = "L"
for (int i = 0; i < N1; i++)
if GoodPair[i] not found in pair group: NViolations++
--> We must determine the group of GoodPair[i][0] and GoodPair[i][1]
|
Next: write the program using the data structure than we have chosen :
3
A B GoodPair[0][0] = "A" GoodPair[0][1] = "B"
G L GoodPair[1][0] = "G" GoodPair[1][1] = "L"
J K GoodPair[2][0] = "J" GoodPair[2][1] = "K"
2
D F BadPair[0][0] = "D" BadPair[0][1] = "F"
D G BadPair[1][0] = "D" BadPair[1][1] = "G"
4
A C G Grp[0][0] = "A" Grp[0][1] = "C" Grp[0][2] = "G"
B D F Grp[1][0] = "B" Grp[1][1] = "D" Grp[1][2] = "F"
E H I Grp[2][0] = "E" Grp[2][1] = "H" Grp[2][2] = "I"
J K L Grp[3][0] = "J" Grp[3][1] = "K" Grp[3][2] = "L"
for (int i = 0; i < N1; i++)
find Grp of GoodPair[i][0] ---> store group in g0
find Grp of GoodPair[i][1] ---> store group in g1
if (g0 != g1) NViolations++
|
Next: write the program using the data structure than we have chosen :
3
A B GoodPair[0][0] = "A" GoodPair[0][1] = "B"
G L GoodPair[1][0] = "G" GoodPair[1][1] = "L"
J K GoodPair[2][0] = "J" GoodPair[2][1] = "K"
2
D F BadPair[0][0] = "D" BadPair[0][1] = "F"
D G BadPair[1][0] = "D" BadPair[1][1] = "G"
4
A C G Grp[0][0] = "A" Grp[0][1] = "C" Grp[0][2] = "G"
B D F Grp[1][0] = "B" Grp[1][1] = "D" Grp[1][2] = "F"
E H I Grp[2][0] = "E" Grp[2][1] = "H" Grp[2][2] = "I"
J K L Grp[3][0] = "J" Grp[3][1] = "K" Grp[3][2] = "L"
for (int i = 0; i < N1; i++)
for (int j = 0; j < N3; j++) // Check every group...
if GoodPair[i][0] in Grp[j]: g0 = j // Grp[j] has 3 members !
find Grp of GoodPair[i][1] ---> store group in g1
if (g0 != g1) NViolations++
|
Next: write the program using the data structure than we have chosen :
3
A B GoodPair[0][0] = "A" GoodPair[0][1] = "B"
G L GoodPair[1][0] = "G" GoodPair[1][1] = "L"
J K GoodPair[2][0] = "J" GoodPair[2][1] = "K"
2
D F BadPair[0][0] = "D" BadPair[0][1] = "F"
D G BadPair[1][0] = "D" BadPair[1][1] = "G"
4
A C G Grp[0][0] = "A" Grp[0][1] = "C" Grp[0][2] = "G"
B D F Grp[1][0] = "B" Grp[1][1] = "D" Grp[1][2] = "F"
E H I Grp[2][0] = "E" Grp[2][1] = "H" Grp[2][2] = "I"
J K L Grp[3][0] = "J" Grp[3][1] = "K" Grp[3][2] = "L"
for (int i = 0; i < N1; i++)
for (int j = 0; j < N3; j++)
if (Grp[j][0] == GoodPair[i][0] || Grp[j][1] == GoodPair[i][0]
|| Grp[j][2] == GoodPair[i][0]) g0 = j, break;
find GoodPair[i][1] in Grp[] ---> g1 // Do same for GoodPair[i][1]
if (g0 != g1) NViolations++
|
Next: write the program using the data structure than we have chosen :
3
A B GoodPair[0][0] = "A" GoodPair[0][1] = "B"
G L GoodPair[1][0] = "G" GoodPair[1][1] = "L"
J K GoodPair[2][0] = "J" GoodPair[2][1] = "K"
2
D F BadPair[0][0] = "D" BadPair[0][1] = "F"
D G BadPair[1][0] = "D" BadPair[1][1] = "G"
4
A C G Grp[0][0] = "A" Grp[0][1] = "C" Grp[0][2] = "G"
B D F Grp[1][0] = "B" Grp[1][1] = "D" Grp[1][2] = "F"
E H I Grp[2][0] = "E" Grp[2][1] = "H" Grp[2][2] = "I"
J K L Grp[3][0] = "J" Grp[3][1] = "K" Grp[3][2] = "L"
for (int i = 0; i < N1; i++)
for (int j = 0; j < N3; j++)
if (Grp[j][0] == GoodPair[i][0] || Grp[j][1] == GoodPair[i][0]
|| Grp[j][2] == GoodPair[i][0]) g0 = j, break;
find GoodPair[i][1] in Grp[] ---> g1
if (g0 != g1) NViolations++
Code for "BadPair" is similar...
|
Solution:
// Process "Good pairs"
for (int i = 0; i < N1; i++)
{
// Find the group of GoodPair[i][0]
for (int j = 0; j < N3; j++)
{
if (Grp[j][0] == GoodPair[i][0] || Grp[j][1] == GoodPair[i][0]
|| Grp[j][2] == GoodPair[i][0])
{
g0 = j; // Found GoodPair[i][0]'s group
break;
}
}
// Find the group of GoodPair[i][1]
for (int j = 0; j < N3; j++)
{
if (Grp[j][0] == GoodPair[i][1] || Grp[j][1] == GoodPair[i][1]
|| Grp[j][2] == GoodPair[i][1])
{
g1 = j; // Found GoodPair[i][1]'s group
break;
}
}
// Check violation
if (g0 != g1) NViolations++;
}
// Process "BadPairs"
for (int i = 0; i < N2; i++)
{
// Find the group of BadPair[i][0]
for (int j = 0; j < N3; j++)
{
if (Grp[j][0] == BadPair[i][0] || Grp[j][1] == BadPair[i][0]
|| Grp[j][2] == BadPair[i][0])
{
g0 = j; // Found BadPair[i][0]'s group
break;
}
}
// Find the group of BadPair[i][1]
for (int j = 0; j < N3; j++)
{
if (Grp[j][0] == BadPair[i][1] || Grp[j][1] == BadPair[i][1]
|| Grp[j][2] == BadPair[i][1])
{
g1 = j;
break;
}
}
// Check violation
if (g0 == g1) NViolations++;
}
cout << "\nAnswer: " << NViolations << endl;
|
Demo: CCC/2022/Progs/j4.cc
It's inefficient ! How many times is the inner code executed ?
// Process "Good pairs"
for (int i = 0; i < N1; i++)
{
// Find the group of GoodPair[i][0]
for (int j = 0; j < N3; j++)
{
if (Grp[j][0] == GoodPair[i][0] || Grp[j][1] == GoodPair[i][0]
|| Grp[j][2] == GoodPair[i][0])
{
g0 = j; // Found GoodPair[i][0]'s group
break;
}
}
// Find the group of GoodPair[i][1]
for (int j = 0; j < N3; j++)
{
if (Grp[j][0] == GoodPair[i][1] || Grp[j][1] == GoodPair[i][1]
|| Grp[j][2] == GoodPair[i][1])
{
g1 = j; // Found GoodPair[i][1]'s group
break;
}
}
// Check violation
if (g0 != g1) NViolations++;
}
....
|
The inner code is executed N1*N3 times (100,000 * 100,000 = 10,000,000,000 !) May fail the last test...
// Process "Good pairs"
for (int i = 0; i < N1; i++)
{
// Find the group of GoodPair[i][0]
for (int j = 0; j < N3; j++)
{
if (Grp[j][0] == GoodPair[i][0] || Grp[j][1] == GoodPair[i][0]
|| Grp[j][2] == GoodPair[i][0])
{
g0 = j; // Found GoodPair[i][0]'s group
break;
}
}
// Find the group of GoodPair[i][1]
for (int j = 0; j < N3; j++)
{
if (Grp[j][0] == GoodPair[i][1] || Grp[j][1] == GoodPair[i][1]
|| Grp[j][2] == GoodPair[i][1])
{
g1 = j; // Found GoodPair[i][1]'s group
break;
}
}
// Check violation
if (g0 != g1) NViolations++;
}
....
|