StoryFromTCO | Topcoder Archive

Problem Statement

After the Challenge Phase of TCO 2014 round 2C ended, I realized that I probably wouldn't get into top 50. With the best place I'd ever gotten in an SRM, however, it would've been possible. Aargh, why can't I just swap them... but what about making another problem out of this situation?

BonifÃ¡c is going to compete in a tournament with N online rounds, numbered 0 through N-1 in no particular order. Unlike the TCO, each contestant may compete officially in all online rounds. However, only contestants who finished among the top cutoff[i] participants of round i for all 0 <= i < N are invited to the onsite finals.

BonifÃ¡c wants to compete in the onsite finals. For that, he assessed his skills and determined that if he competed in round i, he'd take the places[i]-th place. This might not be sufficient, but BonifÃ¡c is able to select any subset of elements of places and reorder them in any way (don't think too deeply into how he'd do it). However, such a feat is very difficult, so he wants to perform it on as few elements as possible.

You're given int[]s cutoff and places. Return the smallest non-negative integer K, such that BonifÃ¡c could advance to the onsite finals after reordering (permuting) his results in K online rounds. Formally, for BonifÃ¡c to advance, there have to be K elements of places, such that after rearranging them into a different order, places[i] <= cutoff[i] would hold for all 0 <= i < N. If no such K exists, return -1 instead.

Definition

Class:: StoryFromTCO
Method:: minimumChanges
Parameters:: int[], int[]
Returns:: int
Method signature:: int minimumChanges(int[] places, int[] cutoff)
(be sure your method is public)

Constraints

places and cutoff will contain the same number of elements.
places will contain between 1 and 1,000 elements, inclusive.
All elements of places and cutoff will be between 1 and 1,000,000, inclusive.

Examples

```
{20,100,500,50}
```
```
{7500,2250,150,24}
```
```
Returns: 3
```
Without any changes to places, BonifÃ¡c's current performance in rounds 2 and 3 isn't sufficient (because 500 > 150, 50 > 24). For BonifÃ¡c to advance to the finals, he should permute places to {500,100,50,20}, which requires moving 3 elements.
```
{5,4,3,2,1}
```
```
{5,4,3,2,1}
```
```
Returns: 0
```
BonifÃ¡c's current performance is exactly sufficient.
```
{1,5,5,5}
```
```
{8,6,4,2}
```
```
Returns: -1
```
```
{3,1,5}
```
```
{6,4,2}
```
```
Returns: 3
```
There's exactly 1 correct order; to achieve it, all elements must be permuted.

{14,11,42,9,19}

{11,16,37,41,47}

Returns: 4

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

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

Returns: 6

{213,177,237,444,497,315,294,104,522,635,13,26,22,276,88,249,374,17,42,245,80,553,121,625,62,105,
53,132,178,250,18,210,492,181,2,99,29,21,62,218,188,584,702,63,41,79,28,452,2}

{33,40,41,48,74,84,117,125,126,164,197,197,201,218,222,231,244,277,290,309,321,321,360,376,440,
442,465,477,491,513,639,645,647,675,706,710,726,736,736,765,801,838,845,854,863,865,887,902,908}

Returns: 23

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.