ICPC SWERC 2017 A - Cakey McCakeFace - Olympiads Online Judge

ICPC SWERC 2017 A - Cakey McCakeFace

View as PDF

Submit solution

All submissions

Best submissions

Points: 5

Time limit: 4.0s

Memory limit: 1G

Problem type

Cakey McCakeFace's signature pastry, the Unknowable Cake, is baked daily in their Paris facility. The make-or-break trick for this cake is the cooking time, which is a very well-kept secret. Eve, the well-known spy, wants to steal this secret, and your job is to help her.

Cakes are cooked in a single huge oven that has exactly one front and one back door. The uncooked cakes are inserted through the front door. After the exact and very secret cooking time has passed, the cakes exit the oven through the back door. Only one cake can go through the front or back door at any given time.

Eve has secretly installed detectors at the front and back of the oven. They record a signal every time a cake passes through the doors. A cake will therefore trigger the entry detector at some time $t$ ~t~ when it goes through the front door, and then trigger the exit detector at time exactly $t + \text{cooking_time}$ ~t + \text{cooking_time}~ when it goes through the back door (all cakes at Cakey McCakeFace are always perfectly cooked).

After a few days, she receives two sets of timestamps (in ms) corresponding to entry and exit detectors. Unfortunately, the detectors are faulty: they are sometimes triggered when no cake has passed, or they may fail to be triggered when a cake passes. Eve noticed that she could make a good guess of the secret $\text{cooking_time}$ ~\text{cooking_time}~ by finding the time difference that maximizes the number of correspondences of entry and exit detection times. Help Eve compute this.

Input Specification

Line $1$ ~1~: the number $N$ ~N~ of times the entry detector was triggered.
Line $2$ ~2~: the number $M$ ~M~ of times the exit detector was triggered.
Line $3$ ~3~: the $N$ ~N~ integer timestamps at which the entry detector was triggered, sorted in ascending order, with no repetition, space-separated.
Line $4$ ~4~: the $M$ ~M~ integer timestamps at which the exit detector was triggered, sorted in ascending order, with no repetition, space-separated.

Constraints

$1 \le N, M \le 2\,000$ ~1 \le N, M \le 2\,000~;
each timestamp is between $0$ ~0~ and $1\,000\,000\,000$ ~1\,000\,000\,000~ (inclusive).

Output Specification

A single integer: your best guess of the secret $\text{cooking_time}$ ~\text{cooking_time}~, the (positive or zero) time difference that maximizes the number of correspondences of entry and exit detection times. If multiple such values exist, the smallest one should be returned.

Sample Input

5
5
0 10 12 20 30
1 5 17 27 50

Sample Output

Comments

2
yeerk16 commented on Aug. 26, 2020, 2:54 p.m.
I'm having trouble justifying why the output for the following test case should be 0:

1 1 4 2

The entry time is after the exit time. Why does 0 maximize the number of correspondences here?

Thank you!

3

chika commented on Aug. 26, 2020, 10:17 p.m.

The problem statement says to return the minimum nonnegative cooking time that maximizes the number of correspondences. All nonnegative cooking times give zero correspondences, so therefore we tiebreak on the minimum nonnegative cooking time, which for this test case is zero.

-3

Lele567 commented on Aug. 26, 2020, 8:31 p.m.

Given that test case, you can't know if the cooking time is 3 or 100. The only data is obviously false, so you have nothing reliable to go on. So the output defaults to 0.