Connection Status:
Competition Arena > TwoMonthScheduling

TwoMonthScheduling

SRM 771 · 2019-11-26 · by misof

SRM 771 · 2019-11-26 · by misof · Dynamic Programming
Class Name: TwoMonthScheduling
Return Type: int
Method Name: minimumMonths
Arg Types: (int, vector<int>, vector<int>, vector<int>, vector<int>)
Problem Statement

Problem Statement

There is a sequence of pending jobs. Each job depends on all previous jobs. If job B depends on job A, job B cannot be started before job A (but they can be started at the same time).

The total number of workers you have available is workers. Each job takes two months to complete, and must be completed in two consecutive months. Job i demands firstMonth[i] workers during the first month and secondMonth[i] workers during the second month.

Compute and return the smallest number of months in which all jobs can be completed.

Use the pseudocode below to generate firstMonth[] and secondMonth[]: 

L0, L1 = length(firstMonth0), length(firstMonth1)
for i1 in 0 .. L1-1:
    for i0 in 0 .. L0-1:
        firstMonth [ i1 * L0 + i0 ] = min( workers,  firstMonth0[i0] xor  firstMonth1[i1] )
        secondMonth[ i1 * L0 + i0 ] = min( workers, secondMonth0[i0] xor secondMonth1[i1] )

Notes

  • The reference solution does not depend on the input format, it would correctly solve any input of the size allowed by the constraints.
  • The elements of the arrays firstMonth and secondMonth do not exceed the number of workers you have. Thus, a solution always exists.

Constraints

  • workers will be between 1 and 10^9, inclusive.
  • firstMonth0 will have between 1 and 500 elements, inclusive.
  • firstMonth1 will have between 1 and 10 elements, inclusive.
  • secondMonth0 will have the same number of elements as firstMonth0.
  • secondMonth1 will have the same number of elements as firstMonth1.
  • Each element of the four arrays will be between 0 and 10^9, inclusive.
Examples
0)
1000
{900, 150, 300, 200}
{0}
{400, 300, 600, 150}
{0}
Returns: 4

The arrays firstMonth0 and secondMonth0 are identical to the generated arrays firstMonth and secondMonth. An optimal solution looks as follows: month 1: first month of job 0 (900 workers needed) month 2: second month of job 0, first month of job 1 (400 + 150 workers needed) month 3: second month of job 1, first month of jobs 2 and 3 (300 + 300 + 200 workers needed) month 4: second month of jobs 2 and 3 (600 + 50 workers needed)

1)
1000
{900, 150, 300, 200}
{0}
{400, 600, 300, 150}
{0}
Returns: 5

The input looks similar to Example 0, but job 1 now requires more and job 2 requires fewer workers during their second months. Even though the sum of times is still the same, it is no longer possible to do everything in four months.

2)
1000
{350, 172, 24}
{998, 54}
{513, 119, 0}
{24, 118}
Returns: 7

The arrays you are supposed to generate: firstMonth = {696, 842, 1000, 360, 154, 46} secondMonth = {537, 111, 24, 631, 1, 118}

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

A lot of jobs, but most of them require no workers at all. All these jobs can be done at the same time.

4)
1000
{900, 150, 300, 200}
{0}
{400, 600, 300, 50}
{0}
Returns: 4

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

Coding Area

Language: C++17 · define a public class TwoMonthScheduling with a public method int minimumMonths(int workers, vector<int> firstMonth0, vector<int> firstMonth1, vector<int> secondMonth0, vector<int> secondMonth1) · 143 test cases · 2 s / 256 MB per case

Submitting as anonymous