10797 - Peaceful Sharing

All about problems in Volume 107. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Destination Goa
Experienced poster
Posts: 123
Joined: Thu Feb 10, 2005 4:46 am

Post by Destination Goa » Sun Feb 20, 2005 5:02 pm

Ok.
To be the best you must become the best!

Destination Goa
Experienced poster
Posts: 123
Joined: Thu Feb 10, 2005 4:46 am

Post by Destination Goa » Sun Feb 20, 2005 5:03 pm

I guess it depends on coordinate limits, right? like log(DX) * log(DY)

DX=MAXX-MINX, DY=MAXY-MINY

If so, then it's actually O(N*log(DX)*log(DY)) for arbitrary values of X/Y fitting into 'long double' without precision issues. Might be O(N*log(N)) if we can compact space between neighboring X/Y values.

I'll know when I find it :)
To be the best you must become the best!

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Sun Nov 19, 2006 3:39 am

I implemented my algorithm in 40 lines, and it's O((log X)*(n log n))
using stl. I can make it faster, but it's not needed to get AC.

phy
New poster
Posts: 3
Joined: Sat Apr 26, 2008 8:41 am

Re: 10797 - Peaceful Sharing

Post by phy » Mon Oct 20, 2008 8:46 pm

Could someone explain or introduce something about the term "dual" or "median of arrangement"?
This problem looks interesting. But I just got no idea on solving this...

Thanks in advance.

Post Reply

Return to “Volume 107 (10700-10799)”