## Search found 18 matches

Tue Aug 07, 2007 8:29 am
Forum: Volume 112 (11200-11299)
Topic: 11257 - New Marketing Plan
Replies: 23
Views: 8683
In my case, the epsilon is 1e-7, but 0.0009 is way too big. I would never use any epsilon larger than 1e-6. The thing is that this is the smallest epsilon I can use without timeouting, I wonder if people that solved it using the nested ternary search approach did something better in complexity than...
Mon Aug 06, 2007 11:56 pm
Forum: Volume 112 (11200-11299)
Topic: 11257 - New Marketing Plan
Replies: 23
Views: 8683
Ivan wrote:In the contest it took a few submissions to figure out the right balance between precision and runtime but finally I got "solved".
I've implemented this approach using epsilon=0.0009 but got WA, can you tell me the largest value of epsilon you used to get it solved?
Fri Oct 20, 2006 10:25 pm
Forum: Volume 101 (10100-10199)
Topic: 10167 - Birthday Cake
Replies: 16
Views: 7722
Got AC using your random approach (I had a bug in intializing an array :oops: ). Btw, that "if both sets same size, break" part is wrong, should be "if both sets are of size n, break". Just check that you really break. Funny thing I got AC using my wrong condition, I think there ...
Fri Oct 20, 2006 9:21 pm
Forum: Volume 101 (10100-10199)
Topic: 10167 - Birthday Cake
Replies: 16
Views: 7722
Well I've tried the random approach as follows: while(true){ -randomly generate A, B. That is O(1) -divide the points in two sets where each set lies in one side of the line Ax+BY=0. That is O(n) -if both sets has the same size break } However the soltion also times out! do you make any further enha...
Fri Oct 20, 2006 4:37 pm
Forum: Volume 101 (10100-10199)
Topic: 10167 - Birthday Cake
Replies: 16
Views: 7722
do you mean you randomly choose A then randomly choose B and check if the same number of points lie on each of the line sides?

I think this problem has some mathematical approach (looking at the very small times it has been solved in), any ideas?
Fri Oct 20, 2006 3:02 pm
Forum: Algorithms
Topic: MinCost MaxFlow code
Replies: 20
Views: 15922
I'm trying to solve this problem http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=3562 which is very much related to this thread but always get WA actually i'm using Igor's code for mincost max flow, and for max cost I let cost [j] = MaxCost we got-cost [j] and rerun the mincost max...
Thu Oct 19, 2006 11:07 pm
Forum: Volume 101 (10100-10199)
Topic: 10167 - Birthday Cake
Replies: 16
Views: 7722
Can anyone explain how to solve this problem?

Thanks alot
Mon Oct 16, 2006 1:08 pm
Forum: Volume 111 (11100-11199)
Topic: 11125 - Arrange Some Marbles
Replies: 20
Views: 14920
Usually i don't include <cstring>, memset doesn't need it on VC++ and GCC if i remember correctly, but the wierd thing is that i tried to submit the problem now with memset and without including any additional headers and got AC! anyway i'll try cstring the next time i got compilation error for mems...
Mon Oct 16, 2006 12:54 pm
Forum: Volume 111 (11100-11199)
Topic: 11122 - Tri Tri
Replies: 29
Views: 9559
I have code to find intersection of 2 convex polygons, so I just used that, then compute the area of the resulting polygons. I'm interested in implementing a convex polygon intersection algorithm, can you post your algorithm? (code, resources, links ...) Also can anyone expalin other approaches to ...
Mon Oct 16, 2006 12:49 pm
Forum: Volume 111 (11100-11199)
Topic: 11125 - Arrange Some Marbles
Replies: 20
Views: 14920
Here is my code, #include<algorithm> #include<iostream> using namespace std; #define big int int cNum[4]; big table[5][8][8][8][8][8][5][8]; big get(int firstColor, int firstSize, int c1, int c2, int c3, int c4, int prevColor, int prevSize){ if(c1 == 0 && c2 == 0 && c3 == 0 &&...
Mon Oct 16, 2006 9:11 am
Forum: Volume 111 (11100-11199)
Topic: 11122 - Tri Tri
Replies: 29
Views: 9559
Those two have all their points in common - I am not sure why you thought that we were looking for points with integer coordinates only. I thought so because in the sample input we have: 0 0 2 0 0 2 1 1 3 3 2 3 and answer is no although they've a common area (infinite non integer points)! can you p...
Mon Oct 16, 2006 6:54 am
Forum: Volume 111 (11100-11199)
Topic: 11125 - Arrange Some Marbles
Replies: 20
Views: 14920
During the contest i got AC using the following recursion get(firstGroupColor, firstGroupSize,firstColorAvaiable,secondColorAvaiable, thirdColorAvaiable,fourthColorAvaiable, prevGroupColor, prevGroupSize) = { num = 0; for(each color i from 1 to 4) for(each size j from 1 to avaialable of color i) if(...
Mon Oct 16, 2006 6:44 am
Forum: Volume 111 (11100-11199)
Topic: 11122 - Tri Tri
Replies: 29
Views: 9559

### Re: 11122 - Tri Tri

I'm a bit confused about this problem, does interior point means a lattice point or just an a common area? I assume the first, so shouldn't this testcase output no (I see that you output yes for it)?

0 0 1 0 1 1
0 0 1 0 1 1
Sun Sep 17, 2006 11:19 pm
Forum: Volume 110 (11000-11099)
Topic: 11090 - Going in Cycle!!
Replies: 23
Views: 14236
Very interesting solution thanks alot. by the way I can't find Karp's algorithm in Cormen, is it really there? (actually I looked in the index and found nothing except for an excecise talking about minimum mean cycle).
Sat Sep 16, 2006 3:26 pm
Forum: Volume 110 (11000-11099)
Topic: 11090 - Going in Cycle!!
Replies: 23
Views: 14236
Thanks alot it helped very much, I got AC after getting over a couple of things, 1- The Karp's pseudo code in the paper has a mistake in line 10, we should set lamda to a small value instead of INF. 2- I've applied Kosaraju's Algorithm for SCC as you've advised. by the way do you know if these algor...