-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathMagicMoleculeEasy.html
21 lines (21 loc) · 7.65 KB
/
MagicMoleculeEasy.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
<html><body bgcolor="#000000" text="#ffffff"><table><tr><td colspan="2"><h3>Problem Statement</h3></td></tr><tr><td>    </td><td>Fox Ciel is learning magical physics. Currently, she studies Magic Molecules. Each Magic Molecule consists of some Magic Atoms. Each Magic Atom stores some Magic Power, with different atoms possibly storing different amounts of power. Within the molecule, some pairs of atoms are connected by bidirectional Magic Bonds.
<br></br><br></br>
Ciel now has a Magic Molecule formed by n Magic Atoms. The atoms are numbered 0 through n-1, inclusive. You are given a vector <int> <b>magicPower</b> with n elements: For each i, the amount of power stored in the Magic Atom number i is <b>magicPower</b>[i]. You are also given a vector <string> <b>magicBond</b> with n elements, each containing n characters.
Character j of element i of <b>magicBond</b> is 'Y' if the Magic Atoms i and j are connected by a Magic Bond. Otherwise, character j of element i of <b>magicBond</b> is 'N'.
<br></br><br></br>
Your task is to improve Ciel's Magic Molecule. You have to choose a subset S of the n Magic Atoms so that the following two conditions are met:
<ol>
<li>You are given a int <b>k</b>. The subset S must contain exactly <b>k</b> atoms.</li>
<li>For each pair of the given n atoms that are connected by a Magic Bond, at least one of these two atoms must belong to S.</li>
</ol>
Your goal is to maximize the total Magic Power stored in the chosen atoms. Compute and return the maximum total amount of power. If it is impossible to choose a subset of atoms that satisfies the above criteria, return -1 instead.</td></tr><tr><td colspan="2"><h3>Definition</h3></td></tr><tr><td>    </td><td><table><tr><td>Class:</td><td>MagicMoleculeEasy</td></tr><tr><td>Method:</td><td>maxMagicPower</td></tr><tr><td>Parameters:</td><td>vector <int>, vector <string>, int</td></tr><tr><td>Returns:</td><td>int</td></tr><tr><td>Method signature:</td><td>int maxMagicPower(vector <int> magicPower, vector <string> magicBond, int k)</td></tr><tr><td colspan="2">(be sure your method is public)</td></tr></table></td></tr><tr><td>    </td></tr><tr><td></td></tr><tr><td colspan="2"><h3>Constraints</h3></td></tr><tr><td align="center" valign="top">-</td><td><b>k</b> will be between 1 and min(n, 14), inclusive, where n is the number of elements in <b>magicPower</b>.</td></tr><tr><td align="center" valign="top">-</td><td><b>magicPower</b> will contain between 2 and 50 elements, inclusive.</td></tr><tr><td align="center" valign="top">-</td><td>Each element in <b>magicPower</b> will be between 1 and 100,000, inclusive.</td></tr><tr><td align="center" valign="top">-</td><td><b>magicBond</b> and <b>magicPower</b> will contain the same number of elements.</td></tr><tr><td align="center" valign="top">-</td><td>Each element of <b>magicPower</b> will contain exactly n characters, where n is the number of elements in <b>magicPower</b>.</td></tr><tr><td align="center" valign="top">-</td><td>Each element of <b>magicPower</b> will only contain the characters 'Y' and 'N'.</td></tr><tr><td align="center" valign="top">-</td><td>For each valid i, <b>magicPower</b>[i][i] will be 'N'.</td></tr><tr><td align="center" valign="top">-</td><td>For each valid i and j, <b>magicPower</b>[i][j] will be equal to <b>magicPower</b>[j][i].</td></tr><tr><td colspan="2"><h3>Examples</h3></td></tr><tr><td align="center" nowrap="true">0)</td><td></td></tr><tr><td>    </td><td><table><tr><td><table><tr><td><pre>{1, 2}</pre></td></tr><tr><td><pre>{"NY",
"YN"}</pre></td></tr><tr><td><pre>1</pre></td></tr></table></td></tr><tr><td><pre>Returns: 2</pre></td></tr><tr><td><table><tr><td colspan="2">There are two Magic Atoms and we need to select exactly one of them. Both selections are valid. It is better to choose atom 1 (0-based index) since it stores more power.</td></tr></table></td></tr></table></td></tr><tr><td align="center" nowrap="true">1)</td><td></td></tr><tr><td>    </td><td><table><tr><td><table><tr><td><pre>{100, 1, 100}</pre></td></tr><tr><td><pre>{"NYN",
"YNY",
"NYN"}</pre></td></tr><tr><td><pre>1</pre></td></tr></table></td></tr><tr><td><pre>Returns: 1</pre></td></tr><tr><td><table><tr><td colspan="2">There is only one valid subset. It consists of atom 1.</td></tr></table></td></tr></table></td></tr><tr><td align="center" nowrap="true">2)</td><td></td></tr><tr><td>    </td><td><table><tr><td><table><tr><td><pre>{100, 1, 100}</pre></td></tr><tr><td><pre>{"NYN",
"YNY",
"NYN"}</pre></td></tr><tr><td><pre>2</pre></td></tr></table></td></tr><tr><td><pre>Returns: 200</pre></td></tr><tr><td><table><tr><td colspan="2">The optimal solution is to choose atoms 0 and 2.</td></tr></table></td></tr></table></td></tr><tr><td align="center" nowrap="true">3)</td><td></td></tr><tr><td>    </td><td><table><tr><td><table><tr><td><pre>{4, 7, 5, 8}</pre></td></tr><tr><td><pre>{"NYNY",
"YNYN",
"NYNY",
"YNYN"}</pre></td></tr><tr><td><pre>2</pre></td></tr></table></td></tr><tr><td><pre>Returns: 15</pre></td></tr><tr><td><table><tr><td colspan="2"></td></tr></table></td></tr></table></td></tr><tr><td align="center" nowrap="true">4)</td><td></td></tr><tr><td>    </td><td><table><tr><td><table><tr><td><pre>{46474, 60848, 98282, 58073, 42670, 50373}</pre></td></tr><tr><td><pre>{"NYNNNY", "YNNYNY", "NNNYYY", "NYYNNN", "NNYNNN", "YYYNNN"}</pre></td></tr><tr><td><pre>3</pre></td></tr></table></td></tr><tr><td><pre>Returns: 209503</pre></td></tr><tr><td><table><tr><td colspan="2"></td></tr></table></td></tr></table></td></tr><tr><td align="center" nowrap="true">5)</td><td></td></tr><tr><td>    </td><td><table><tr><td><table><tr><td><pre>{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}</pre></td></tr><tr><td><pre>{"NNYYYNYYNYNNY", "NNYNYYYYYYYNY", "YYNYYNYYYYYYY", "YNYNYYNYYYYYY",
"YYYYNNYYYYYNY", "NYNYNNYYYYYNN", "YYYNYYNYYYYYY", "YYYYYYYNYNYYY",
"NYYYYYYYNYYYY", "YYYYYYYNYNNNN", "NYYYYYYYYNNYN", "NNYYNNYYYNYNN", "YYYYYNYYYNNNN"}</pre></td></tr><tr><td><pre>9</pre></td></tr></table></td></tr><tr><td><pre>Returns: -1</pre></td></tr><tr><td><table><tr><td colspan="2"></td></tr></table></td></tr></table></td></tr><tr><td align="center" nowrap="true">6)</td><td></td></tr><tr><td>    </td><td><table><tr><td><table><tr><td><pre>{1, 1}</pre></td></tr><tr><td><pre>{"NN", "NN"}</pre></td></tr><tr><td><pre>1</pre></td></tr></table></td></tr><tr><td><pre>Returns: 1</pre></td></tr><tr><td><table><tr><td colspan="2"></td></tr></table></td></tr></table></td></tr><tr><td align="center" nowrap="true">7)</td><td></td></tr><tr><td>    </td><td><table><tr><td><table><tr><td><pre>{1,1,2,5,2,4,2}</pre></td></tr><tr><td><pre>{"NNNNNNN","NNYNNNN","NYNNNYN","NNNNNNY","NNNNNNN","NNYNNNN","NNNYNNN"}</pre></td></tr><tr><td><pre>3</pre></td></tr></table></td></tr><tr><td><pre>Returns: 11</pre></td></tr><tr><td><table><tr><td colspan="2"></td></tr></table></td></tr></table></td></tr></table><p>This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved. </p></body></html>