Fashion Shows FASHION

[vinaye_sof]

How to solve this problem? Are we supposed to solve it by greedy?

[ajaysomani_sof]

Yeah. I guess so

[kill_em_all]

it wud be obvious that it's greedy if u what was "rearrangement inequality"

[disillusioned_sof]

I remember "rearrengement inequality" from my math classes: we learnt something about spaces, metrics and so on.

[mpr_sof]

This problem doesn't require anything sophisticated. Fact: you'll get the highest possible product if you multiply the highest number in the first list by the highest number in the second list.

[disillusioned_sof]

Well, thanks to [color=red]kawigi [/color] for so many good problems on Sphere, but this one is purely mathematical, coding part is sorting only. Once we started to programming, let's do programming
We would like to see such problems as "Exchange Operations" here, and 851 - "Maze" on UVa.

[sefak]

This problem doesn't require anything sophisticated. Fact: you'll get the highest possible product if you multiply the highest number in the first list by the highest number in the second list.

Ok, I have solved the problem by sorting. But can someone explain the idea behind this?

Thanks.

[TripleM_sof]

(ab + cd) - (ad + bc) = (a-c)(b-d). You figure out the rest.

[jsuryasuba]

Anyone please explain, I used Arrays.sort() in java to sort the array. When I used merge sort, I got TLE, where as when I used merge sort the code got accepted. How it happens? Time complexity of merge sort is always <= timecomplexity of quick sort, right?