Need help with Exchange Arguments problem

Revision en1, by Bekh, 2019-09-07 20:15:04

Hello,

I have been trying solving this problem: 1747 — Swap Space

Here is my WA code: https://ideone.com/64kU5M

I think the issue is with my comparator since I've seen solutions with other comparators that get AC like this one: https://github.com/morris821028/UVa/blob/master/volume017/1747%20-%20Swap%20Space.cpp

The idea behind my comparator is: if there are 2 disks to be reformatted $$$X$$$ and $$$Y$$$ and I have available storage $$$S$$$. Then if I take $$$X$$$ before $$$Y$$$

$$$S$$$ must be >= $$$X.A$$$ and $$$S + X.B - X.A$$$ >= $$$Y.A$$$, with rearragement:
$$$S >= max(X.A, Y.A - X.B + X.A)$$$

Similarly if i take $$$Y$$$ before $$$X$$$
$$$S >= max(Y.A, X.A - Y.B + Y.A)$$$

thus my comparator between $$$X$$$ and $$$Y$$$ is like this

bool cmp(pair<long long, long long> x, pair<long long, long long> y)
{
    return max(x.first, x.first + y.first - x.second) < max(y.first, x.first + y.first - y.second);
}

Could somebody tell me what's wrong with my comparator?

Thanks.

Tags greedy, sortings, exchange arguments

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English Bekh 2019-09-07 20:15:04 1153 Initial revision (published)