Author |
Topic |
rockmoose
SQL Natt Alfen
3279 Posts |
Posted - 2007-04-09 : 20:26:10
|
They are having an open contest at Sphere Online Judge:http://www.spoj.pl/ZFUN07If someone wants to wet their algorithmic and programming skills it might just be the place and opportunity.Perhaps we could even venture a joint team effort in trying to solve some the problems at that contest.rockmoose |
|
SwePeso
Patron Saint of Lost Yaks
30421 Posts |
Posted - 2007-04-09 : 20:31:25
|
Do you think T-SQL is a valid choice?Peter LarssonHelsingborg, Sweden |
 |
|
rockmoose
SQL Natt Alfen
3279 Posts |
Posted - 2007-04-09 : 20:45:47
|
Alas no (it is not a supported language at spoj).But just coming up with a sql solution is challenging in itself (a set-based solution, or stretching TSQL to it's limits)It's for fun and learning :)rockmoose |
 |
|
harsh_athalye
Master Smack Fu Yak Hacker
5581 Posts |
Posted - 2007-04-10 : 02:01:18
|
Anybody able to open the problems pdf file?Harsh AthalyeIndia."The IMPOSSIBLE is often UNTRIED" |
 |
|
SwePeso
Patron Saint of Lost Yaks
30421 Posts |
Posted - 2007-04-10 : 02:04:10
|
Both PS and PDF are zero bytes.Peter LarssonHelsingborg, Sweden |
 |
|
SwePeso
Patron Saint of Lost Yaks
30421 Posts |
Posted - 2007-04-10 : 02:08:32
|
quote: Open Contest 2007 consists of 10 problems. Tourney will last for several days, from 15 April 2007 to 27 April 2007. Solutions for any problem can be sent for many times but not more than 256. Each solution will be executed with set of tests. Results received with your program will be processed with special Judge Program that will estimate the correctness/effectiveness of your solution. In some tasks you will receive some score for your solution. The score will be proportional to efficiency of the algorithm offered by you. Score will define your place in rating table for given problem. Only the best solution of each participant for given problem will be considered at rating tables. Current results and the information about all sent solutions will be automatically generated by Sphere Online Judge system and will be accessible for all participants of competition.
Still some days to go...Peter LarssonHelsingborg, Sweden |
 |
|
harsh_athalye
Master Smack Fu Yak Hacker
5581 Posts |
Posted - 2007-04-10 : 02:15:33
|
BTW, till that time we can scratch our heads on archive of old classical problems![url]https://www.spoj.pl/problems/classical/[/url]Harsh AthalyeIndia."The IMPOSSIBLE is often UNTRIED" |
 |
|
SwePeso
Patron Saint of Lost Yaks
30421 Posts |
|
SwePeso
Patron Saint of Lost Yaks
30421 Posts |
|
harsh_athalye
Master Smack Fu Yak Hacker
5581 Posts |
|
rockmoose
SQL Natt Alfen
3279 Posts |
Posted - 2007-04-15 : 12:12:07
|
This is problem ID = 1423 (http://www.spoj.pl/ZFUN07/problems/main/)Digits of SQRT(2)rockmoose/*To calculate digits of sqrt(2)As many as possible in 10 secondsResults appx 1500 digits in 10 seconds, appx 5000 digits in 2 minutes. 2.4GHz PCProblem from: Algorithm references:http://www.nist.gov/dads/HTML/squareRoot.htmlhttp://antwrp.gsfc.nasa.gov/htmltest/gifcity/sqrt2.1mil*/set nocount ongo-- helper functions (2)create function mult(@n varchar(8000),@p int) returns varchar(8000) asbegin if @p = 0 return '0'; if @p = 1 return @n declare @i int ,@res varchar(8000) ,@rem int ,@m int select @i = len(@n) ,@res = '' ,@rem = 0 while @i > 0 select @m = @rem + @p*substring(@n,@i,1) ,@res = ltrim(@m%10) + @res ,@rem = @m/10, @i = @i - 1 return case when @rem = 0 then '' else ltrim(@rem) end + @resendgocreate function sub(@n1 varchar(8000),@n2 varchar(8000)) returns varchar(8000) asbegin declare @i int, @j int, @res varchar(8000), @rem int, @m int select @i = len(@n1), @j = len(@n2), @res = '', @rem = 0 --if @i < @j or (@n1 < @n2 and @i = @j) return '-' + dbo.sub(@n2,@n1) while @i > 0 select @m = 10+cast(substring(@n1,@i,1) as int)-cast(substring(@n2,@j,1) as int)+@rem ,@res = ltrim(@m%10) + @res ,@rem = @m/10-1, @i = @i - 1, @j = @j - 1 return substring(@res,patindex('%[^0]%',@res),8000)endgodeclare @s int; set @s = 10 -- seconds to run-- start calc of sqrt(2)declare @i datetime; set @i = dateadd(second,@s,getdate())declare @res varchar(8000) ,@rem varchar(8000) ,@c varchar(8000) ,@try int ,@tst varchar(8000) ,@lenres intselect @res = '1414' ,@rem = '60400' ,@lenres = len(@res) while getdate() <= @ibegin set @try = case len(@rem)-@lenres when 0 then 0 when 1 then cast(left(@rem,5) as int) / 28280 else cast(left(@rem,5) as int) / 2828 end tst: set @tst = dbo.mult(dbo.mult(@res,2)+ltrim(@try),@try) if len(@tst)>len(@rem) or (len(@tst)=len(@rem) and @tst>@rem) begin set @try = @try-1 goto tst end select @rem = dbo.sub(@rem,@tst)+'00', @res = @res + ltrim(@try), @lenres = @lenres + 1endselect @res as sq2 into #sq2select len(sq2) as digits from #sq2select sq2 from #sq2godrop table #sq2godrop function mult,subgo |
 |
|
SwePeso
Patron Saint of Lost Yaks
30421 Posts |
Posted - 2007-04-15 : 17:06:43
|
 quote: Just thirty-nine decimal places would be enough to compute the circumference of a circle surrounding the known universe to within the ra dius of a hydrogen atom.
http://www.math.rutgers.edu/~cherlin/History/Papers2000/wilson.htmlPeter LarssonHelsingborg, Sweden |
 |
|
SwePeso
Patron Saint of Lost Yaks
30421 Posts |
Posted - 2007-04-15 : 17:24:55
|
Is this challenge for real?http://www.spoj.pl/ZFUN07/problems/NGM/-- Set up initializationDECLARE @Number INTSET @Number = 14-- Show the expected outputIF @Number < 1 OR @Number > 2000000000 OR @Number IS NULL SELECT NULLELSE IF @Number % 10 = 0 SELECT 2 ELSE SELECT 1 UNION ALL SELECT @Number % 10 Peter LarssonHelsingborg, Sweden |
 |
|
rockmoose
SQL Natt Alfen
3279 Posts |
Posted - 2007-04-15 : 22:52:31
|
quote: Originally posted by Peso Is this challenge for real?http://www.spoj.pl/ZFUN07/problems/NGM/-- Set up initializationDECLARE @Number INTSET @Number = 14-- Show the expected outputIF @Number < 1 OR @Number > 2000000000 OR @Number IS NULL SELECT NULLELSE IF @Number % 10 = 0 SELECT 2 ELSE SELECT 1 UNION ALL SELECT @Number % 10 Peter LarssonHelsingborg, Sweden
Hmm, yes, that was easy At least now that I saw the solution, I barely understood the problem first. Until I realized that they meant a 1 digit number!You mean the number crunching effort for sqrt of two is overkill for most real world applications ?!! rockmoose |
 |
|
rockmoose
SQL Natt Alfen
3279 Posts |
Posted - 2007-04-15 : 23:01:00
|
Here is another one: (Problem : http://www.spoj.pl/ZFUN07/problems/GEOM/)The geometry problem, it is not very well suited for SQL, and the solution is partial.It just reduces the problem to a set of trivial linear equations.I still haven't found any Gaussian Elimination algorithms in TSQL , maybe time to write one.../*Problem : http://www.spoj.pl/ZFUN07/problems/GEOM/*/declare @dx int ,@dy int ,@side numeric(9,2) ,@px int ,@py intselect @dx = 10 ,@dy = 10 ,@side = 20 ,@px = 5 ,@py = 12create table #v(v varchar(8) primary key, x numeric(9,2), y numeric(9,2))-- vectors from each corner to given point P in the squareinsert #v(v,x,y)select 'A->P', @px-(@dx-@side/2), @py-(@dy-@side/2)union allselect 'B->P', @px-(@dx-@side/2), @py-(@dy+@side/2)union allselect 'C->P', @px-(@dx+@side/2), @py-(@dy+@side/2)union allselect 'D->P', @px-(@dx+@side/2), @py-(@dy-@side/2)-- p'' is the hypothetical point where the lines will meet-- the line drawn through vertex A : AP'' is perpendicular to line BP-- using the fact that two vectors are perpendicular, if their dotproduct is 0, (EDIT: not cross!)-- we create a set of linear equationsselect linearEquationToSolve = ltrim(#v.x)+'*(@x-'+ltrim(u.x)+') + ' + ltrim(#v.y)+'*(@y-'+ltrim(u.y)+') = 0'from #v cross join ( select 'A->P''' v, (@dx-@side/2) x, (@dy-@side/2) y union all select 'B->P''', (@dx-@side/2), (@dy+@side/2) union all select 'C->P''', (@dx+@side/2), (@dy+@side/2) union all select 'D->P''', (@dx+@side/2), (@dy-@side/2) ) uwhere (u.v = 'A->P''' and #v.v = 'B->P') or (u.v = 'B->P''' and #v.v = 'C->P') or (u.v = 'C->P''' and #v.v = 'D->P') or (u.v = 'D->P''' and #v.v = 'A->P')drop table #v======================================================================================linearEquationToSolve -----------------------------------------------5.00*(@x-20.000000) + 12.00*(@y-0.000000) = 05.00*(@x-0.000000) + -8.00*(@y-0.000000) = 0-15.00*(@x-0.000000) + -8.00*(@y-20.000000) = 0-15.00*(@x-20.000000) + 12.00*(@y-20.000000) = 0/* testdeclare @x int, @y int; select @x=8,@y=5select5.00*(@x-20.000000) + 12.00*(@y-0.000000),5.00*(@x-0.000000) + -8.00*(@y-0.000000),-15.00*(@x-0.000000) + -8.00*(@y-20.000000) ,-15.00*(@x-20.000000) + 12.00*(@y-20.000000)*/ rockmoose |
 |
|
jezemine
Master Smack Fu Yak Hacker
2886 Posts |
Posted - 2007-04-15 : 23:09:09
|
quote: Originally posted by Peso
 quote: Just thirty-nine decimal places would be enough to compute the circumference of a circle surrounding the known universe to within the radius of a hydrogen atom.
http://www.math.rutgers.edu/~cherlin/History/Papers2000/wilson.htmlPeter LarssonHelsingborg, Sweden
I didn't believe this at first so had to work it out. sure enough, it's true! radius of observable universe is about 10^40 angstroms. www.elsasoft.org |
 |
|
Michael Valentine Jones
Yak DBA Kernel (pronounced Colonel)
7020 Posts |
|
jezemine
Master Smack Fu Yak Hacker
2886 Posts |
Posted - 2007-04-16 : 00:28:47
|
quote: Originally posted by Michael Valentine JonesI hate when these topics deteriorate into discussions of theoretical physics.
I will not be dissuaded. to get it accurate to the planck length (10^-35 m) you only need 25 more digits. cake!pretty crazy that between a hydrogen atom (pretty small already!) and the planck length there are 25 orders of magnitude. if the planck length was 1 meter, a hydrogen atom would be 1 billion light years in diameter! far, far, bigger than any galaxy or galaxy cluster. strings are pretty small i guess. no wonder we'll never know if they even exist...to bring things full circle, pi itself comes into the definition of the planck length (via hbar). but you can forget about every being able to measure the planck length or any other physical constant to that kind of accuracy. I think the most accurate measurement of any physical constant is only good to 1 part in 10^9 or so. www.elsasoft.org |
 |
|
Michael Valentine Jones
Yak DBA Kernel (pronounced Colonel)
7020 Posts |
Posted - 2007-04-16 : 00:42:12
|
Can't we just once have a discussion about beer or sex that doesn't deteriorate into a discussion of theoretical physics?CODO ERGO SUM |
 |
|
jezemine
Master Smack Fu Yak Hacker
2886 Posts |
Posted - 2007-04-16 : 01:07:17
|
deteriorate? I think you mean elevate! www.elsasoft.org |
 |
|
|