i_will_become_red's blog

Help in Sorting a three value sequence
By i_will_become_red, history, 9 years ago, In English

I was solving a problem "Sorting a three value sequence" USACO training gateway. I managed to solve the problem on my own. But in analysis section I found a solution given below, I was unable to understand whats the use of 2*(max(s12, s21)- min(s12, s21). plz explain me I am a newbie ?

#include <fstream>

using namespace std;

int min (int a, int b) { return a < b ? a : b; }
int max (int a, int b) { return a > b ? a : b; }

int main () {
    int s[1024];
    int n;
    int sc[4] = {0};
    
    ifstream fin("sort3.in");
    ofstream fout("sort3.out");
    fin>>n;
    for (int i = 0; i < n; i++) {
        fin>>s[i];
        sc[s[i]]++;
    }
    int s12 = 0, s13 = 0, s21 = 0, s31 = 0, s23 = 0, s32 = 0;
    for (int i = 0; i < sc[1]; i++){
        if (s[i] == 2) s12++;
        if (s[i] == 3) s13++;
    }
    
    for (int i = sc[1]; i < sc[1]+sc[2]; i++){
        if (s[i] == 1) s21++;
        if (s[i] == 3) s23++;
    }
    
    for (int i = sc[1]+sc[2]; i < sc[1]+sc[2]+sc[3]; i++){
        if (s[i] == 1) s31++;
        if (s[i] == 2) s32++;
    }
    
    fout<<min(s12, s21)+min(s13, s31)+min(s23, s32) +
					2*(max(s12, s21) - min(s12, s21))<<endl;
    return 0;
}
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Let G1 be the portion of the array that should have 1's at the end, and similarly, G2 and G3 the same for 2's and 3's.

  • Step 1: A swap affects at most two elements, so you can't correct more than that with a single swap. Swap 1's in G2 with 2's in G1, 1's in G3 with 3's in G1 and 2's in G3 with 3's in G2. You'll be correcting two elements with every one of those swaps, so it's optimum.
  • Step 2: Suppose you're not finished yet, then it means that there's some group Gx that contains an element y (y! = x), which also means that group Gy contains an unwanted element z (z! = y), but this also implies that z! = x because otherwise it's a swap we should have done in step 1, and finally group Gz contains an unwanted element which must be x. In other words, the remaining unordered elements form cycles, and whatever the direction of the cycles, there must either be a 1 in G2 or a 2 in G1 and you need two swaps to correct three elements. That's where the 2*(max(s12, s21)- min(s12, s21)) comes from.
→ Reply