Connection Status:
Competition Arena > SharksDinner

SharksDinner

SRM 358 · 2007-07-17 · by icanadi

SRM 358 · 2007-07-17 · by icanadi · Graph Theory
Class Name: SharksDinner
Return Type: int
Method Name: minSurvivors
Arg Types: (vector<int>, vector<int>, vector<int>)
Problem Statement

Problem Statement

Some sharks are having dinner and they are eating each other. For every shark we know its size, speed and intelligence (measured in positive integers). Shark A can eat shark B if and only if A's size, speed and intelligence are all greater than or equal to B's. Due to digestive restrictions, each shark can eat at most two other sharks.

Given int[] size, int[] speed and int[] intelligence, return the minimum number of sharks that will survive.

Constraints

  • size, speed and intelligence will contain the same number of elements.
  • size, speed and intelligence will each contain between 1 and 50 elements, inclusive.
  • Each element of size, speed and intelligence will be between 1 and 2,000,000,000, inclusive.

Statement by TopCoder, Inc. — view the original on the archive.

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

Shark 1 eats sharks 0 and 2 so we get 1 survivor.

1)
{ 4, 10, 5, 8, 8 }
{ 5, 10, 7, 7, 10 }
{ 5, 8, 10, 7, 3 }
Returns: 2

Shark 2 eats shark 0, and shark 1 eats sharks 3 and 4.

2)
{ 1, 2, 3, 4, 100 }
{ 4, 3, 2, 1, 100 }
{ 2, 4, 1, 3, 100 }
Returns: 3

The big shark eats two of the smaller sharks and is not hungry anymore, so the other two of the smaller sharks are lucky (and they cannot eat each other).

3)
{ 4, 4, 4, 4 }
{ 3, 3, 3, 3 }
{ 8, 8, 8, 8 }
Returns: 1

Sharks with the same level of speed, size and intelligence can eat each other.

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

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

Coding Area

Language: C++17 · define a public class SharksDinner with a public method int minSurvivors(vector<int> size, vector<int> speed, vector<int> intelligence) · 72 test cases · 2 s / 256 MB per case

Submitting as anonymous