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

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

10797 - Peaceful Sharing

Post by Larry » Thu Dec 30, 2004 7:45 pm

Is there a simpler way to solve this without calculating the median of the arrangements of the duals? It's O(n^2), but is that the solution the problemsetter was looking for (the implementation is long..)? Thanks for any hints.

shahriar_manzoor
System administrator & Problemsetter
Posts: 399
Joined: Sat Jan 12, 2002 2:00 am

hmm

Post by shahriar_manzoor » Fri Dec 31, 2004 2:19 am

I don't know what length will u consider long :)

My faster solution is 140 Lines
My slower (three times) is 100 lines
Kisman's solution is 40 lines (With STL) which is also quite slow but runs within time limit.

User avatar
Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong

Post by Cho » Sat Jan 01, 2005 8:45 am

my solution is less than 70 lines, without using any library except stdio.h.

shahriar_manzoor
System administrator & Problemsetter
Posts: 399
Joined: Sat Jan 12, 2002 2:00 am

Re: 10797 - Peaceful Sharing

Post by shahriar_manzoor » Sat Jan 01, 2005 9:15 am

Larry wrote:Is there a simpler way to solve this without calculating the median of the arrangements of the duals? It's O(n^2), but is that the solution the problemsetter was looking for (the implementation is long..)? Thanks for any hints.
I also forgot to reply the actual question. Yes I used median of arrangement as my idea to solve this problem. Kisman's idea was similar I think.

User avatar
Christian Schuster
Learning poster
Posts: 63
Joined: Thu Apr 04, 2002 2:00 am

Post by Christian Schuster » Thu Jan 13, 2005 6:25 pm

My solution has about 100 lines and uses a tiny bit of STL. I use an iterative approach, improving the selected mines in an alternating manner... And it seems to be quite fast. :D

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

Post by Destination Goa » Sun Feb 20, 2005 2:37 pm

I've got an idea of N*log^2(N) solution. If it works, I'll write it here.

P.S: Was that authors' intention of N^2 solution or they just didn't know how to code a better way for the problem they've put, but are aware of its existence?
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 3:43 pm

Well, my method didn't work (tried binary search over convex hull nodes). Though, there still might be another one which consider inner points as well. I was unable yet to find any n*log(n) ordering.

By the way, if the intentional complexity was O(N^2), so you wanted to prevent people from sending O(N^3), why did you set limit to 10'000, but not to 2000? 10'000 is not better than 2000 as O(N^3) blocker, but it is very confusing limit as O(N^2) allower.
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 3:46 pm

Also I won't be surprised if O(N^2) testing of the 1st set via 2nd set will differ from the opposite approach (testing 2nd set via 1st set) 5 or 6 times on time. E.g. TL will turn into AC once you make x=-x. Fair square limit of 2000-3000 won't allow such weird thing to happen.
To be the best you must become the best!

shahriar_manzoor
System administrator & Problemsetter
Posts: 399
Joined: Sat Jan 12, 2002 2:00 am

hmm

Post by shahriar_manzoor » Sun Feb 20, 2005 3:56 pm

I don't think the judge solution is O(N^2).

I have two solutions one was O(N^2) and modifying it slightly I made a better solution. But I allowed both the better and the O(N^2) to pass. I did not want a very bad O(N^2) to pass that is why N=10000. And I don't understand what is your problem if N=10000 and not 2000.

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

Post by Destination Goa » Sun Feb 20, 2005 4:10 pm

Shahriar,
I don't think the judge solution is O(N^2).
If you are the author, they why don't you know? :) Or you're not?

The problem is that whenever I see N=10'000 or greater, I seek for N*log^k(N) solution. I think that problems are intended to demand some asymptotics, but not optimizing N^2 (or N^3) to make it AC. Because for any such "solution" there is always a test which makes its worst. And all those "optimizatiosn" just increase the contanst, and you get a fair TL. Limits are a way to set an upper limit for demanded asymptotic.

Perhaps I am just too old problem solver, and what before was 1'000 now is 10'000. Well, never mind.

THE QUESTION:
Is there a way to build nested convex hulls of set of points better than at O(N^2)? I.e. once the outer hull is built, delete all its nodes and do it again until no points left (innermost hull may contain 1 or 2 points). If such algoritmh exists, there is possibility of logarithm for this problem.
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 4:16 pm

Yes, here it is. Called "Onion-peeling". http://cgm.cs.mcgill.ca/~orm/ontri.html
To be the best you must become the best!

shahriar_manzoor
System administrator & Problemsetter
Posts: 399
Joined: Sat Jan 12, 2002 2:00 am

hmm

Post by shahriar_manzoor » Sun Feb 20, 2005 4:33 pm

To be specific the judge solution is O(cN), where c is a constant of value around 100. "I don't think..." was another way to say "is not".

I never thought of convex hull while setting this problem so cannot comment on your issue.

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

Post by Destination Goa » Sun Feb 20, 2005 4:58 pm

No, onion-peeling won't work either. Well, it will give correct answer, but we'll have logarithm only for layer length, not on number of layers. So, if each layer has 3 nodes, we'll stay at O(n1*n2) = O(N^2).

What do you mean by C=100? CPU cycles, some fixed time or what? Or is this some sort of function which is 100 for N<=10'000? Would it remain 100 for N<=1'000'000?
To be the best you must become the best!

shahriar_manzoor
System administrator & Problemsetter
Posts: 399
Joined: Sat Jan 12, 2002 2:00 am

hmm

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

I used bisection in this problem. C is the number of iteration required in bisection to find the answer in the worst case. When N=10000000 C will not change.

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

Uh. I read one of your 1st posts incorrectly. You said that you also seek for the median, but you didn't say that you also perform it at O(N^2) :)

Anyway, my question about C remains.
To be the best you must become the best!

Post Reply

Return to “Volume 107 (10700-10799)”