ECOO '18 R3 P4 - Circular Cities

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 30.0s
Memory limit: 256M

Problem types

In Ringworld, there are M cities numbered from 1 to M which lie uniformly spaced along a circular, two-way road. It takes one hour to travel between city i and city i+1 for 1\leq i\leq M and one hour to travel between city 1 and city M.

Thre are N students and N teachers living in the cities. You would like to assign every teacher to a distinct student such that the sum of the times needed for each student to travel to their assigned teacher's city is minimized.

What is the minimum sum of the travel times for a teacher-student assignment?

Input Specifications

The standard input will contain 10 datasets. Each dataset begins with two integers N and M (1\leq N\leq 5\times10^5, 1\leq M\leq10^9).

The next line contains N integers A_i\,(1\leq A_i\leq M) such that student i lives in city A_i. The third line contains N integers B_i\,(1\leq B_i\leq M) such that teacher i lives in city B_i. At most one student or teacher lives in each city.

for the first 4 cases, N\leq1000.

Output Specifications

For each dataset, output the minimum sum of the travel times for a teacher-student assignment.

Sample Input (Two Datasets Shown)

2 5
1 4
5 3
5 100
10 20 30 40 50
60 70 80 90 100

Sample Output



  • -2
    daoboyang41  commented on July 29, 2018, 5:25 p.m. edit 3

    no judge, and problem type should be brute force. No kidding. Shouldn't do that...