Connection Status:
Competition Arena > MagicMoleculeEasy

MagicMoleculeEasy

SRM 571 · 2012-12-13 · by cgy4ever

SRM 571 · 2012-12-13 · by cgy4ever · Search
Class Name: MagicMoleculeEasy
Return Type: int
Method Name: maxMagicPower
Arg Types: (vector<int>, vector<string>, int)
Problem Statement

Problem Statement

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.

Ciel now has a Magic Molecule formed by n Magic Atoms. The atoms are numbered 0 through n-1, inclusive. You are given a int[] magicPower with n elements: For each i, the amount of power stored in the Magic Atom number i is magicPower[i]. You are also given a String[] magicBond with n elements, each containing n characters. Character j of element i of magicBond is 'Y' if the Magic Atoms i and j are connected by a Magic Bond. Otherwise, character j of element i of magicBond is 'N'.

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:
  1. You are given a int k. The subset S must contain exactly k atoms.
  2. 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.
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.

Constraints

  • k will be between 1 and min(n, 14), inclusive, where n is the number of elements in magicPower.
  • magicPower will contain between 2 and 50 elements, inclusive.
  • Each element in magicPower will be between 1 and 100,000, inclusive.
  • magicBond and magicPower will contain the same number of elements.
  • Each element of magicBond will contain exactly n characters, where n is the number of elements in magicPower.
  • Each element of magicBond will only contain the characters 'Y' and 'N'.
  • For each valid i, magicBond[i][i] will be 'N'.
  • For each valid i and j, magicBond[i][j] will be equal to magicBond[j][i].
Examples
0)
{1, 2}
{"NY",
 "YN"}
1
Returns: 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.

1)
{100, 1, 100}
{"NYN",
 "YNY",
 "NYN"}
1
Returns: 1

There is only one valid subset. It consists of atom 1.

2)
{100, 1, 100}
{"NYN",
 "YNY",
 "NYN"}
2
Returns: 200

The optimal solution is to choose atoms 0 and 2.

3)
{4, 7, 5, 8}
{"NYNY",
 "YNYN",
 "NYNY",
 "YNYN"}
2
Returns: 15
4)
{46474, 60848, 98282, 58073, 42670, 50373}
{"NYNNNY", "YNNYNY", "NNNYYY", "NYYNNN", "NNYNNN", "YYYNNN"}
3
Returns: 209503

Submissions are judged against all 153 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class MagicMoleculeEasy with a public method int maxMagicPower(vector<int> magicPower, vector<string> magicBond, int k) · 153 test cases · 2 s / 256 MB per case

Submitting as anonymous