ApplesAndOrangesHard | Topcoder Archive

Problem Statement

Garth likes apples and oranges. Recently he bought N fruits, where each fruit was either an apple or an orange. Then he ate all N fruits in some order. You are given an int K. Garth observed that at every point in time, if he made a list of the last K fruits he ate, there were at most K/2 (rounded down) apples in this list.

For each valid i, you know that the info[i]-th fruit Garth ate was an apple. (Fruits Garth ate are numbered starting from 1. For example, info[i]=1 means that the very first fruit Garth ate was an apple.)

Please find and return the maximum number of apples Garth could have eaten.

Definition

Class:: ApplesAndOrangesHard
Method:: maximumApples
Parameters:: int, int, int[]
Returns:: int
Method signature:: int maximumApples(int N, int K, int[] info)
(be sure your method is public)

Notes

If Garth makes his list at a point in time when he ate fewer than K fruits, his list will have fewer than K fruits but the requirement will still be the same: there have to be at most K/2 apples in the list.

Constraints

N will be between 2 and 1,000,000,000, inclusive.
K will be between 2 and min(100,000, N), inclusive.
info will contain between 0 and 50 elements, inclusive.
Each element of info will be between 1 and N, inclusive.
The elements of info will be distinct.
The elements of info will be consistent with Garth's observation.

Examples

```
3
```
```
2
```
```
{}
```
```
Returns: 2
```
Garth ate N=3 fruites. The requirement is that any K=2 consecutive fruits may contain at most K/2 = 1 apple. As info is empty, you have no additional information about the fruits Garth ate. Garth might have eaten an apple, then an orange, then an apple. This satisfies the conditions: After eating the 1st fruit, the list is [apple]. After eating the 2nd fruit, the list is [apple, orange]. After eating the 3rd fruit, the list is [orange, apple]. Each list contains at most 1 apple.
```
10
```
```
3
```
```
{3, 8}
```
```
Returns: 2
```
All fruits, except for the 3rd and the 8th, must have been oranges.
```
9
```
```
4
```
```
{1, 4}
```
```
Returns: 5
```
```
9
```
```
4
```
```
{2, 4}
```
```
Returns: 4
```

{3, 2, 9, 1, 15, 23, 20, 19}

Returns: 10

1000000000

{2110119, 401933834, 401933833, 10}

Returns: 470588238

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.