Woburn Challenge 2016-17 Round 2 - Senior Division

Problem 2: Away Mission

During its travels, the Starship Enterprise has come across a rather curious planet which appears to be contain vast deposits of kironide, a rare and valuable mineral. Captain Kerk has ordered N (1 ≤ N ≤ 200,000) of his crewmembers to go on an away mission to the planet's surface in order to confirm the sensors' readings. If all goes well, they'll be able to locate the kironide and collect some samples… before anything on the planet collects them as samples.

Each of the N crewmembers will need to be outfitted with a shirt, of course. It's standard Starfleet procedure for shirts to be manufactured on demand, with the use of a shirt replicator. The replicator is fed three Colour Component Chips (CCCs) – a red, green, and blue one – which determine the colour of the resulting shirt. Each CCC, in addition to corresponding to a particular colour component (either red, green, or blue), is encoded with an integral value between 0 and 255, inclusive. Kerk has N red CCCs with values R_1..N at his disposal. He similarly has N green CCCs with values G_1..N, and N blue CCCs with values B_1..N.

Kerk may feed the CCCs into the shirt replicator in any combinations he'd like to in order to create N shirts, as long as the replicator is always given CCCs corresponding to all three different colour components at a time, and each of the 3N CCCs is only used once.

A shirt is considered "red" if its red CCC's value is strictly larger than its other two CCCs' values. In other words, if a shirt was produced using red, green, and blue CCCs with values r, g, and b, then it's red if both r > g and r > b.

Unfortunate accidents have a way of happening to crewmembers wearing red shirts, so producing as few red shirts as possible would be beneficial. However, a strange anomaly has recently struck the Enterprise, which may be having unusual psychological effects on its crew, based on the value of Q (1 ≤ Q ≤ 2). If Q = 1, then Kerk has remained resilient and is determined to arrange his CCCs such that as few as possible of the N shirts are red. Otherwise, if Q = 2, then Kerk's psychological state has been compromised, and he'll instead maximize the number of red shirts produced!

In either case, please help estimate the number of "accidents" which might occur on the away mission by determining how many of the crewmembers will end up wearing red shirts.

In test cases worth 4/20 of the points, N ≤ 2000 and B_i = 0 for i = 1..N (and in exactly 50% of these, Q = 1).
In test cases worth another 8/20 of the points, N ≤ 2000 (and in exactly 50% of these, Q = 1).
In exactly 50% of the remaining test cases, Q = 1.

Input Format

The first line of input consists of two space-separated integers N and Q.
The next line consists of N space-separated integers R_1..N.
The next line consists of N space-separated integers G_1..N.
The next line consists of N space-separated integers B_1..N.

Output Format

Output a single integer – either the minimum possible number of red shirts that must be made if Q = 1, or the maximum possible number that can be made if Q = 2.

Sample Input 1

3 1
200 0 123
0 42 122
5 200 99

Sample Output 1

1

Explanation 1

One optimal set of shirts is as follows (with each one notated as (r, g, b)):

(200, 0, 200)
(0, 42, 99)
(123, 122, 5)

Of these, only the last one is red. Unfortunately, it's impossible for none of the shirts to be red.

Sample Input 2

3 2
200 0 123
0 42 122
5 200 99

Sample Output 2

2

Explanation 2

One optimal set of shirts is as follows:

(200, 0, 99)
(0, 42, 200)
(123, 122, 5)

All Submissions
Best Solutions

Point Value: 12 (partial)
Time Limit: 3.00s
Memory Limit: 64M
Added: Dec 11, 2016
Author: SourSpinach

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)