Partition | Topcoder Archive

Problem Statement

A computer company is seeking to divide the components of a new system across a number of circuit boards. Each circuit board can hold a fixed maximum number of parts; we need to determine which parts are placed on each circuit board, such that we minimize the number of wires that go from one board to another.

For example, we might have a CPU, a bank of memory, and a graphics coprocessor. If the memory bus is 32 bits wide, the graphics bus is 16 bits wide, and we are limited to only two components on a circuit board, we would want to keep the CPU and memory on one board, needing only 16 wires to travel to the graphics coprocessor. If we had instead placed the memory and graphics coprocessor on one board, we would need 48 wires.

Create a class Partition with a method mincut that takes a String[] busses, a int capacity, and a int boards, and returns an int that represents the minimum number of bus wires that span more than one circuit board.

Definition

Class:: Partition
Method:: mincut
Parameters:: String[], int, int
Returns:: int
Method signature:: int mincut(String[] busses, int capacity, int boards)
(be sure your method is public)

Notes

We are optimizing the number of wires that span more than one board; if a 16 bit bus connects components on three different circuit boards, it contributes only 16 to the total bus wire count.

Constraints

busses will contain between 0 and 50 elements inclusive.
Each element of busses will contain between 3 and 50 characters inclusive.
Each element of busses will consist of the integer bus size (between 1 and 128 inclusive, with no leading zeros), a single space (' '), and then the names each component that connects to the bus, each separated by a single space (' ').
The component names listed in each element of busses will be between 1 and 10 characters inclusive.
The component names listed in each element of busses will consist of only upper case letters ('A'-'Z').
There will be at most 10 unique component names.
capacity will be between 1 and 100 inclusive.
boards will be between 1 and 4 inclusive.

Examples

No public sample cases were explicitly marked for this problem in the original data.

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.