Connection Status:
Competition Arena > StoryFromTCO

StoryFromTCO

SRM 635 · 2014-08-25 · by Xellos0

SRM 635 · 2014-08-25 · by Xellos0 · Greedy
Class Name: StoryFromTCO
Return Type: int
Method Name: minimumChanges
Arg Types: (vector<int>, vector<int>)
Problem Statement

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.

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

1)
{5,4,3,2,1}
{5,4,3,2,1}
Returns: 0

Bonifác's current performance is exactly sufficient.

2)
{1,5,5,5}
{8,6,4,2}
Returns: -1
3)
{3,1,5}
{6,4,2}
Returns: 3

There's exactly 1 correct order; to achieve it, all elements must be permuted.

4)
{14,11,42,9,19}
{11,16,37,41,47}
Returns: 4

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

Coding Area

Language: C++17 · define a public class StoryFromTCO with a public method int minimumChanges(vector<int> places, vector<int> cutoff) · 110 test cases · 2 s / 256 MB per case

Submitting as anonymous