Programming C, C++, Java, PHP, Ruby, Turing, VB
Computer Science Canada 
Programming C, C++, Java, PHP, Ruby, Turing, VB  

Username:   Password: 
 RegisterRegister   
 Project Euler...
Index -> Contests
Goto page Previous  1, 2, 3 ... 9, 10, 11, 12  Next
View previous topic Printable versionDownload TopicSubscribe to this topicPrivate MessagesRefresh page View next topic
Author Message
A.J




PostPosted: Sat Jun 27, 2009 11:53 pm   Post subject: RE:Project Euler...

hmm...500 choose 3 is just under 21,000,000...not too bad...

Anyways, I am going to try implementing something I had in mind....

Oh yeah, coding in California...it has a ring to it =)
Sponsor
Sponsor
Sponsor
sponsor
Shah-Cuber




PostPosted: Sun Jun 28, 2009 12:45 pm   Post subject: Re: Project Euler...

After a day or so of tweaking with #247 (Squares under a hyperbola), I first used brute force but it somehow overflowed integers O_O which was weird enough, then i thought of using priority queues to enumerate the squares as they come from the end of the queue, and before you know it, it was solved (~10 sec), which may seem slow, but for me (being the nOOb that i am), it was one of my rather faster solutions. It's basically just checking if the number is the square that satisfies the concept, which is finding the largest n for which the index of Sn(not tin) is (3,3) ... Recursion or BFS might have worked too, but this is challenging your undersatanding of data structures, i.e Priority Queue is the best way to go Smile

Regarding #252, Divide & Conquer seems the way to go ...
A.J




PostPosted: Sun Jun 28, 2009 6:33 pm   Post subject: RE:Project Euler...

I used prirority queues too for #247 (which ran in about 2 - 3s...).

I am almost done #252. I am triangulating the points and trying to construct convex holes by matching triangles that share a common edge and making sure that the interior angles of this new shapes are all <= 180 (and using matrices to calculate the area of these triangles given its points as coordinates....also known as 'Up-and-Down Products')
Shah-Cuber




PostPosted: Tue Jun 30, 2009 12:12 pm   Post subject: Re: Project Euler...

HAHA, #244 was fun, i always love problems that involve minimal path techniques. I used BFS, storing the minimum distances from the initial position, then backtracking to find all paths (backtracking is useful Very Happy), however i was surprised that there was only one shortest path, very fun problem nonetheless, i recommend this problem for those who love slider puzzles.
A.J




PostPosted: Tue Jun 30, 2009 12:37 pm   Post subject: RE:Project Euler...

er...there's is more than one shortest path...

I used BFS to get the minimum # of moves. Then I DFSID'd to get all other minimum paths, and I just added the checksums (since I stored all the paths while DFSID'ing).

Shah-Cuber, do you mind me looking at your code? I am curious to see how you coded it out.

Btw, when did you finish #244? How long did it take you to code it?
endless




PostPosted: Tue Jun 30, 2009 2:23 pm   Post subject: Re: Project Euler...

anyone else feel like this since starting project euler? i know i do.
Posted Image, might have been reduced in size. Click Image to view fullscreen.
bbi5291




PostPosted: Tue Jun 30, 2009 3:40 pm   Post subject: Re: Project Euler...

Source: xkcd

I avoid the problem by not doing Project Euler at all, but this is probably not a good solution because sooner or later I'll regret it (like when A.J. takes my spot on the IOI team next year? Razz)
A.J




PostPosted: Tue Jun 30, 2009 4:10 pm   Post subject: RE:Project Euler...

yea, I wish Brian =)

I am not too good at compsci....and to even come close to doing that is impossible...

And that xkcd comic is sort of true, I guess....
Sponsor
Sponsor
Sponsor
sponsor
darkraven




PostPosted: Tue Jun 30, 2009 11:10 pm   Post subject: Re: Project Euler...

Passed #251
my program run 24 seconds
A.J




PostPosted: Wed Jul 01, 2009 12:00 am   Post subject: RE:Project Euler...

nice =), good job

how did you finally solve it?
darkraven




PostPosted: Wed Jul 01, 2009 2:10 am   Post subject: Re: Project Euler...

it's hard to explain.
Spoiler:

a=3i-1,
b=i,
c=8i-3,
because a+b+c<=1000
so there is 83 solutions fit this pattern.
then ,let
a=54i-37
b=18i-12
c=144i-99,
b is divisible by 2 ,& c is divisible by 9,
so let b'=b/2*3=27i-18,c'=c/9*4=64i-44
,there is 7 solutions fit this pattern.
& so on.......
darkraven




PostPosted: Wed Jul 01, 2009 4:56 am   Post subject: Re: Project Euler...

solve #252 using a dynamic programming method
Shah-Cuber




PostPosted: Wed Jul 01, 2009 11:32 am   Post subject: Re: Project Euler...

Heh, same thing, got #252 via DP, did it in like 3 hours or so, runs in 3.456 sec...

@A.J: I'm not sure i can just share code with you here, i'll probably post it on Project Euler forum if you want ... and it took me all of Monday to program it ... It's been really hectic and boring the past several days ... ahhhg, tired, should get some sleep >_>
Shah-Cuber




PostPosted: Wed Jul 01, 2009 11:50 am   Post subject: Re: Project Euler...

@darkraven: What is your user name on Project Euler & approximately how many problems have you solved so far?
A.J




PostPosted: Wed Jul 01, 2009 11:52 am   Post subject: RE:Project Euler...

no, Shah-Cuber, just pm me your solutions to #251 and #252 (dont worry, I got #252 yesterday).

Did you guys notice that CrappyToilet also solved #252...using a java applet? For once he didn't cheat Laughing

EDIT: Just one more to 100% =)
Display posts from previous:   
   Index -> Contests
View previous topic Tell A FriendPrintable versionDownload TopicSubscribe to this topicPrivate MessagesRefresh page View next topic

Page 10 of 12  [ 176 Posts ]
Goto page Previous  1, 2, 3 ... 9, 10, 11, 12  Next
Jump to:   


Style:  
Search: