CircuitsConstruction | Topcoder Archive

Problem Statement

Janusz is a young physicist. He is currently playing with some electric circuits.

The simplest circuit consists of a single conductor (i.e., a single piece of wire). Each such circuit is labeled using the string "X".

Janusz is using two different ways to connect two simpler circuits into one new, more complex circuit. Note that these are not the standard two ways (connecting in series and in parallel), so read the following description carefully.

If Janusz uses the type-A connection, the resistance of the new circuit is the sum of the resistances of the two original circuits.
If Janusz uses the type-B connection, the resistance of the new circuit is the maximum of the resistances of the two original circuits.

Suppose that the two original circuits had labels C1 and C2. Then we use the label "A"+C1+C2 for a new circuit constructed from them using the type-A connection, and the label "B"+C1+C2 if type-B connection was used. For example, "AXX" is the label of the circuit obtained by using a type-A connection on two conductors.

You are given a String circuit with a valid label of a circuit. You are also given a int[] conductors with as many elements as the number of occurrences of 'X' in circuit. The elements of conductors are the resistances of all conductors you are going to use to construct the circuit described by circuit. Each of the conductors can only be used once. Each of the conductors can be used as each of the 'X's. Return the largest possible resistance of the constructed circuit.

Definition

Class:: CircuitsConstruction
Method:: maximizeResistance
Parameters:: String, int[]
Returns:: int
Method signature:: int maximizeResistance(String circuit, int[] conductors)
(be sure your method is public)

Notes

There is no explicit constraint on the length of circuit. This is intentional, as it can be derived from the other constraints.

Constraints

Each character in circuit will be 'A', 'B', or 'X'.
circuit will be a valid circuit label according to the problem statement.
conductors will contain between 1 and 2,000 elements, inclusive.
Each element of conductors will be between 1 and 100,000, inclusive.
The number of occurrences of the character 'X' in circuit will be equal to the number of elements of conductors.

Examples

```
"BXBXX"
```
```
{8, 2, 3}
```
```
Returns: 8
```
Regardless of the order in which we use the conductors, the final resistance will be the maximum of the resistances of our three conductors.
```
"AAXXAXAXX"
```
```
{1, 1, 2, 8, 10}
```
```
Returns: 22
```
Regardless of the order in which we use the conductors, the final resistance will be the sum of the resistances of our five conductors.
```
"AXBXX"
```
```
{8, 2, 3}
```
```
Returns: 11
```
One possible optimal solution looks as follows: We take the conductors with resistance 2 and 3, and use a type-B connection to combine them into a new circuit. We take the remaining conductor (with resistance 8) and the new circuit constructed in the previous step. We use a type-A connection to combine them into the resulting circuit. The resistance of the circuit constructed in the first step is max(2,3) = 3. The resistance of the whole circuit is 8 + 3 = 11, which is the largest value we can obtain.

"BAAXBXXBXAXXBBAXXBXXAAXXX"

{17, 7, 21, 102, 56, 72, 88, 15, 9, 192, 16, 8, 30}

Returns: 454

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)2024, Topcoder, Inc. All rights reserved.