Search found 105 matches

by temper_3243
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...
by temper_3243
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 ...
by temper_3243
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...
by temper_3243
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...
by temper_3243
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...
by temper_3243
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...
by temper_3243
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...
by temper_3243
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...
by temper_3243
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 <...
by temper_3243
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.
by temper_3243
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, ...
by temper_3243
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...
by temper_3243
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...
by temper_3243
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...
by temper_3243
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 <> /* ...

Go to advanced search