3 (# "good" pairings <= 100,000) A B G L J K 2 (# "bad" pairings <= 100,000) D F D G 4 (# 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)
score = 0;
for each "good" pair:
if pair found in pair group: score++
for each "bad" pair:
if pair found in pair group: score--
|
Naive solution: use arrays
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" |
Naive solution: problem
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 found in pair group: score++ Try find: (GoodPair[2][0] = "J" GoodPair[2][1] = "K") in Grp[][] (search !) |
Improved solution: use a map the name to an index
3 A B GoodPair[0][0] = GoodPair[0][1] = G L GoodPair[1][0] = GoodPair[1][1] = J K GoodPair[2][0] = GoodPair[2][1] = 2 D F BadPair[0][0] = BadPair[0][1] = D G BadPair[1][0] = BadPair[1][1] = 4 A C G B D F E H I J K L NextIndex = 0 Map: (empty) |
Processing "good" pairs: read in a pair and assign the names to a unique index
3
A B GoodPair[0][0] = GoodPair[0][1] =
G L GoodPair[1][0] = GoodPair[1][1] =
J K GoodPair[2][0] = GoodPair[2][1] =
2
D F BadPair[0][0] = BadPair[0][1] =
D G BadPair[1][0] = BadPair[1][1] =
4
A C G
B D F
E H I
J K L
NextIndex = 2 ---> Map: A -> 0 B -> 1
Map: (empty)
|
Processing "good" pairs: store the name -> index assignment in a map for quick access
3
A B GoodPair[0][0] = GoodPair[0][1] =
G L GoodPair[1][0] = GoodPair[1][1] =
J K GoodPair[2][0] = GoodPair[2][1] =
2
D F BadPair[0][0] = BadPair[0][1] =
D G BadPair[1][0] = BadPair[1][1] =
4
A C G
B D F
E H I
J K L
NextIndex = 2 ---> Map: A -> 0 B -> 1
Map: A -> 0
B -> 1
|
Processing "good" pairs: record the "good" pair using indexes
3
A B GoodPair[0][0] = 0 GoodPair[0][1] = 1
G L GoodPair[1][0] = GoodPair[1][1] =
J K GoodPair[2][0] = GoodPair[2][1] =
2
D F BadPair[0][0] = BadPair[0][1] =
D G BadPair[1][0] = BadPair[1][1] =
4
A C G
B D F
E H I
J K L
NextIndex = 2 ---> Map: A -> 0 B -> 1
Map: A -> 0
B -> 1
|
Processing "good" pairs: read the next "good" pair
3
A B GoodPair[0][0] = 0 GoodPair[0][1] = 1
G L GoodPair[1][0] = GoodPair[1][1] =
J K GoodPair[2][0] = GoodPair[2][1] =
2
D F BadPair[0][0] = BadPair[0][1] =
D G BadPair[1][0] = BadPair[1][1] =
4
A C G
B D F
E H I
J K L
NextIndex = 4 ---> Map: G -> 2 L -> 3
Map: A -> 0
B -> 1
|
Processing "good" pairs: store the next "good" pair
3
A B GoodPair[0][0] = 0 GoodPair[0][1] = 1
G L GoodPair[1][0] = 2 GoodPair[1][1] = 3
J K GoodPair[2][0] = GoodPair[2][1] =
2
D F BadPair[0][0] = BadPair[0][1] =
D G BadPair[1][0] = BadPair[1][1] =
4
A C G
B D F
E H I
J K L
NextIndex = 4 ---> Map: G -> 2 L -> 3
Map: A -> 0
B -> 1
G -> 2
L -> 3
|
Processing "good" pairs: read the next "good" pair
3
A B GoodPair[0][0] = 0 GoodPair[0][1] = 1
G L GoodPair[1][0] = 2 GoodPair[1][1] = 3
J K GoodPair[2][0] = GoodPair[2][1] =
2
D F BadPair[0][0] = BadPair[0][1] =
D G BadPair[1][0] = BadPair[1][1] =
4
A C G
B D F
E H I
J K L
NextIndex = 6 ---> Map: J -> 4 K -> 5
Map: A -> 0 J -> 4
B -> 1 K -> 5
G -> 2
L -> 3
|
Processing "good" pairs: store the next "good" pair
3
A B GoodPair[0][0] = 0 GoodPair[0][1] = 1
G L GoodPair[1][0] = 2 GoodPair[1][1] = 3
J K GoodPair[2][0] = 4 GoodPair[2][1] = 5
2
D F BadPair[0][0] = BadPair[0][1] =
D G BadPair[1][0] = BadPair[1][1] =
4
A C G
B D F
E H I
J K L
NextIndex = 6 ---> Map: J -> 4 K -> 5
Map: A -> 0 J -> 4
B -> 1 K -> 5
G -> 2
L -> 3
|
Processing "bad" pairs: same procedure - I will do it quicker....
3
A B GoodPair[0][0] = 0 GoodPair[0][1] = 1
G L GoodPair[1][0] = 2 GoodPair[1][1] = 3
J K GoodPair[2][0] = 4 GoodPair[2][1] = 5
2
D F BadPair[0][0] = BadPair[0][1] =
D G BadPair[1][0] = BadPair[1][1] =
4
A C G
B D F
E H I
J K L
NextIndex = 6
Map: A -> 0 J -> 4
B -> 1 K -> 5
G -> 2
L -> 3
|
Processing "bad" pairs: same procedure - I will do it quicker....
3
A B GoodPair[0][0] = 0 GoodPair[0][1] = 1
G L GoodPair[1][0] = 2 GoodPair[1][1] = 3
J K GoodPair[2][0] = 4 GoodPair[2][1] = 5
2
D F BadPair[0][0] = 6 BadPair[0][1] = 7
D G BadPair[1][0] = BadPair[1][1] =
4
A C G
B D F
E H I
J K L
NextIndex = 8 ---> Map: D -> 6 F -> 7
Map: A -> 0 J -> 4
B -> 1 K -> 5
G -> 2 D -> 6
L -> 3 F -> 7
|
Processing "bad" pairs: same procedure - I will do it quicker....
3 A B GoodPair[0][0] = 0 GoodPair[0][1] = 1 G L GoodPair[1][0] = 2 GoodPair[1][1] = 3 J K GoodPair[2][0] = 4 GoodPair[2][1] = 5 2 D F BadPair[0][0] = 6 BadPair[0][1] = 7 D G BadPair[1][0] = BadPair[1][1] = 4 A C G B D F E H I J K L NextIndex = 8 (Note: D and G are found in the map !) Map: A -> 0 J -> 4 B -> 1 K -> 5 G -> 2 D -> 6 L -> 3 F -> 7 |
Processing "bad" pairs: same procedure - I will do it quicker....
3 A B GoodPair[0][0] = 0 GoodPair[0][1] = 1 G L GoodPair[1][0] = 2 GoodPair[1][1] = 3 J K GoodPair[2][0] = 4 GoodPair[2][1] = 5 2 D F BadPair[0][0] = 6 BadPair[0][1] = 7 D G BadPair[1][0] = 6 BadPair[1][1] = 2 4 A C G B D F E H I J K L NextIndex = 8 ---> Map: no new entry ! Map: A -> 0 J -> 4 B -> 1 K -> 5 G -> 2 D -> 6 L -> 3 F -> 7 |
Processing paired groups: design a representation that let you find same group quickly !
3
A B GoodPair[0][0] = 0 GoodPair[0][1] = 1
G L GoodPair[1][0] = 2 GoodPair[1][1] = 3
J K GoodPair[2][0] = 4 GoodPair[2][1] = 5
2
D F BadPair[0][0] = 6 BadPair[0][1] = 7
D G BadPair[1][0] = 6 BadPair[1][1] = 2
4
A C G
B D F
E H I
J K L
NextIndex = 8
Map: A -> 0 J -> 4
B -> 1 K -> 5
G -> 2 D -> 6
L -> 3 F -> 7
|
Processing paired groups: store group ID in array indexed by name
3
A B GoodPair[0][0] = 0 GoodPair[0][1] = 1
G L GoodPair[1][0] = 2 GoodPair[1][1] = 3
J K GoodPair[2][0] = 4 GoodPair[2][1] = 5
2
D F BadPair[0][0] = 6 BadPair[0][1] = 7
D G BadPair[1][0] = 6 BadPair[1][1] = 2
4
A C G Something like this: Grp["A"] = 0 Grp["C"] = 0 Grp["G"] = 0
B D F
E H I (But C++ uses integer indexes)
J K L
NextIndex = 8
Map: A -> 0 J -> 4
B -> 1 K -> 5
G -> 2 D -> 6
L -> 3 F -> 7
|
Processing paired groups: store group ID in array indexed by name
3
A B GoodPair[0][0] = 0 GoodPair[0][1] = 1
G L GoodPair[1][0] = 2 GoodPair[1][1] = 3
J K GoodPair[2][0] = 4 GoodPair[2][1] = 5
2
D F BadPair[0][0] = 6 BadPair[0][1] = 7
D G BadPair[1][0] = 6 BadPair[1][1] = 2
4
A C G Something like this: Grp["A"] = 0 Grp["C"] = 0 Grp["G"] = 0
B D F
E H I (But C++ uses integer indexes)
J K L Use the map to translate: "A" => 0, "C" => int index, "G" => 2
NextIndex = 8
Map: A -> 0 J -> 4
B -> 1 K -> 5
G -> 2 D -> 6
L -> 3 F -> 7
|
Read more on
the C++ map class here:
(Demo: alienware::~cheung/OutSchool/compet-prog/DataStruct/map/)
Processing paired groups: read the next group
3
A B GoodPair[0][0] = 0 GoodPair[0][1] = 1
G L GoodPair[1][0] = 2 GoodPair[1][1] = 3
J K GoodPair[2][0] = 4 GoodPair[2][1] = 5
2
D F BadPair[0][0] = 6 BadPair[0][1] = 7
D G BadPair[1][0] = 6 BadPair[1][1] = 2
4
A C G Grp[0] = Grp[4] = Grp[8] =
B D F Grp[1] = Grp[5] = Grp[9] =
E H I Grp[2] = Grp[6] = Grp[10] =
J K L Grp[3] = Grp[7] = Grp[11] =
NextIndex = 8
Map: A -> 0 J -> 4
B -> 1 K -> 5
G -> 2 D -> 6
L -> 3 F -> 7
|
Processing paired groups: map the unknown names
3
A B GoodPair[0][0] = 0 GoodPair[0][1] = 1
G L GoodPair[1][0] = 2 GoodPair[1][1] = 3
J K GoodPair[2][0] = 4 GoodPair[2][1] = 5
2
D F BadPair[0][0] = 6 BadPair[0][1] = 7
D G BadPair[1][0] = 6 BadPair[1][1] = 2
4
A C G Grp[0] = Grp[4] = Grp[8] =
B D F Grp[1] = Grp[5] = Grp[9] =
E H I Grp[2] = Grp[6] = Grp[10] =
J K L Grp[3] = Grp[7] = Grp[11] =
NextIndex = 9 ---> Map: C -> 8
Map: A -> 0 J -> 4 C -> 8
B -> 1 K -> 5
G -> 2 D -> 6
L -> 3 F -> 7
|
Processing paired groups: store the group
3
A B GoodPair[0][0] = 0 GoodPair[0][1] = 1
G L GoodPair[1][0] = 2 GoodPair[1][1] = 3
J K GoodPair[2][0] = 4 GoodPair[2][1] = 5
2
D F BadPair[0][0] = 6 BadPair[0][1] = 7
D G BadPair[1][0] = 6 BadPair[1][1] = 8
4
A C G Grp[0] = 0 Grp[4] = Grp[8] = 0
B D F Grp[1] = Grp[5] = Grp[9] =
E H I Grp[2] = 0 Grp[6] = Grp[10] =
J K L Grp[3] = Grp[7] = Grp[11] =
NextIndex = 9
Map: A -> 0 J -> 4 C -> 8
B -> 1 K -> 5
G -> 2 D -> 6
L -> 3 F -> 7
|
Processing paired groups: read the group
3
A B GoodPair[0][0] = 0 GoodPair[0][1] = 1
G L GoodPair[1][0] = 2 GoodPair[1][1] = 3
J K GoodPair[2][0] = 4 GoodPair[2][1] = 5
2
D F BadPair[0][0] = 6 BadPair[0][1] = 7
D G BadPair[1][0] = 6 BadPair[1][1] = 8
4
A C G Grp[0] = 0 Grp[4] = Grp[8] = 0
B D F Grp[1] = Grp[5] = Grp[9] =
E H I Grp[2] = 0 Grp[6] = Grp[10] =
J K L Grp[3] = Grp[7] = Grp[11] =
NextIndex = 9
Map: A -> 0 J -> 4 C -> 8
B -> 1 K -> 5
G -> 2 D -> 6
L -> 3 F -> 7
|
Processing paired groups: map the unknown names
3
A B GoodPair[0][0] = 0 GoodPair[0][1] = 1
G L GoodPair[1][0] = 2 GoodPair[1][1] = 3
J K GoodPair[2][0] = 4 GoodPair[2][1] = 5
2
D F BadPair[0][0] = 6 BadPair[0][1] = 7
D G BadPair[1][0] = 6 BadPair[1][1] = 8
4
A C G Grp[0] = 0 Grp[4] = Grp[8] = 0
B D F Grp[1] = Grp[5] = Grp[9] =
E H I Grp[2] = 0 Grp[6] = Grp[10] =
J K L Grp[3] = Grp[7] = Grp[11] =
NextIndex = 9 ---> Map: no new entry !
Map: A -> 0 J -> 4 C -> 8
B -> 1 K -> 5
G -> 2 D -> 6
L -> 3 F -> 7
|
Processing paired groups: store the group
3
A B GoodPair[0][0] = 0 GoodPair[0][1] = 1
G L GoodPair[1][0] = 2 GoodPair[1][1] = 3
J K GoodPair[2][0] = 4 GoodPair[2][1] = 5
2
D F BadPair[0][0] = 6 BadPair[0][1] = 7
D G BadPair[1][0] = 6 BadPair[1][1] = 8
4
A C G Grp[0] = 0 Grp[4] = Grp[8] = 0
B D F Grp[1] = 1 Grp[5] = Grp[9] =
E H I Grp[2] = 0 Grp[6] = 1 Grp[10] =
J K L Grp[3] = Grp[7] = 1 Grp[11] =
NextIndex = 9
Map: A -> 0 J -> 4 C -> 8
B -> 1 K -> 5
G -> 2 D -> 6
L -> 3 F -> 7
|
Processing paired groups: process the next group - I will do it quicker...
3
A B GoodPair[0][0] = 0 GoodPair[0][1] = 1
G L GoodPair[1][0] = 2 GoodPair[1][1] = 3
J K GoodPair[2][0] = 4 GoodPair[2][1] = 5
2
D F BadPair[0][0] = 6 BadPair[0][1] = 7
D G BadPair[1][0] = 6 BadPair[1][1] = 8
4
A C G Grp[0] = 0 Grp[4] = Grp[8] = 0
B D F Grp[1] = 1 Grp[5] = Grp[9] =
E H I Grp[2] = 0 Grp[6] = 1 Grp[10] =
J K L Grp[3] = Grp[7] = 1 Grp[11] =
NextIndex = 9
Map: A -> 0 J -> 4 C -> 8
B -> 1 K -> 5
G -> 2 D -> 6
L -> 3 F -> 7
|
Processing paired groups: process the next group - I will do it quicker...
3
A B GoodPair[0][0] = 0 GoodPair[0][1] = 1
G L GoodPair[1][0] = 2 GoodPair[1][1] = 3
J K GoodPair[2][0] = 4 GoodPair[2][1] = 5
2
D F BadPair[0][0] = 6 BadPair[0][1] = 7
D G BadPair[1][0] = 6 BadPair[1][1] = 8
4
A C G Grp[0] = 0 Grp[4] = Grp[8] = 0
B D F Grp[1] = 1 Grp[5] = Grp[9] = 2
E H I Grp[2] = 0 Grp[6] = 1 Grp[10] = 2
J K L Grp[3] = Grp[7] = 1 Grp[11] = 2
NextIndex = 9 ----> Map: E -> 9 H -> 10 I -> 11
Map: A -> 0 J -> 4 C -> 8
B -> 1 K -> 5 E -> 9
G -> 2 D -> 6 H -> 10
L -> 3 F -> 7 I -> 11
|
Processing paired groups: process the next group - I will do it quicker...
3
A B GoodPair[0][0] = 0 GoodPair[0][1] = 1
G L GoodPair[1][0] = 2 GoodPair[1][1] = 3
J K GoodPair[2][0] = 4 GoodPair[2][1] = 5
2
D F BadPair[0][0] = 6 BadPair[0][1] = 7
D G BadPair[1][0] = 6 BadPair[1][1] = 8
4
A C G Grp[0] = 0 Grp[4] = Grp[8] = 0
B D F Grp[1] = 1 Grp[5] = Grp[9] = 2
E H I Grp[2] = 0 Grp[6] = 1 Grp[10] = 2
J K L Grp[3] = Grp[7] = 1 Grp[11] = 2
NextIndex = 9
Map: A -> 0 J -> 4 C -> 8
B -> 1 K -> 5 E -> 9
G -> 2 D -> 6 H -> 10
L -> 3 F -> 7 I -> 11
|
Processing paired groups: process the next group - I will do it quicker...
3
A B GoodPair[0][0] = 0 GoodPair[0][1] = 1
G L GoodPair[1][0] = 2 GoodPair[1][1] = 3
J K GoodPair[2][0] = 4 GoodPair[2][1] = 5
2
D F BadPair[0][0] = 6 BadPair[0][1] = 7
D G BadPair[1][0] = 6 BadPair[1][1] = 8
4
A C G Grp[0] = 0 Grp[4] = 3 Grp[8] = 0
B D F Grp[1] = 1 Grp[5] = 3 Grp[9] = 2
E H I Grp[2] = 0 Grp[6] = 1 Grp[10] = 2
J K L Grp[3] = 3 Grp[7] = 1 Grp[11] = 2
NextIndex = 9 ----> Map: no new entry !
Map: A -> 0 J -> 4 C -> 8
B -> 1 K -> 5 E -> 9
G -> 2 D -> 6 H -> 10
L -> 3 F -> 7 I -> 11
|
Computing the score:
3
A B GoodPair[0][0] = 0 GoodPair[0][1] = 1
G L GoodPair[1][0] = 2 GoodPair[1][1] = 3
J K GoodPair[2][0] = 4 GoodPair[2][1] = 5
2
D F BadPair[0][0] = 6 BadPair[0][1] = 7
D G BadPair[1][0] = 6 BadPair[1][1] = 8
4
A C G Grp[0] = 0 Grp[4] = 3 Grp[8] = 0
B D F Grp[1] = 1 Grp[5] = 3 Grp[9] = 2
E H I Grp[2] = 0 Grp[6] = 1 Grp[10] = 2
J K L Grp[3] = 3 Grp[7] = 1 Grp[11] = 2
for each "good" pair:
if pair found in pair group: score++
Do we still need to search ?
|
Computing the score:
3 A B GoodPair[0][0] = 0 GoodPair[0][1] = 1 G L GoodPair[1][0] = 2 GoodPair[1][1] = 3 J K GoodPair[2][0] = 4 GoodPair[2][1] = 5 2 D F BadPair[0][0] = 6 BadPair[0][1] = 7 D G BadPair[1][0] = 6 BadPair[1][1] = 8 4 A C G Grp[0] = 0 Grp[4] = 3 Grp[8] = 0 B D F Grp[1] = 1 Grp[5] = 3 Grp[9] = 2 E H I Grp[2] = 0 Grp[6] = 1 Grp[10] = 2 J K L Grp[3] = 3 Grp[7] = 1 Grp[11] = 2 for each "good" pair: if pair found in pair group: score++ Do we still need to search ? A B are in different groups |
Computing the score:
3 A B GoodPair[0][0] = 0 GoodPair[0][1] = 1 G L GoodPair[1][0] = 2 GoodPair[1][1] = 3 J K GoodPair[2][0] = 4 GoodPair[2][1] = 5 2 D F BadPair[0][0] = 6 BadPair[0][1] = 7 D G BadPair[1][0] = 6 BadPair[1][1] = 8 4 A C G Grp[0] = 0 Grp[4] = 3 Grp[8] = 0 B D F Grp[1] = 1 Grp[5] = 3 Grp[9] = 2 E H I Grp[2] = 0 Grp[6] = 1 Grp[10] = 2 J K L Grp[3] = 3 Grp[7] = 1 Grp[11] = 2 for each "good" pair: if pair found in pair group: score++ Do we still need to search ? J K are in same group ! |