This is my first post on this forum, so I’m sad that I can’t provide a link to the problem because this problem was prepared for an offline round in the city I live in, Ha Noi, Viet Nam, but I’ll provide the following translation from Vietnamese :
A company have N shippers and they need to deliver T packages to their customers (there are also T customers, each want to receive one package. It doesn’t matters which package they receive, so you can consider all packages the same). When trying to ship on order, 1 shipper will have to do the following procedure : he first go to either one of the company’s 2 storehouses between their company and the group of customer, receive the package, and then ship it to one customer. We are given the distances between our N shippers and the 2 storehouses, and also the distances between these 2 storehouses and T customers. Find a way to arranges our shippers so that the total distances our shippers have to go is the smallest.
INPUT:
-
The first line contains N and T (1 <= T <= N <= 10^5), the number of our shippers and customers respectively.
-
The second line consists of N integers a1[i] (1 <= i <= N) indicates the distance from the i-th shipper to the first storehouse.
-
The third line consists of N integers a2[i] (1 <= i <= N) indicates the distance from the i-th shipper to the second storehouse.
-
The fourth line consists of T integers b1[j] (1 <= j <= T) indicates the distance from the first storehouse to the j-th customer.
-
The fifth line consists of T integers b2[j] (1 <= j <= T) indicates the distance from the second storehouse to the j-th customer.
OUTPUT:
Print the total smallest distance that our employees will have to move if we arranges them optimally.
A note : you can’t use the same shipper twice, and each customer must receive exactly one package, no more, no less. Also, you can safely assume that each storehouse has an infinity amount of package, so it doesn’t matter how many shipper come to one storehouse.
The following picture will show you how this problem work graphically :
I’ll also write the input manually so you can copy it right away if you want.
Input:
3 2
1 2 2
7 5 3
3 5
2 3
Output:
10
I did participate in this offline round, just a few days ago. The first 4 problem was easy, but the fifth (this problem) was abnormally hard that no one managed to solve it onsite. What I didn’t expect is even my teacher can’t solve this too, so I will have to ask you guys. Please save me from my suffering, and finally, Happy New Year to you guys.
Edit : I know that there maybe some grammar mistakes, etc … But please forgive me, english is not my first language 
Edit2: Notice that I’ve changed the input part from “The fourth line … (1 <= j <= N)” to “The fourth line … (1 <= j <= T)” as there are only T customers, and same goes for the fifth line. I’m sorry for the mistakes. Is there more info that you guys would like to be provided ? like clarification of something ?