Cow Sorting [Osman Ay, 2004]

Farmer John's N (1 <= N <= 10,000) cows are lined up to be milked in the evening. Each cow has a unique "grumpiness" level in the range 1...100,000. Since grumpy cows are more likely to damage FJ's milking equipment, FJ would like to reorder the cows in line so they are lined up in increasing order of grumpiness. During this process, the places of any two cows (not necessarily adjacent) can be interchanged. Since grumpy cows are harder to move, it takes FJ a total of X+Y units of time to exchange two cows whose grumpiness levels are X and Y. Please help FJ calculate the minimal time required to reorder the cows. PROBLEM NAME: csort INPUT FORMAT: * Line 1: A single integer: N. * Lines 2..N+1: Each line contains a single integer: line i+1 describes the grumpiness of cow i. SAMPLE INPUT (file csort.in): 3 2 3 1 INPUT DETAILS: Three cows are standing in line with respective grumpiness levels 2, 3, and 1. OUTPUT FORMAT: * Line 1: A single line with the minimal time required to reorder the cows in increasing order of grumpiness. SAMPLE OUTPUT (file csort.out): 7 OUTPUT DETAILS: 2 3 1 : Initial order. 2 1 3 : After interchanging cows with grumpiness 3 and 1 (time=1+3=4). 1 2 3 : After interchanging cows with grumpiness 1 and 2 (time=2+1=3).

ძროხების სორტირება – ბექა მაისურაძის თარგმანი

ფერმერ ჯონის N (1 <= N <= 10,000) ძროხა დგას რიგში, რათა ჯონმა საღამოს ისინი მოწველოს. თითოეულ ძროხას აქვს თავისი უნიკალური გაბრაზებულობის დონე 1-დან 100,000-მდე. ვინაიდან მეტად გაბრაზებული ძროხისგან მეტად მოსალოდნელია მოსაწველი აღჭურვილობის დაზიანება, ჯონს სურს გაბრაზებულობის დონის ზრდის მიხედვით დააყენოს ძროხები რიგში. პროცესის განმავლობაში ორ ძროხას (არა აუცილებლად მეზობლებს) შეიძლება ადგილები გაეცვალოთ. რადგან გაბრაზებული ძროხის გადაადგილება უფრო რთულია, შესაბამისად, ჯონს ჭირდება X +Y დრო ისეთი 2 ძროხის ადგილების გასაცვლელად, რომელთა გაბრაზების დონე შესაბამისად X და Y-ია. გთხოვთ, დაეხმაროთ ჯონს, გამოიანგარიშოს, რა მინიმალური დრო დაჭირდება ძროხების რიგის სასურველი თანმიმდევრობით გადალაგებას. შესატანი მონაცემების (INPUT) ფორმატი: *პირველი ხაზი: ერთადერთი ნატურალური რიცხვი - N. *მომდევნო N ხაზი: თითოეული ხაზი შეიცავს ერთ ნატურალურ რიცხვს. i+1-ე ხაზზე აღწერილი რიცხვი ასახავს i-ური ძროხის გაბარაზებულობის დონეს. შესატანი მონაცემების მაგალითი (csort.in): 3 2 3 1 ახსნა: სამი ძროხა დგას რიგში შესაბამისად 2, 3 და 1 გაბრაზების დონეებით. გამოსატანი ინფორმაციის (OUTPUT) ფორმატი: *ხაზი 1: ერთი ნატურალური რიცხვი, რომელიც არის მინიმალური დროის ხანგრძლივობა, რომელიც საჭიროა ძროხების რიგის სასურველი თანმიმდევრობით დალაგებისთვის. გამოსატანი ინფორმაციის მაგალითი (csort.out): 7 ახსნა: 2 3 1 : პირველი ძროხის გაბრაზებულობის დონეა 2, მეორის – 3 და მესამის – 1. 2 1 3 : ადგილი გაეცვალა მეორე და მესამე ძროხებს, რომელთაც გაბრაზებულობის დონე შესაბამისად ჰქონდათ 3 და 1. 1 2 3 : ადგილი გაეცვალა პირველ და მეორე ძროხებს, რომელთაც გაბრაზებულობის დონე შესაბამისად ჰქონდათ 2 და 1.

csort

A powerful idea in dealing with sorting and permutations are disjoint cycles. Draw an arrow from each cow's current position to its target position. These arrows will create a graph that consists purely of disjoint cycles. It is well-known (and fairly easy to show) that resolving a cycle of length N requires N-1 exchanges. Furthermore, each element of the cycle will clearly need to be involved in one of the swaps. This leaves us with two possibilities for resolving a cycle, of which we use the best: Repeatedly swap the least grumpy cow in cycle with the cow that belongs in that spot. If the least grumpiness is L and the total grumpiness of the cycle is T, then this takes T + (N-2)L. We can also “borrow” a cow from outside, in particular the globally least grumpy cow, with grumpiness G. We first swap cows with grumpiness G and L, resolve the cycle as before but using G instead of L, then swap G and L back into place. Total time: T + NG + 2L. A rigorous proof that this is optimal turns out to be quite difficult. A possible starting point is to define the potential of any permutation to be the total time required by this algorithm, then show that no possible swap can decrease the potential by more than the cost of the swap. Below is Bruce Merry's solution. #include <fstream> #include <algorithm> #include <vector> #include <utility> using namespace std; /* Let the permutation be broken into disjoint cyclic permutations. Let * m be the globally minimum ID. Define the weight of a cyclic permutation * with k elements, smallest element w, and sum of remaining element s to be * s + f(k, w), where f(k, w) = min((k-1)w, (k-1)m + 2(m+w)). Note that * if i < k and (k-1)w < (k-1)m + 2(m+w) then (i-1)w < (i-1)m + 2(m+w). * * We claim that the sum of weights is a semi-invariant that cannot decrease * by more than the cost of the exchanges made. * For a split exchange, we go from * (a_1...a_i b_1...b_j) to (a_1...a_i)(b_1...b_j) at a cost of * a_i + b_j. The sums of the new weights plus this cost is at least * s_a + s_b + a_i + b_j + min((i-1)w, (i-1)m + 2(m + w)) * + min((j-1)w, (j-1)m + 2(m + w)) * >= s + w + min((i-1)w, (i-1)m + 2(m + w)) * + min((j-1)w, (j-1)m + 2(m + w)) * = s + w + (i+j-2)w = s + (k - 1)w * or s + w + (i-1)w + (j-1)m + 2(m+w) >= s + w + (k-1)m + 2(m + w) * or s + w + (i+j-2)m + 4(m + w) > s + (k-1)m + 2(m + w) * * For a joining exchange, we go from * (a_1...a_i)(b_1...b_j) to (a_1...a_i b_1...b_j) * at a cost of a_i + b_j. We assume that w comes from a i.e. w = w_a. * The new weight plus this cost is at least * s + a_i + b_j + min((k-1)w, (k-1)m + 2(m+w)) * >= s + w_a + w_b + min((k-1)w, (k-1)m + 2(m+w)) * >= s_a + s_b + w + 2w_b + min((k-1)w, (k-1)m + 2(m+w)) * If the min is (k-1)w, then it is * = s_a + (i-1)w + s_b + (j-1)w + 2w + 2w_b * >= [s_a + (i-1)w] + [s_b + (j-1)m + 2(m+w_b)] * >= s_a + min((i-1)w_a, (i-1)m + 2(m+w_a)) * + s_b + min((j-1)w_b, (j-1)m + 2(m+w_b)) * However, if the min is (k-1)m + 2(m+w) then it is * = s_a + s_b + w + 2w_b + (k-1)m + 2(m+w) * = s_a + s_b + (i-1)m + (j-1)m + 2(m+w) + m + w + 2w_b * >= [s_a + (i-1)m + 2(m+w)] + [s_b + (j-1)m + 2(m + w_b)] * >= s_a + min((i-1)w_a, (i-1)m + 2(m+w_a)) * + s_b + min((j-1)w_b, (j-1)m + 2(m+w_b)) */ int main() { vector<pair<int, int> > cows; int N; int ans = 0; ifstream in("csort.in"); ofstream out("csort.out"); in >> N; for (int i = 0; i < N; i++) { int x; in >> x; cows.push_back(make_pair(x, i)); } sort(cows.begin(), cows.end()); int m = cows[0].first; for (int i = 0; i < N; i++) if (cows[i].second != -1) { int j = cows[i].second; int w = cows[i].first; int k = 1; cows[i].second = -1; while (j != i) { ans += cows[j].first; int nxt = cows[j].second; cows[j].second = -1; j = nxt; k++; } ans += min((k - 1) * w, (k - 1) * m + 2 * (m + w)); } out << ans << "\n"; return 0; }

csort – ბექა მაისურაძის თარგმანი

როდესაც საქმე გვაქვს სორტირებასთან და პერმუტაციებთან, ამ დროს გამოსადეგია დანაწევრებული ციკლების (disjoint cycles) იდეა. გავავლოთ ისარი თითოეული ძროხის ამჟამინდელი პოზიციიდან მის სამიზნე პოზიციამდე. ეს ისრები შექმნის გრაფს, რომელიც შეიცავს დანაწევრებულ ციკლებს. კარგად ცნობილი ფაქტია (და საჩვენებლად საკმაოდ მარტივიც), რომ N სიგრძის ციკლის ამოხსნა (resolve) მოითხოვს N-1 გადანაცვლებას. უფრო კონკრეტულად, ციკლის თითოეული ელემენტი აუცილებლად ჩაერთვება ამ გადანაცვლებებიდან ერთ-ერთში. ამით ჩვენ გვაქვს ციკლის ამოხსნის ორი შესაძლებლობა, საიდანაც ჩვენ გამოვიყენებთ საუკეთესო მათგანს: ყოველ ჯერზე გავუცვალოთ ადგილები ციკლის ყველაზე ნაკლებად გაბრაზებულ A ძროხასა და იმ ძროხას, რომელთანაც დაკავშირებულია ისრით. თუ A ძროხის გაბრაზებულობის დონე არის L და ციკლის ჯამური დონე კი - T, მაშინ ამ პროცესს დაჭირდება T + (N-2)L დრო. ჩვენ ასევე შეგვიძლია “ვისესხოთ“ ძროხა გარედან, კონკრეტულად გლობალურად ყველაზე ნაკლებად გაბრაზებული, რომლის გაბრაზებულობის დონე არის G. თავდაპირველად ჩვენ გადავანაცვლებთ ძროხებს დონეებით G და L, ამოვხსნით (resolve) ციკლს როგორც მანამდე, მაგრამ L-ის მაგივრად გამოვიყენებთ G-ს, შემდეგ ჩავანაცვლებთ G-ს და L-ს ისევ საწყის ადგილზე. სრული დრო: T + NG + 2L. ზუსტი დამტკიცება ამ ამოხსნის ოპტიმალურობისა საკმაოდ რთულია. შესაძლო საწყისი წერტილი არის ის, რომ ამ ალგორითმით განისაზღვროს ნებისმიერი პერმუტაციის პოტენციალი მისი ოპტიმალურობისა, შემდეგ ვაჩვენოთ, რომ არცერთი შესაძლო გაცვლა არ ამცირებს პოტენციალს თავის (გაცვლის) წონაზე მეტად. ანუ ნებისმიერი გაცვლის შედეგი (მთლიანი დრო) მეტი ან ტოლი იქნება ამ ალგორითმით მიღებული შედეგისა.

Below is Bruce Merry's solution

#include <fstream>
#include <algorithm>
#include <vector>
#include <utility>

using namespace std;

/* Let the permutation be broken into disjoint cyclic permutations. Let
 * m be the globally minimum ID. Define the weight of a cyclic permutation
 * with k elements, smallest element w, and sum of remaining element s to be
 * s + f(k, w), where f(k, w) = min((k-1)w, (k-1)m + 2(m+w)). Note that
 * if i < k and (k-1)w < (k-1)m + 2(m+w) then (i-1)w < (i-1)m + 2(m+w).
 *
 * We claim that the sum of weights is a semi-invariant that cannot decrease
 * by more than the cost of the exchanges made.
 * For a split exchange, we go from
 * (a_1...a_i b_1...b_j) to (a_1...a_i)(b_1...b_j) at a cost of
 * a_i + b_j. The sums of the new weights plus this cost is at least
 * s_a + s_b + a_i + b_j + min((i-1)w, (i-1)m + 2(m + w))
 *                       + min((j-1)w, (j-1)m + 2(m + w))
 * >= s + w + min((i-1)w, (i-1)m + 2(m + w))
 *          + min((j-1)w, (j-1)m + 2(m + w))
 * = s + w + (i+j-2)w = s + (k - 1)w
 * or s + w + (i-1)w + (j-1)m + 2(m+w) >= s + w + (k-1)m + 2(m + w)
 * or s + w + (i+j-2)m + 4(m + w) > s + (k-1)m + 2(m + w)
 *
 * For a joining exchange, we go from
 * (a_1...a_i)(b_1...b_j) to (a_1...a_i b_1...b_j)
 * at a cost of a_i + b_j. We assume that w comes from a i.e. w = w_a.
 * The new weight plus this cost is at least
 * s + a_i + b_j + min((k-1)w, (k-1)m + 2(m+w))
 * >= s + w_a + w_b + min((k-1)w, (k-1)m + 2(m+w))
 * >= s_a + s_b + w + 2w_b + min((k-1)w, (k-1)m + 2(m+w))
 * If the min is (k-1)w, then it is
 *  = s_a + (i-1)w + s_b + (j-1)w + 2w + 2w_b
 * >= [s_a + (i-1)w] + [s_b + (j-1)m + 2(m+w_b)]
 * >= s_a + min((i-1)w_a, (i-1)m + 2(m+w_a))
 *  + s_b + min((j-1)w_b, (j-1)m + 2(m+w_b))
 * However, if the min is (k-1)m + 2(m+w) then it is
 *  = s_a + s_b + w + 2w_b + (k-1)m + 2(m+w)
 *  = s_a + s_b + (i-1)m + (j-1)m + 2(m+w) + m + w + 2w_b
 * >= [s_a + (i-1)m + 2(m+w)] + [s_b + (j-1)m + 2(m + w_b)]
 * >= s_a + min((i-1)w_a, (i-1)m + 2(m+w_a))
 *  + s_b + min((j-1)w_b, (j-1)m + 2(m+w_b))
 */

int main()
{
    vector<pair<int, int> > cows;
    int N;
    int ans = 0;
    ifstream in("csort.in");
    ofstream out("csort.out");

    in >> N;
    for (int i = 0; i < N; i++)
    {
        int x;
        in >> x;
        cows.push_back(make_pair(x, i));
    }
    sort(cows.begin(), cows.end());
    int m = cows[0].first;

    for (int i = 0; i < N; i++)
        if (cows[i].second != -1)
        {
            int j = cows[i].second;
            int w = cows[i].first;
            int k = 1;
            cows[i].second = -1;
            while (j != i)
            {
                ans += cows[j].first;
                int nxt = cows[j].second;
                cows[j].second = -1;
                j = nxt;
                k++;
            }
            ans += min((k - 1) * w, (k - 1) * m + 2 * (m + w));
        }

    out << ans << "\n";
    return 0;
}