Connection Status:
Competition Arena > LoadBalancing

LoadBalancing

SRM 209 · 2004-08-28 · by Wernie

SRM 209 · 2004-08-28 · by Wernie · Dynamic Programming
Class Name: LoadBalancing
Return Type: int
Method Name: minTime
Arg Types: (vector<int>)
Problem Statement

Problem Statement

The scientific program ITES runs on a computer with two CPUs. The input data for ITES consists of chunks of different sizes, and each chunk has to be processed in whole by either of the CPUs. The chunks may also be processed in any order. Both CPUs run at the same speed and require 1 second of time to process any 1 kilobyte of data.

You are given a int[] chunkSizes containing the sizes of the different input chunks in kilobytes. Due to the method by which the input data is gathered, all sizes are multiples of 1024. Return the fastest time in seconds in which all the input can be processed.

Notes

  • Reminder: Your method may use at most 64 megabytes of memory.

Constraints

  • chunkSizes contains between 0 and 50 elements, inclusive.
  • Each element of chunkSizes is between 1024 and 4194304, inclusive.
  • Each element of chunkSizes is a multiple of 1024.
Examples
0)
{3072, 3072, 7168, 3072, 1024}
Returns: 9216

One CPU gets assigned the chunks of size 7168 and 1024 and requires 8192 seconds to process them, the other CPU gets assigned the three chunks of size 3072 and requires 9216 seconds to process them.

1)
{2048}
Returns: 2048
2)
{2048, 1024, 1024, 2048}
Returns: 3072
3)
{4194304, 4194304, 4194304, 4194304, 4194304,
 4194304, 4194304, 4194304, 4194304, 4194304,
 4194304, 4194304, 4194304, 4194304, 4194304,
 4194304, 4194304, 4194304, 4194304, 4194304,
 4194304, 4194304, 4194304, 4194304, 4194304,
 4194304, 4194304, 4194304, 4194304, 4194304,
 4194304, 4194304, 4194304, 4194304, 4194304,
 4194304, 4194304, 4194304, 4194304, 4194304,
 4194304, 4194304, 4194304, 4194304, 4194304,
 4194304, 4194304, 4194304, 4194304, 4194304}
Returns: 104857600
4)
{}
Returns: 0

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

Coding Area

Language: C++17 · define a public class LoadBalancing with a public method int minTime(vector<int> chunkSizes) · 53 test cases · 2 s / 256 MB per case

Submitting as anonymous