Finding an arrangement that yield minimum salary

Question

Once again I am stuck with a sopj problem pilots

The problem statement is..

Charlie acquired airline transport company and to stay in business he needs to lower the expenses by any means possible. There are N pilots working for his company (N is even) and N/2 plane crews needs to be made. A plane crew consists of two pilots - a captain and his assistant. A captain must be older than his assistant. Each pilot has a contract granting him two possible salaries - one as a captain and the other as an assistant. A captain's salary is larger than assistant's for the same pilot. However, it is possible that an assistant has larger salary than his captain. Write a program that will compute the minimal amount of money Charlie needs to give for the pilots' salaries if he decides to spend some time to make the optimal (i.e. the cheapest) arrangement of pilots in crews.

input

The first line of input contains integer N, 2 ≤ N ≤ 10,000, N is even, the number of pilots working for the Charlie's company. The next N lines of input contain pilots' salaries. The lines are sorted by pilot's age, the salaries of the youngest pilot are given the first. Each of those N lines contains two integers separated by a space character, X i Y, 1 ≤ Y < X ≤ 100,000, a salary as a captain (X) and a salary as an assistant (Y).

output

The first and only line of output should contain the minimal amount of money Charlie needs to give for the pilots' salaries.

sample

input

4 
5000 3000 
6000 2000 
8000 1000 
9000 6000 

output 19000

input

6 
10000 7000 
9000 3000 
6000 4000 
5000 1000 
9000 3000 
8000 6000 

output 32000

Now i am using a greedy approch as it is clear that first pilot should be assistant and after that i check if it will be possible to save money by making the pilot captain if yes then i will make him a captain else an assistant.

It is perfectly working for most of the cases but I get a wrong awnser.

my code is..

#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define FOR(i,n) for(int i=0;i<n;i++)

int main()
{
    int n;
    //freopen("input.txt","r",stdin);
    cin>>n;
    vector<pair<pii,int> > data;
    FOR(i,n)
    {
        int csal,asal;
        cin>>csal>>asal;
        int diff=csal-asal;
        data.pb(mp(mp(csal,asal),diff));
    }
    int ccount=0,acount=0,sal=0;
    FOR(i,n)
    {
        if(acount<n/2)
        {
            int flag=1;
            for(int j=i+1;j<=i+(acount-ccount);j++)
            {
                if(data[i].se<=data[j].se)
                {
                    //cout<<j<<" ";
                    flag=0;
                    break;
                }
            }
            if(flag)
            {
                sal+=data[i].fi.se;
                acount++;
            }
            else
            {
                sal+=data[i].fi.fi;
                ccount++;
            }
        }
        else
        {
            sal+=data[i].fi.fi;
                ccount++;
        }
        //cout<<sal<<" "<<i<<"\n";
    }
    cout<<sal<<"\n";
    return 0;
}

please help me to solve this problem..

Answer 1

Here is a solution with O(N log N) running time. It uses greedy algorithm, but it is different from yours.

1)Let's assume that delta[i] = X[i] - Y[i].
2)Now let's process pilots sorted by delta[i] in descending order. We will assume that all pilots are initially given captain positions.
3)Each pilot should be reassigned to assistant position if it is possible.
That's it. I claim that this algorithm always gives a correct result.

Proof:
1)When a pilot cannot be given an assistant job?
i)When there are no "free" captains to the right(in terms of age) of him(that is, if the number of captains to the right of him is greater than or equal to the number of assistants). Why could this happen? Only if there are "too many" assistants to the right of him. Let's assume that we decided to fix it. It would require changing one of the assistants to the captain. But if a pilot is an assistant, he was processed before the current pilot. It means that his delta is greater(recall that we iterate over them in sorted order). One more observation: one assistant can block only one captain(because the crew includes only one captain). These two observation show that changing something when it is not possible to make current pilot an assistant would only make the answer worse.
ii)When he is taken as a captain by an assistant to the left(in terms of age) from him. To fix it, it would be necessary to make that guy a captain again, like in i). It would make the answer only worse(the proof is the same as in the situation above).
2)Using mathematical induction and two observations above, it can be proven rigorously that this algorithm is correct.
3)This algorithm will always produce exactly N / 2 assistants because it makes a pilot an assistant whenever possible and there are exactly N / 2 possibilities to do it.

The only question remaining is: how to check if it is possible to make the current pilot an assistant?
Here is a fast way: let's assign each pilot 1 if he is a captain and -1 otherwise. Let's take a look at this array of -1 and 1 in order of pilots' ages. I claim that if there is a suffix with negative sum, the configuration is invalid. Otherwise, it is valid(this statement is not that hard to prove, but I will not post the proof here or there will too much proofs in my answer). So we need to maintain two operations: change -1 to 1(and vice versa) and tell if there is a suffix with negative sum. It is a standard problem and can be solved with segment tree(you can store total sum and minimum suffix sum in each node, update is easy because the value of only one element is changed at a time(that is, a value in a leaf)).

The complexity is O(N log N) because we need to sort the array and during the iteration at most 3 queries to a segment tree are done per one step(and each query takes O(log N) time).