Malay Keshav

Download Resume PDF

Malay Keshav

Netaji Subhas Institute of Technology

ACM ICPC Amritapuri 2013 – Problem B (Sorted Queues) – Solution

December 29, 2013, by malay.keshav, category ACM ICPC, All, Editorial

This invloved using Linear Dynamic Programming.
The subproblem was to divide the Single queue into multiple independent queues and solve for them individually.

Let the two queues be A[N] and B[N]. The queue is separated at critical points. These critical points are those indexes i where the following the condition is satisfied :
(b[i] > a[i-1] && a[i] > b[i-1]) && (a[i] > a[i-1] && b[i] > b[i-1])

Once the critical points are found, the independent queues are simply the elements between two critical points.
Scan from Left to Right and check every element if they are valid or not. If they are not valid, SWAP the elements of the two queues. If the elements are still invalid, then there is no solution, and output -1. Else move on to the next element.

Another important point to note, is that for a subproblem of size M. If the number of swaps calculated is S, then
2*S <= M
If this is not true, set
S = M-S
This is because if (eg) M = 5 and S = 3. Then instead of swapping 3 elements, we can swap the other 2 elements to obtain the same valid queue.

 

for(int i =1;i<n;i++){
	if(!isValid(i)){
		SWAP(a[i], b[i]);
		ss++;
		if(!isValid(i)){
			noAns = true;
			break;
		}
	}
	else if(b[i] > a[i-1] && a[i] > b[i-1]){
		ans +=  (2*ss)>(i-ii)?(i-ii-ss):ss;
		ss = 0;
		ii = i;
	}
	if(noAns)
		break;
}
if(ss!= 0)	
	ans +=  (2*ss)>(n-ii)?(n-ii-ss):ss;
if(noAns)
	cout << -1 << endl;
else
	cout << ans << endl;

Comments are closed.