Connection Status:
Competition Arena > CollectTrash

CollectTrash

SRM 853 · 2024-02-21 · by misof

SRM 853 · 2024-02-21 · by misof · Greedy, Search
Class Name: CollectTrash
Return Type: int
Method Name: optimize
Arg Types: (int, int, int, int, vector<int>, int)
Problem Statement

Problem Statement

Streetparade just finished. It took place along a single long straight road. The road is now full of trash that needs to be picked up.

There are P people on our cleaning crew. Currently, they are all located at the beginning of the road: coordinate 0.

There are T pieces of trash to pick up. Piece i is located at the non-negative integer coordinate L[i].

In each second, each member of the cleanup crew can either take a step along the road (increase their coordinate by 1) or pick up a single piece of trash that is located at their current coordinate.

(If there are multiple pieces of trash at the same coordinate, each needs to be picked up separately.)

Calculate and return the minimum time in seconds needed to clean the whole road.


In order to keep the input small, the array L with the trash locations is pseudorandom. Please use the pseudocode below to generate it. 


state = seed
PL = length(Lprefix)

for i = 0 to PL-1:
    L[i] = Lprefix[i]

for i = PL to T-1:
    if C == 1 and i > 0:
        state = (state * 1103515245 + 12345) modulo 2^31
        old = L[state modulo i]
        state = (state * 1103515245 + 12345) modulo 2^31
        spread = (state modulo 21) - 10
        L[i] = max(0, min(M-1, old+spread))       
    else:
        state = (state * 1103515245 + 12345) modulo 2^31
        L[i] = (state modulo M)

Notes

  • The reference solution does not depend on the input being pseudorandom. It would correctly solve any input of the maximum allowed size.
  • Inputs with C = 0 have trash that is distributed roughly uniformly, inputs with C = 1 will generally have trash clusters.

Constraints

  • P will be between 1 and 100,000, inclusive.
  • T will be between 1 and 100,000, inclusive.
  • M will be between 1 and 10^9, inclusive.
  • C will be either 0 or 1.
  • Lprefix will have between 0 and min(T, 300) elements, inclusive.
  • Each element of Lprefix will be between 0 and M-1, inclusive.
  • seed will be between 0 and 2^31 - 1, inclusive.
Examples
0)
1
4
1000000000
0
{7, 4, 10, 4}
1000000000
Returns: 14

All trash locations are given: L = {7, 4, 10, 4}. A single-person cleanup crew has to simply walk along the road and pick up all trash as they find it. For this input they will spend a total of 10 seconds walking and another 4 seconds picking up the trash.

1)
47
47003
1
0
{}
47
Returns: 1001

There are 47003 pieces of trash at coordinate 0. Our cleanup crew can pick them up at 47 pieces per second.

2)
2
5
100000
0
{1, 2, 3, 4, 5}
42
Returns: 7
3)
3
12
7654321
0
{1000, 2000, 3000}
1234567
Returns: 5937965

The array L generated by the pseudocode should look as follows: L = {1000, 2000, 3000, 5937964, 3269905, 5758721, 3464886, 1703385, 3468591, 3011979, 5757124, 2724395}. Watch out for integer overflow when generating it.

4)
3
12
7654321
1
{1000, 2000, 3000}
1234567
Returns: 3015

Here the array L looks as follows: L = {1000, 2000, 3000, 1999, 2992, 2986, 995, 2986, 3010, 3014, 989, 3002}

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

Coding Area

Language: C++17 · define a public class CollectTrash with a public method int optimize(int P, int T, int M, int C, vector<int> Lprefix, int seed) · 205 test cases · 2 s / 256 MB per case

Submitting as anonymous