## Search found 105 matches

Sun Aug 24, 2008 8:02 pm
Forum: Volume 114 (11400-11499)
Topic: 11476 - Factorizing Large Integers
Replies: 17
Views: 8049

### 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: 8049

### 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: 1534

### 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: 1534

### 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: 1534

### 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: 1534

### 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: 953

### 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: 1132

### 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: 9501

### 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: 1828

### 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.
Mon Apr 21, 2008 7:48 pm
Forum: Algorithms
Topic: chicken soup problem
Replies: 8
Views: 1828

### 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: 1828

### 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: 1828

### 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: 1828

### 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: 1581

### 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 <> /* ...