Connection Status:
Competition Arena > ApplesAndOrangesHard

ApplesAndOrangesHard

SRM 659 · 2015-05-01 · by zxqfl

SRM 659 · 2015-05-01 · by zxqfl · Greedy
Class Name: ApplesAndOrangesHard
Return Type: int
Method Name: maximumApples
Arg Types: (int, int, vector<int>)
Problem Statement

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.

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
0)
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.

1)
10
3
{3, 8}
Returns: 2

All fruits, except for the 3rd and the 8th, must have been oranges.

2)
9
4
{1, 4}
Returns: 5
3)
9
4
{2, 4}
Returns: 4
4)
23
7
{3, 2, 9, 1, 15, 23, 20, 19}
Returns: 10

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

Coding Area

Language: C++17 · define a public class ApplesAndOrangesHard with a public method int maximumApples(int N, int K, vector<int> info) · 130 test cases · 2 s / 256 MB per case

Submitting as anonymous