SRM 817, D2, 500-Pointer (Gym)

James S. Plank

• Problem Statement.
• A main() with the examples compiled in. Use "-" to enter the parameters on standard input.
• A skeleton that compiles with main.cpp.
• tests.sh
• answers.txt

• Problem Given in Topcoder: October, 2021
• Competitors who opened the problem: 92
• Competitors who submitted a solution: 68
• Number of correct solutions: 35
• Accuracy (percentage correct vs those who opened): 38.0
• Average Correct Time: 20 minutes, 36 seconds.

In case topcoder's servers are down

• You are given numbers M, N, T.
• 1 ≤ M ≤ 300,000.
• 1 ≤ N ≤ 300,000.
• 1 ≤ T ≤ 1,000,000.
• You are operating a gym, with M workout machines.
• N people, numbered 0 through N-1 will enter the gym.
• Person i enters the gym at time i, in seconds.
• If a machine is available when person i enters the gym, he/she will work out on it for 0.5 + i²%T seconds.
• If no machine is available when person i enters the gym, he/she will leave and not work out.
• Return how many people work out.

Examples:

#      M      N      T  Answer and comments.
- ------ ------ ------ --------------------------------------------
0     47     10   1000  10: There are more machines than people.
1      1     10   1000   3: People 0, 1 and 3 can workout.
2      1     10      1  10: Everyone only works out for 0.5 seconds.
3      2     10    100  10: People 0, 1, 2, 3 and 7 can workout.
4     15    100     47  82: No comment.

Testing yourself

Hints

Obviously, we iterate on the people, from 0 to N-1. That's O(N).

For each person, we see if there's a machine available. If so, we allocate the machine, and calculate when it will be free again. We also add one to the return value. If there's no machine available, then we move on.

So, how should we "allocate the machine." My recommendation is to use a multiset, keyed on the time when the machine will be free. To avoid floating point, I inserted the time minus 0.5. Then, my loop went as follows:

for (i = 0; i < N; i++) {
  if (the machines multiset has less than N elements) {
    add one to the return value
    add the finishing time (minus 0.5) to the multimap
  } else {
    do nothing
  }
  for all machines that are finished at time i, remove them from the multimep
}