Search found 105 matches
- Sun Aug 24, 2008 8:02 pm
- Forum: Volume 114 (11400-11499)
- Topic: 11476 - Factorizing Large Integers
- Replies: 17
- Views: 8868
Re: 11476 - Factorizing Large Integers
6609411 11476 Factorizing Larget Integers Accepted C++ 2.520 2008-08-24 17:28:24 Did anyone get accepted without caching primes ? Can you please send you code to temper3243@gmail.com i used brent + fermat. even with only brent i got accepted. i got couple of TLE's because of not caching primes. Once...
- Sat Aug 23, 2008 1:51 am
- Forum: Volume 114 (11400-11499)
- Topic: 11476 - Factorizing Large Integers
- Replies: 17
- Views: 8868
Re: 11476 - Factorizing Large Integers
hi , i'm trying to get accept using brents version, i get the factors but it gets TLE, if i increase the NOTRIES it becomes TLE, otherwise it doesn't find a factor , Is x^1 + C the optimal function ? Can someone give me their fast algorithm ? i want to see how to improve upon this. Please post some ...
- Mon Jun 30, 2008 7:40 pm
- Forum: Algorithms
- Topic: 2D lattice number of triangles
- Replies: 5
- Views: 1741
Re: 2D lattice number of triangles
i have the algorithm which calculates in 1st and 2nd quad and then translations work but it is slow. Is it optimizable ? or any other better ways. It is of the order (h*h*2w), when i evaluate the test case (250*250*500) 250 250 1 (area) ans is 3618895456 Time is real 0m2.358s Now if i reduce that 2w...
- Sun Jun 29, 2008 5:12 pm
- Forum: Algorithms
- Topic: 2D lattice number of triangles
- Replies: 5
- Views: 1741
Re: 2D lattice number of triangles
Solution in O(S^3) time, where S is max(a, b): Consider all triangles such that one of their vertices is (0, 0), and the two others are (x1, y1) and (x2, y2), where 0 <= x1, x2 <= a, 0 <= y1, y2 <= b. You can enumerate all of them in O(S^3) time by brute forcing any three of these numbers (for exam...
- Mon Jun 16, 2008 2:09 pm
- Forum: Algorithms
- Topic: 2D lattice number of triangles
- Replies: 5
- Views: 1741
Re: 2D lattice number of triangles
Thanks mf for all your replies and for the future replies :) You might want to look at this thread after 2 or 3 days . I asked it here. http://groups.google.com/group/sci.math/browse_thread/thread/8939ffbb70b916f3# For area =1 , they have a closed form (-1 + 4 sum_{k=1}^{500} phi(k)) , don't know ho...
- Sun Jun 15, 2008 9:57 pm
- Forum: Algorithms
- Topic: 2D lattice number of triangles
- Replies: 5
- Views: 1741
2D lattice number of triangles
hi, this problem is from spoj VTRI2. We have a bounded 2-D lattice , now consider the 1st quadrant (ie x>=0,y>=0, x and y are positive integers such that x <= a , y<=b). An area of a triangle is given namely A. Now we have to find how many such triangles with all vertices (both x and y cordinates po...
- Sun Jun 01, 2008 9:59 pm
- Forum: Algorithms
- Topic: Base conversion
- Replies: 1
- Views: 1079
Base conversion
hi, is there any algorithm that converts from base b1 to base b2 without converting to base 10 in intermediate stages. I'm asking this because if i give a number like this 1000 0000 0000 0000 0000 ....( 1 follwed by 67 0s > 2^64) , now in base 16 it is 8000..( 8 followed by 16 0s ) . If i had conver...
- Sun May 11, 2008 11:08 am
- Forum: Algorithms
- Topic: simplex algorithm
- Replies: 0
- Views: 1258
simplex algorithm
I tried implementing simplex algorithm, Does anyone see any problems with it. I've tried to use floating point comparision at possible places. This doesn't do degenerate cases. Can anyone give me test cases for 10498 ? i always get WA. My algo goes something like this 1) Form a tableau for simplex 2...
- Sat May 03, 2008 9:57 pm
- Forum: Volume 104 (10400-10499)
- Topic: 10498 - Happiness
- Replies: 18
- Views: 10071
Re: 10498 - Happiness!
In the example given at http://acm.uva.es/p/v104/10498.html 3 3 1 0.67 1.67 1 2 1 430 3 0 2 460 1 4 0 420 do the linear equations turn out to be a11 + 2*a12+a13 < 430 3*a21 + 0*a22 + a23*2 < 460 a31 + 4*a32 + 0*a33 < 420 maxmimze a11+a21+a31 + (a12+a22+a32)*0.67 + 1.67*(a13+a23+a13) or a + 2*b +c <...
- Tue Apr 22, 2008 4:17 pm
- Forum: Algorithms
- Topic: chicken soup problem
- Replies: 8
- Views: 2101
Re: chicken soup problem
thanks mf
found that using intermediates in profit function got it to accepted + using your way. This certainly looks like floating point issue on the judge.
found that using intermediates in profit function got it to accepted + using your way. This certainly looks like floating point issue on the judge.
- Mon Apr 21, 2008 7:48 pm
- Forum: Algorithms
- Topic: chicken soup problem
- Replies: 8
- Views: 2101
Re: chicken soup problem
/* ID=4725 CODE=TAFO PROB=111 LANG=C++ */ /* mail this to judge@rabbit.eng.miami.edu and you will get a reply saying accepted or rejected */ #include<cstdio> #include<cassert> #include<cmath> #include<algorithm> using namespace std; #define MYEPS (1e-05) double fa, ma, fb, mb, ffmax, mmax, pf, pm, ...
- Mon Apr 21, 2008 4:15 pm
- Forum: Algorithms
- Topic: chicken soup problem
- Replies: 8
- Views: 2101
Re: chicken soup problem
#include<cstdio> #include<cassert> #include<cmath> #include<algorithm> using namespace std; #define MYEPS (1e-10) double fa, ma, fb, mb, ffmax, mmax, pf, pm, amin, bmin, pa, pb, qf, qm; /* is the minimum acheivable */ inline bool ispossiblemin(void) { if (amin * fa + bmin * fb > ffmax) return false...
- Mon Apr 21, 2008 9:57 am
- Forum: Algorithms
- Topic: chicken soup problem
- Replies: 8
- Views: 2101
Re: chicken soup problem
Linear programming with few variables and constraints isn't hard at all. In 2D it just reduces to computing line intersections, which is quite elementary. x*fa + y*fb <= leftF x*ma + y*mb <= leftM x>=0,y>=0 maximize f(x,y) Define four lines: 1) x*fa + y*fb = leftF 2) x*ma + y*mb = leftM 3) x=0 4) y...
- Sun Apr 20, 2008 6:47 pm
- Forum: Algorithms
- Topic: chicken soup problem
- Replies: 8
- Views: 2101
chicken soup problem
hi, i think this problem is about linear programming but few claim to have it solved using elementary math. I fail to get the insight. Can someone give me hints for this. http://rabbit.eng.miami.edu/judge/p111.html -------------- My approach was leftF=Fmax - amin*fa -bmin*fb leftM=Mmax -amin*ma -bmi...
- Mon Apr 14, 2008 7:34 pm
- Forum: Algorithms
- Topic: domino(2x1) tiling of rectangle mxn (mn even)
- Replies: 1
- Views: 1776
domino(2x1) tiling of rectangle mxn (mn even)
hi, Can anyone point out to me domino tiling of rectangle mxn (m*n is even) using backtracking ? The problem i'm facing is each tiling counting multiple tiles ie in 2x2 , i fill a horizontal in 0,0 <> and horizontal in 1,0 <> {count 1} now it also counts horizontal in 1,0 <> horizontal in 0,0 <> /* ...