Connection Status:
Competition Arena > SchedulingWoes

SchedulingWoes

SRM 769 · 2019-10-17 · by misof

SRM 769 · 2019-10-17 · by misof · Greedy, Sorting
Class Name: SchedulingWoes
Return Type: int
Method Name: study
Arg Types: (int, int, vector<int>, int, vector<int>, int)
Problem Statement

Problem Statement

Samko has N exams coming up soon. Today is day 0, and as it is Samko's birthday, today he is not going to study. On each of the upcoming days Samko is willing to spend the whole morning studying. On some of those days he will have exams. Exams are always in the afternoon, and if there are multiple exams on the same day, they do not collide (and thus Samko can attend all of them).

The exams are numbered 0 through N-1. Exam i is on the afternoon of day D[i]. In order to pass the exam, Samko has to spend at least T[i] mornings studying its subject before taking the exam.

Compute and return the maximum number of exams Samko can pass.

Use the following pseudocode to generate the input: 

random[0] = seed
for i = 1 to 2*N-1:
    random[i] = (random[i-1] * 1103515245 + 12345) mod 2^31

for i = 0 to len(Dprefix)-1:
    D[i] = Dprefix[i]
    T[i] = Tprefix[i]

for i = len(Dprefix) to N-1:
    D[i] = 1 + (random[2*i] modulo maxD)
    maxT = max(1, D[i] div factor)
    T[i] = 1 + (random[2*i+1] modulo maxT)

Constraints

  • N will be between 1 and 200,000, inclusive.
  • seed will be between 0 and 2^31 - 1, inclusive.
  • Dprefix will have between 0 and 100 elements, inclusive.
  • Dprefix will have no more than N elements, inclusive.
  • Each element of Dprefix will be between 1 and maxD, inclusive.
  • maxD will be between 1 and 1,000,000,007, inclusive.
  • Tprefix will have the same number of elements as Dprefix.
  • For each i, Tprefix[i] will be between 1 and Dprefix[i], inclusive.
  • factor will be between 1 and 1,000,000,007, inclusive.
Examples
0)
5
0
{20, 30, 50, 40, 50}
474747
{10, 5, 20, 30, 10}
474747
Returns: 4

This input has no pseudorandom part, so seed, maxD and factor don't matter. There are five exams. Samko is not able to pass all five, but he can pass four of them. Here's one possible study plan: Day 1: study for exam 1. Days 2-11: study for exam 0. Days 12-20: study for exam 4. Afternoon of day 20: PASS exam 0 (studied for 10 days). Days 21-24: study for exam 1. Days 25-29: study for exam 4. Day 30: study for exam 3. Afternoon of day 30: PASS exam 1 (studied for 5 days). Days 31-40: study for exam 2. Afternoon of day 40: FAIL exam 3 (only studied for 1 day). Days 41-50: study for exam 2. Afternoon of day 50: PASS exam 2 (studied for 20 days) and PASS exam 4 (studied for 14 days).

1)
7
0
{3,1,4,7,2,5,6}
474747
{1,1,1,1,1,1,1}
424242
Returns: 7

Samko can pass all seven exams by always studying on the same day as taking the exam.

2)
7
0
{7,7,7,7,7,7,7}
123456
{3,1,4,7,2,5,6}
654321
Returns: 3

All exams are on the same day. Samko can pass at most three of them.

3)
30
47
{1000, 2000, 3000}
4700
{900, 347, 152}
5
Returns: 25

D = {1000, 2000, 3000, 2834, 3828, 4538, 1224, 382, 1076, 2814, 2656, 3594, 916, 2950, 44, 1578, 3116, 4350, 2072, 566, 2648, 226, 2000, 930, 436, 3286, 3828, 2062, 3564, 4234} T = {900, 347, 152, 415, 422, 345, 141, 51, 208, 79, 218, 161, 28, 363, 1, 221, 462, 371, 37, 6, 244, 45, 369, 137, 77, 2, 8, 311, 589, 329}

4)
200000
47
{}
1000000007
{}
147
Returns: 15642

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

Coding Area

Language: C++17 · define a public class SchedulingWoes with a public method int study(int N, int seed, vector<int> Dprefix, int maxD, vector<int> Tprefix, int factor) · 131 test cases · 2 s / 256 MB per case

Submitting as anonymous