Building A New Barn [Jeffrey Wang, 2007]

After scrimping and saving for years, Farmer John has decided to build a new barn. He wants the barn to be highly accessible, and he knows the coordinates of the grazing spots of all N (2 <= N <= 10,000) cows. Each grazing spot is at a point with integer coordinates (X_i, Y_i) (-10,000 <= X_i <= 10,000; -10,000 <= Y_i <= 10,000). The hungry cows never graze in spots that are horizontally or vertically adjacent. The barn must be placed at integer coordinates and cannot be on any cow's grazing spot. The inconvenience of the barn for any cow is given the Manhattan distance formula |X-X_i|+|Y-Y_i|, where (X, Y) and (X_i, Y_i) are the coordinates of the barn and the cow's grazing spot, respectively. Where should the barn be constructed in order to minimize the sum of its inconvenience for all the cows? PROBLEM NAME: newbarn INPUT FORMAT: * Line 1: A single integer: N * Lines 2..N+1: Line i+1 contains two space-separated integers which are the grazing location (X_i, Y_i) of cow i SAMPLE INPUT (file newbarn.in): 4 1 -3 0 1 -2 1 1 -1 INPUT DETAILS: The field contains 4 cows with grazing spots at the points (1, -3), (0, 1), (-2, 1), and (1, -1). OUTPUT FORMAT: * Line 1: Two space-separated integers: the minimum inconvenience for the barn and the number of spots on which Farmer John can build the barn to achieve this minimum. SAMPLE OUTPUT (file newbarn.out): 10 4 OUTPUT DETAILS: The minimum inconvenience is 10, and there are 4 spots that Farmer John can build the farm to achieve this: (0, -1), (0, 0), (1, 0), and (1, 1).

ახალი ბეღელი – ირაკლი მარგელაშვილის თარგმანი

სიღარიბეში გატარებული წლების შემდეგ ფერმერმა ჯონმა გადაწყვიტა აეშენებინა ახალი ბეღელი. მას სურს, რომ ბეღელი მაქსიმალურად ხელმისაწვდომი იყოს და მან იცის საძოვრის კოორდინატები N(2 <= N <= 10,000) ძროხისთვის. ყველა საძოვრის კოორდინატი მთელი რიცხვია (X_i, Y_i) (-10,000 <= X_i , Y_i<= 10,000). მშიერი ძროხები არასოდეს ძოვენ ისეთ საძოვრებზე, რომლებიც ერთმანეთის მეზობლად მდებარეობენ(ჰორიზონტალურად, ან ვერტიკალურად). ბეღელი უნდა მდებარეობდეს მთელ კოორდინატებზე და არ უნდა ემთხვეოდეს რომელიმე საძოვარს. თითოეული ძროხის დაბრკოლების კოეფიციენტი მოცემულია ფორმულით |X-X_i|+|Y-Y_i|,სადაც (X,Y)ბეღელის კოორდინატებია და (X_i, Y_i) კი ამ ძროხის საძოვრის. სად უნდა ავაშენოთ ბეღელი, რომ ძროხების დაბრკოლების კოეფიციენტების ჯამი იყოს მინიმალური? ამოცანის სახელი: newbarn შესატანი ფაილის ფორმატი: *ხაზი 1: მთელი რიცხვი: N *ხაზები 2..N+1: ხაზი i+1 შეიცავს ორ ჰარით გამოყოფილ მთელ რიცხვს, საძოვრების კოორდინატებს (X_i, Y_i)i_ური ძროხისთვის. შესატანი ფაილის მაგალითი: 4 1 -3 0 1 -2 1 1 -1 შესატანი ფაილის მაგალითის დეტალები: მდელო მოიცავს 4 ძროხას თავისი საძოვრებით (1, -3), (0, 1), (-2, 1), (1, -1) წერტილებზე. გამოსატანი ფაილის ფორმატი: *ხაზი 1: ორი ჰარით გამოყოფილი მთელი რიცხვი: მინიმალური დაბრკოლება და წერტილების რაოდენობა , რომლებზეც შეუძლია ფერმერ ჯონს ააშენოს ბეღელი რომ მიიღოს მინიმალური დაბრკოლება. გამოსატანი ფაილის მაგალითი: 10 4 გამოსატანი ფაილის მაგალითის დეტალები: მინიმალური დაბრკოლება არის 10 და არსებობს 4 წერტილი რომლებზედაც ბეღელის აშენების შემდეგ მივიღებთ მინიმუმს: (0, -1), (0, 0), (1, 0) და (1, 1).

newbarn

Consider just a single dimension, say X. If there are more cows to the right of the barn than the left, then moving the barn to the right will decrease the total inconvenience, and similarly if there are more cows to the left than the right. It should immediately be clear that the optimal location is on the median (for N odd) or anywhere between the two medians (for N even). In two dimensions, nothing really changes, because the inconvenience is just the sum of the X and Y inconveniences. We do, however, have to consider the case where only one possible square site exists and it is occupied by a cow. In this case, the four adjacent squares become candidates, and we simply need to find the best of them and count the number of ties. Below is Bruce's solution. #include <fstream> #include <algorithm> #include <utility> #include <cstdlib> using namespace std; static pair<int, int> medians(const int *Z, int N) { int s[N]; copy(Z, Z + N, s); nth_element(s, s + N / 2, s + N); if (N & 1) return make_pair(s[N / 2], s[N / 2]); else return make_pair(*max_element(s, s + N / 2), s[N / 2]); } static int cost_of(int x, int y, int *X, int *Y, int N) { int cost = 0; for (int i = 0; i < N; i++) cost += abs(X[i] - x) + abs(Y[i] - y); return cost; } int main() { int N; pair<int, int> xlh, ylh; int opts; int cost; ifstream in("newbarn.in"); ofstream out("newbarn.out"); in >> N; int X[N], Y[N]; for (int i = 0; i < N; i++) in >> X[i] >> Y[i]; xlh = medians(X, N); ylh = medians(Y, N); opts = (xlh.second - xlh.first + 1) * (ylh.second - ylh.first + 1); for (int i = 0; i < N; i++) { if (X[i] >= xlh.first && X[i] <= xlh.second && Y[i] >= ylh.first && Y[i] <= ylh.second) opts--; } cost = cost_of(xlh.first, ylh.first, X, Y, N); if (opts == 0) { const int dr[4] = {-1, 0, 1, 0}; const int dc[4] = {0, -1, 0, 1}; int costs[4]; for (int d = 0; d < 4; d++) costs[d] = cost_of(xlh.first + dr[d], ylh.first + dc[d], X, Y, N); cost = *min_element(costs, costs + 4); opts = count(costs, costs + 4, cost); } out << cost << " " << opts << "\n"; return 0; }

ირაკლი მარგველაშვილის თარგმანი

ჩავთვალოთ , რომ ერთ განზომილებაში ვართ ანუ გვაქვს მხოლოდ X კოორდინატი. თუ ბეღელის მარჯვენა მხარეს არის უფრო მეტი ძროხა ვიდრე მარცხენა მხარეს, მაშინ ბეღელის მარჯვნივ გადანაცვლებით შევამცირებთ საერთო დაბრკოლებას. ანალოგიურად თუ მარცხნივ უფრო მეტი ძროხაა ვიდრე მარჯვნივ. აქედან გამომდინარე ცხადია, რომ ბეღელის ოპტიმალური მდებარეობა არის შუა წერტილი (თუ N კენტია) და ნებისმიერ წერტილზე ორ შუა წერტილს შორის (თუ N ლუწია). ორ განზომილებაში არაფერი არ იცვლება, რადგან დაბრკოლება ძროხებისათვის არის X_ისა და Y_ის დაბრკოლებების ჯამი. გასათვალისწინებელია ის შემთხვევა როდესაც არსებობს მხოლოდ ერთი შესაძლო კვადრატული ნაკვეთი და ის დაკავებული აქვს ძროხის საძოვარს. ამ შემთხვევაში 4 მეზობელი კვადრატიდან ერთ-ერთია ოპტიმალური და ჩვენ უბრალოდ ვიპოვით საუკეთესოს ამ 4_ს შორის და დავთვლით დამთხვევების რაოდენობას. ქვემოთ მოცემულია ბრიუსის ამოხსნა: #include <fstream> #include <algorithm> #include <utility> #include <cstdlib> using namespace std; static pair<int, int>medians(constint *Z, int N) { int s[N]; copy(Z, Z + N, s); nth_element(s, s + N / 2, s + N); if (N & 1) return make_pair(s[N / 2], s[N / 2]); else return make_pair(*max_element(s, s + N / 2), s[N / 2]); } static intcost_of(int x, int y, int *X, int *Y, int N) { int cost = 0; for (inti = 0; i< N; i++) cost += abs(X[i] - x) + abs(Y[i] - y); return cost; } intmain() { int N; pair<int, int>xlh, ylh; int opts; int cost; ifstream in("newbarn.in"); ofstream out("newbarn.out"); in >> N; int X[N], Y[N]; for (inti = 0; i< N; i++) in >> X[i] >> Y[i]; xlh = medians(X, N); ylh = medians(Y, N); opts = (xlh.second - xlh.first + 1) * (ylh.second - ylh.first + 1); for (inti = 0; i< N; i++) { if (X[i] >= xlh.first&& X[i] <= xlh.second&& Y[i] >= ylh.first&& Y[i] <= ylh.second) opts--; } cost = cost_of(xlh.first, ylh.first, X, Y, N); if (opts == 0) { constintdr[4] = {-1, 0, 1, 0}; constintdc[4] = {0, -1, 0, 1}; intcosts[4]; for (int d = 0; d < 4; d++) costs[d] = cost_of(xlh.first + dr[d], ylh.first + dc[d], X, Y, N); cost = *min_element(costs, costs + 4); opts = count(costs, costs + 4, cost); } out << cost << " " << opts << "\n"; return 0; }

Below is Bruce's solution

#include <fstream>
#include <algorithm>
#include <utility>
#include <cstdlib>

using namespace std;

static pair<int, int> medians(const int *Z, int N)
{
    int s[N];
    copy(Z, Z + N, s);
    nth_element(s, s + N / 2, s + N);
    if (N & 1) return make_pair(s[N / 2], s[N / 2]);
    else return make_pair(*max_element(s, s + N / 2), s[N / 2]);
}

static int cost_of(int x, int y, int *X, int *Y, int N)
{
    int cost = 0;
    for (int i = 0; i < N; i++)
        cost += abs(X[i] - x) + abs(Y[i] - y);
    return cost;
}

int main()
{
    int N;
    pair<int, int> xlh, ylh;
    int opts;
    int cost;
    ifstream in("newbarn.in");
    ofstream out("newbarn.out");
    in >> N;
    int X[N], Y[N];

    for (int i = 0; i < N; i++)
        in >> X[i] >> Y[i];
    xlh = medians(X, N);
    ylh = medians(Y, N);
    opts = (xlh.second - xlh.first + 1) * (ylh.second - ylh.first + 1);
    for (int i = 0; i < N; i++)
    {
        if (X[i] >= xlh.first && X[i] <= xlh.second
            && Y[i] >= ylh.first && Y[i] <= ylh.second)
            opts--;
    }
    cost = cost_of(xlh.first, ylh.first, X, Y, N);
    if (opts == 0)
    {
        const int dr[4] = {-1, 0, 1, 0};
        const int dc[4] = {0, -1, 0, 1};
        int costs[4];
        for (int d = 0; d < 4; d++)
            costs[d] = cost_of(xlh.first + dr[d], ylh.first + dc[d], X, Y, N);
        cost = *min_element(costs, costs + 4);
        opts = count(costs, costs + 4, cost);
    }
    out << cost << " " << opts << "\n";
    return 0;
}