10797 - Peaceful Sharing
Moderator: Board moderators
-
- Guru
- Posts: 647
- Joined: Wed Jun 26, 2002 10:12 pm
- Location: Hong Kong and New York City
- Contact:
10797 - Peaceful Sharing
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.
-
- System administrator & Problemsetter
- Posts: 399
- Joined: Sat Jan 12, 2002 2:00 am
hmm
I don't know what length will u consider long ![:)](./images/smilies/icon_smile.gif)
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.
![:)](./images/smilies/icon_smile.gif)
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.
-
- System administrator & Problemsetter
- Posts: 399
- Joined: Sat Jan 12, 2002 2:00 am
Re: 10797 - Peaceful Sharing
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.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.
-
- Learning poster
- Posts: 63
- Joined: Thu Apr 04, 2002 2:00 am
-
- Experienced poster
- Posts: 123
- Joined: Thu Feb 10, 2005 4:46 am
-
- Experienced poster
- Posts: 123
- Joined: Thu Feb 10, 2005 4:46 am
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.
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!
-
- Experienced poster
- Posts: 123
- Joined: Thu Feb 10, 2005 4:46 am
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!
-
- System administrator & Problemsetter
- Posts: 399
- Joined: Sat Jan 12, 2002 2:00 am
hmm
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.
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.
-
- Experienced poster
- Posts: 123
- Joined: Thu Feb 10, 2005 4:46 am
Shahriar,
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.
If you are the author, they why don't you know?I don't think the judge solution is O(N^2).
![:)](./images/smilies/icon_smile.gif)
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!
-
- Experienced poster
- Posts: 123
- Joined: Thu Feb 10, 2005 4:46 am
Yes, here it is. Called "Onion-peeling". http://cgm.cs.mcgill.ca/~orm/ontri.html
To be the best you must become the best!
-
- System administrator & Problemsetter
- Posts: 399
- Joined: Sat Jan 12, 2002 2:00 am
hmm
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.
I never thought of convex hull while setting this problem so cannot comment on your issue.
-
- Experienced poster
- Posts: 123
- Joined: Thu Feb 10, 2005 4:46 am
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?
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!
-
- System administrator & Problemsetter
- Posts: 399
- Joined: Sat Jan 12, 2002 2:00 am
hmm
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.
-
- Experienced poster
- Posts: 123
- Joined: Thu Feb 10, 2005 4:46 am