OvercookedDiv2 | Topcoder Archive

Problem Statement

Alice and Bob are playing a popular game called Overcooked. In this game, players work together to cook dishes and serve them to customers. We'll be discussing a simplified version of the game in this problem.

Alice and Bob wish to prepare a single dish. The recipe consists of n steps. The steps must be done sequentially in order from 0 to n-1: step i+1 cannot be started before step i has been completed. (It is allowed to start the next step in the same moment in which they finished working on the previous step.)

Alice and Bob have a stopwatch. At the beginning of the game they start the stopwatch. Each step of the recipe can only be started when the time on the stopwatch is an integer. Additionally, the steps are not necessarily available from the start: the i-th step only becomes available when the stopwatch reaches start[i] seconds. Step i takes time[i] seconds to complete.

Given a particular schedule that describes when to do which step of the recipe, we can measure the waiting times. For each step of the recipe, the waiting time before step i is the idle time between finishing step i-1 and starting step i. (For step 0, the waiting time is the time between starting the stopwatch and starting step 0.) The boredom level of the schedule is the maximum of all waiting times.

You are given the int[]s start and time. Determine and return the smallest possible boredom level of a schedule that describes how to execute the given recipe.

Definition

Class:: OvercookedDiv2
Method:: minStale
Parameters:: int[], int[]
Returns:: int
Method signature:: int minStale(int[] start, int[] time)
(be sure your method is public)

Constraints

start,time will have the same number of elements.
start will have between 1 and 50 elements, inclusive.
Each element of start,time will be between 1 and 10^6, inclusive.
Elements in start will be in increasing order.

Examples

```
{1,5,10}
```
```
{3,6,1}
```
```
Returns: 1
```
The smallest possible boredom level is 1 second. It can be achieved with the following schedule: 0: Wait for 1 second. 1: Step 0 now becomes available. Start doing it. 4: Finish doing step 0. Wait for 1 second. 5: Step 1 now becomes available. Start doing it. 10: Step 2 now becomes available, but we are still doing step 1. 11: Finish doing step 1. Without any waiting start doing step 2. 12: Finish the recipe.
```
{3,10}
```
```
{1,10}
```
```
Returns: 5
```
Here, it is better to wait until time 4 or 5 to start the first step.

{1,10,100,1000,10000,100000}

{50,50,50,50,50,50}

Returns: 16625

{10,30,50,60,70,80,90,100,110,120}

{5,4,3,2,1,5,4,3,2,1}

Returns: 14

```
{1000}
```
```
{1000000}
```
```
Returns: 1000
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.