OJ Board

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...

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 ...

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...

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...

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...

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...

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...

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...

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 <...

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.

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

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

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...

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...

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