CCC '16 S2 - Tandem Bicycle - Olympiads Online Judge

CCC '16 S2 - Tandem Bicycle

Points: 5 (partial)

Time limit: 2.0s

Memory limit: 256M

Author:

Problem types

Canadian Computing Competition: 2016 Stage 1, Junior #5, Senior #2

Since time immemorial, the citizens of Dmojistan and Pegland have been at war. Now, they have finally signed a truce. They have decided to participate in a tandem bicycle ride to celebrate the truce. There are $N$ ~N~ citizens from each country. They must be assigned to pairs so that each pair contains one person from Dmojistan and one person from Pegland.

Each citizen has a cycling speed. In a pair, the fastest person will always operate the tandem bicycle while the slower person simply enjoys the ride. In other words, if the members of a pair have speeds $a$ ~a~ and $b$ ~b~, then the bike speed of the pair is $\max(a,b)$ ~\max(a,b)~. The total speed is the sum of the $N$ ~N~ individual bike speeds.

For this problem, in each test case, you will be asked to answer one of two questions:

Question 1: what is the minimum total speed, out of all possible assignments into pairs?
Question 2: what is the maximum total speed, out of all possible assignments into pairs?

Input Specification

The first line will contain the type of question you are to solve, which is either $1$ ~1~ or $2$ ~2~.

The second line will contain $N$ ~N~ $(1 \le N \le 100)$ ~(1 \le N \le 100)~.

The third line will contain $N$ ~N~ space-separated integers: the speeds of the citizens of Dmojistan.

The fourth line will contain $N$ ~N~ space-separated integers: the speeds of the citizens of Pegland.

Each person's speed will be an integer between $1$ ~1~ and $1\,000\,000$ ~1\,000\,000~.

For 8 of the 15 available marks, questions of type $1$ ~1~ will be asked. For 7 of the 15 available marks, questions of type $2$ ~2~ will be asked.

Output Specification

Output the maximum or minimum total speed that answers the question asked.

Sample Input 1

Output for Sample Input 1

Explanation for Output for Sample Input 1

There is a unique optimal solution:

Pair the citizen from Dmojistan with speed $5$ ~5~ and the citizen from Pegland with speed $6$ ~6~.
Pair the citizen from Dmojistan with speed $1$ ~1~ and the citizen from Pegland with speed $2$ ~2~.
Pair the citizen from Dmojistan with speed $4$ ~4~ and the citizen from Pegland with speed $4$ ~4~.

Sample Input 2

Output for Sample Input 2

Explanation for Output for Sample Input 2

There are multiple possible optimal solutions. Here is one optimal solution:

Pair the citizen from Dmojistan with speed $5$ ~5~ and the citizen from Pegland with speed $2$ ~2~.
Pair the citizen from Dmojistan with speed $1$ ~1~ and the citizen from Pegland with speed $6$ ~6~.
Pair the citizen from Dmojistan with speed $4$ ~4~ and the citizen from Pegland with speed $4$ ~4~.

Sample Input 3

2
5
202 177 189 589 102
17 78 1 496 540

Output for Sample Input 3

Explanation for Output for Sample Input 3

There are multiple possible optimal solutions. Here is one optimal solution:

Pair the citizen from Dmojistan with speed $202$ ~202~ and the citizen from Pegland with speed $1$ ~1~.
Pair the citizen from Dmojistan with speed $177$ ~177~ and the citizen from Pegland with speed $540$ ~540~.
Pair the citizen from Dmojistan with speed $189$ ~189~ and the citizen from Pegland with speed $17$ ~17~.
Pair the citizen from Dmojistan with speed $589$ ~589~ and the citizen from Pegland with speed $78$ ~78~.
Pair the citizen from Dmojistan with speed $102$ ~102~ and the citizen from Pegland with speed $496$ ~496~.

This sum yields $202+540+189+589+496=2016$ ~202+540+189+589+496=2016~.

Comments

-2

MrBloc01 commented on Dec. 11, 2022, 12:28 a.m.

This whole question is based on the Christmas Truce in WW1 between Pakistan (in this case Dmojistan, dmoj.ca) and England (in this case Pegland, wcipeg.com).

4

Plasmatic commented on Dec. 14, 2022, 5:03 a.m.

Pakistan? Are you sure?

-1

MrBloc01 commented on Dec. 18, 2022, 12:21 a.m.

Pakistan is the only axis power in ww1 that ends in a "istan", if I'm wrong, feel free to correct me

5

gavin_chen commented on Dec. 18, 2022, 1:31 a.m. ← edited →

ww1 or ww2? either way, its false. Pakistan was part of the British Indian colony during those 2 periods.

13

vishnus commented on May 27, 2021, 10:33 p.m.

It's kind of cool that DMOJ and PEG get the recognition they deserve in the actual CCC contest. DMOJ has quite literally changed my life. Without it, I'd never have discovered competitive programming.

19

cyopotatoe commented on Nov. 21, 2020, 4:56 p.m.

DMOJ and PEG casually declaring war

59

kobortor commented on June 10, 2020, 5:47 a.m.

DMOJistan declares victor over PEG!

https://wcipeg.com/announcement/9383

5

glasa commented on Aug. 1, 2020, 11:40 p.m.

HOORAH! Glory to DMOJistan

-5

fishingguy456 commented on Jan. 23, 2020, 7:22 p.m.

Why is the answer for the first test case 12 and not 7? 1 can pair with 6, 5 can pair with 2 and 4 can pair with 4, giving an answer that is even smaller.

This comment is hidden due to too much negative feedback. Show it anyway.

1

injust commented on Jan. 23, 2020, 7:36 p.m.

$6 + 5 + 4 = 15$ ~6 + 5 + 4 = 15~

-6

fishingguy456 commented on Jan. 24, 2020, 3:00 a.m.

No, for the first test case where the sample output is 12.

This comment is hidden due to too much negative feedback. Show it anyway.

6

leonzalion commented on Jan. 24, 2020, 3:37 a.m. ← edit 8 →

if the members of a pair have speeds 𝑎 and 𝑏, then the bike speed of the pair is 𝑚𝑎𝑥(𝑎,𝑏).

As such, when you pair 1 with 6, the pair's bike speed is max(1, 6) = 6. Pairing 5 with 2 gives a bike speed of max(5, 2) = 5 and pairing 4 with 4 gives a bike speed of max(4, 4) = 4. 6 + 5 + 4 = 15

However, there is a more optimal pairing to minimize the total speed by pairing 6 with 5 (giving a bike speed of 6), pairing 2 with 1 (giving a bike speed of 2), and pairing 4 with 4 (giving a bike speed of 4), resulting in 6 + 4 + 2 = 12, matching the sample output.

I may be wrong, but I'm assuming you got 7 from adding min(a, b)s instead: 1 + 2 + 4 = 7

-3

MakanDey commented on Feb. 15, 2019, 2:19 a.m. ← edited →

For sample case one, shouldn't it be 10 instead of 12 if it wants the minimum?

1

GeoHD commented on Feb. 15, 2019, 3:14 a.m.

No, it should be 12. Look at the explanation. When you pair them up, you only take the sum of all the cyclist which cycles the fastest out of the pair.

41

PiMachine commented on Feb. 21, 2016, 3:26 a.m.

"DMOJ"istan and "PEG"land LOL XD

14

yellowsn0w1004 commented on Feb. 20, 2016, 8:46 p.m.

So Tandem Bicycle is problem 5 on the junior exam and is supposed to be the hardest (according to order), but I found that it was significantly easier than problems 3 and 4.

Am I wrong thinking that the problems are in order of difficulty?

Anyone else find this weird?

3

odaniel commented on Feb. 20, 2016, 11:03 p.m. ← edited →

It's a "big-data" question - designed to catch people with ultra-naive solutions. Note that the speeds can be as high as one million - if somebody tried to compare every single combination, it would take forever.