Connection Status:
Competition Arena > PlugStuffIn

PlugStuffIn

2022 TCO Parallel 2A · 2022-04-14 · by misof

2022 TCO Parallel 2A · 2022-04-14 · by misof · Greedy, Simple Math, Simulation, Sorting
Class Name: PlugStuffIn
Return Type: int[]
Method Name: plug
Arg Types: (vector<int>)
Problem Statement

Problem Statement

You have a collection of power cords and devices that use electricity. We will refer to them as "cords" and "devices", and we will use the word "gadgets" to refer to both cables and devices.

Each gadget has exactly one plug.

Devices have no sockets. Cords have one or more sockets. Different cords may have a different number of sockets.

Additionally, there is exactly one socket on the wall: the power outlet.

All plugs have the same shape, all sockets have the same shape, and they all match.


You want to plug all your devices into electricity at the same time. (Plugging in all the cords is optional.)

Determine whether it is possible, and if it is, find one way of doing so.


You are given the int[] gadgets with N elements. This array describes a collection of N gadgets, numbered from 0 to N-1. For each i, gadgets[i] is the number of sockets on gadget number i. (Hence, gadgets with gadgets[i] = 0 are the devices and all other gadgets are the cords.)

If it is possible to plug in all the devices, find one way of doing so and return a int[] that describes it. For each j, element j of the return value should be the number of the gadget into which gadget j is plugged. Use the value -1 for a gadget that remains unplugged, and the value N for a gadget that is plugged into the wall socket.

If there is no solution, return an empty int[] instead.

Constraints

  • gadgets will contain between 0 and 50 elements, inclusive.
  • Each element of gadgets will be between 0 and 50, inclusive.
Examples
0)
{0}
Returns: {1 }

A single device. The only solution is to plug the device into the wall.

1)
{1, 1, 0, 1, 1, 1}
Returns: {-1, -1, 4, -1, 6, -1 }

A single device and five extension cords (each with one socket). Our example return value describes a solution in which we plug cord 4 into the wall and then device 2 into cord 4. Other solutions exist, including the one in which we plug the device straight into the wall and we ignore the cords.

2)
{1, 1, 0, 1, 1, 1, 0}
Returns: { }

Now we have two devices. The extension cords are useless - regardless of whether we use them or not, there is no way to plug both devices at the same time.

3)
{0, 0, 2, 0, 2}
Returns: {2, 4, 5, 4, 2 }

We have to use everything. In our solution, cord 2 goes into the wall and cord 4 into one of the two sockets on cord 2. This leaves three empty sockets that now all have power: the unused one on cord 2 and both sockets on cord 4. Thus, we can plug our three devices in (taking care to plug each of them into its own socket).

4)
{0, 3, 3}
Returns: {3, 2, 1 }

We have a device + two cords, each with three sockets. In our solution we have plugged the device into the wall, cord 1 into one of the sockets on cord 2, and cord 2 into one of the sockets on cord 1. Note that the two cords now don't have power - they are only plugged into each other, but they aren't connected to the electrical network. If we were to plug another device into one of their sockets, that device would not have electricity, and thus such a configuration would NOT be a valid solution.

5)
{10, 20, 30, 40}
Returns: {-1, 1, -1, -1 }

No devices here, so we don't have to do anything. But just for good fun we plugged cable 1 (the one with 20 sockets) into one of its own sockets. (As in the previous example, this cable doesn't have electricity.)

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

Coding Area

Language: C++17 · define a public class PlugStuffIn with a public method vector<int> plug(vector<int> gadgets) · 127 test cases · 2 s / 256 MB per case

Submitting as anonymous