That looks fun! I'm on question two now
Computer Science Canada Project Euler... |
| Author: | A.J [ Sun May 31, 2009 12:52 am ] |
| Post subject: | Project Euler... |
I have 2 HUGE summatives due in 2 days...what a time to get hooked on project euler... I wanted to inquire about the latest question on there : http://projecteuler.net/index.php?section=problems&id=247 I have only got 154 problems solved, but I am trying to increase my 'performance' (i.e. the # of questions solved in the last 25 problems, Currently, it is 15/25). This particular question is very interesting. I have a couple of ideas on how to start, but not anything elegant yet. Anyone have any thoughts about this problem? |
|
| Author: | DtY [ Sun May 31, 2009 2:55 am ] |
| Post subject: | RE:Project Euler... |
That looks fun! I'm on question two now |
|
| Author: | A.J [ Sun May 31, 2009 10:42 am ] |
| Post subject: | RE:Project Euler... |
@DtY - nice! but a small warning, these questions are addicting 
k, I might have a bruteforce solution for #247, but it reall won't finish <1min...hmm, maybe I should integrate  ... |
|
| Author: | Cyril [ Sun May 31, 2009 2:55 pm ] | ||||||
| Post subject: | Re: Project Euler... | ||||||
Ah, got it in an hour. Runs in about 1 second. Nice problem! Hopefully this doesn't give anything away: 1.
2.
3.
|
|||||||
| Author: | DtY [ Sun May 31, 2009 3:59 pm ] |
| Post subject: | Re: Project Euler... |
Hmm.. I'm having trouble with question ten.. If I run it with ten, it gets seventeen as the question says it should, but using 2'000'000, the answer it gives me is wrong 
Without posting my source, can someone give me vague hints as to why it might not be working? I'll attach the output The beginning is unimportant, it's just to let me know how much is left then => marks the answer, then after that all the prime numbers it found. [edit] Oops, I guess it didn't like my extensionless filename |
|
| Author: | A.J [ Sun May 31, 2009 4:07 pm ] |
| Post subject: | RE:Project Euler... |
@DtY - The hardest part of this question is actually generating the primes below 2000000 and to store their sum (well, that's pretty much the whole question  ). For generating the primes, try looking at prime sieving (sieving primes from all the numbers from 1->2000000). There a lot of efficient sieves that can with run at astounding speeds. Now, long long should suffice in storing the sum.
As for why your program works for 10 and not 2000000, well maybe it omits some of the bigger primes? How are you generating the primes and how are you storing their sum? |
|
| Author: | DtY [ Sun May 31, 2009 4:13 pm ] | ||||
| Post subject: | RE:Project Euler... | ||||
I'm doing it in Ruby, so size doesn't matter I'm using the Sieve of Eratosthenes (the first one described) to store them in an array, then to get the sum primes.sum Sum is just a simple method I wrote:
the only thing I can think of that might be the problem is this line, is this the right number of times to iterate?
(int.sqrt is another method I wrote as an alias to Math.sqrt(int)) |
|||||
| Author: | A.J [ Sun May 31, 2009 4:23 pm ] | ||
| Post subject: | RE:Project Euler... | ||
Eratosthenes should be fast enough. For sieving, it suffices to go up till the floor(sqrt(number)). However, for the 'cancelling out the multiples of smaller primes', you have to iterate up to the number. In other words:
|
|||
| Author: | DtY [ Sun May 31, 2009 5:05 pm ] | ||
| Post subject: | RE:Project Euler... | ||
The part that actually decides which ones are good is:
Where primes[-1] is the next prime number to remove multiples of |
|||
| Author: | chili5 [ Sun May 31, 2009 7:41 pm ] |
| Post subject: | RE:Project Euler... |
I've started to get really hooked to this as well, bad time to get hooked on this, with summatives due in a week. :-s Seeing other people's solutions in the forum is really interesting.
The primes ones are really easy, and Eratosthenes is usually always fast enough. A lot of the first few questions seem to involve using the BigDecimal class in Java. |
|
| Author: | Cyril [ Sun May 31, 2009 7:42 pm ] |
| Post subject: | RE:Project Euler... |
I find that it's convenient to write a quick program to write a bunch of primes to a file. When you come across a problem that requires primes (too often?), you can just read from the file, which is much faster than generating them every time. |
|
| Author: | A.J [ Sun May 31, 2009 10:18 pm ] |
| Post subject: | RE:Project Euler... |
@DtY - I am not familiar with Ruby, so I can't help you there. @chili5 - welcome to the world of questions-that-drive-you-mad 
@Cyril - well, generating the primes only takes a couple of seconds, so it isn't that bad. And besides, the new questions nowadays almost never have primes in them |
|
| Author: | chili5 [ Mon Jun 01, 2009 5:23 am ] | ||
| Post subject: | RE:Project Euler... | ||
I wonder why there isn't any more prime questions, primes are fun. I supposed all the good questions have been done already though. A.J, how many problems have you got done? Woot, I got question 5. My code (very inefficient) ran in 29 seconds.
|
|||
| Author: | A.J [ Mon Jun 01, 2009 9:49 am ] |
| Post subject: | RE:Project Euler... |
I currently have 188 solved, out of which 16 are out of the last 25. |
|
| Author: | Shah-Cuber [ Mon Jun 01, 2009 4:18 pm ] |
| Post subject: | Re: Project Euler... |
Hello CompSci
I have currently registered as a new member, and I am static about your discussion so far regarding Project Euler. I am a grade 10 student - Python program (mainly), though I also program in C++, Java, and Mathematica. Though I have registered just now, I have visited this site for a quite a long time, and know/heard many of you. Today is also a good day, because i also received my SIN (Sir Isaac Newton Physics Contest) results, which has also made me very hyper in addition to my insomnia (joking) over the past several days -_- I too enjoy doing Project Euler questions, and my username is the same there as it is here. I have learned a lot through doing such questions, and find it very beneficial if one enjoys a challenge and deep mathematical concepts. I have also recently started doing some fun SPOJ questions, and find it as addicting as Project Euler. I also recommend that if your bored as i am (usually). However, currently, i have been bombarded with loads of homework, and find little time to program anymore. Robotics is also one of my interests, and our school team (more like 5 people, who never sleep >_>) went to the world championships this year, with somewhat good results. Regarding your question on #242, though i haven't done it yet (too busy), i believe some simple recursion should do the trick. I am still working on #245 (Coresilience), and find it somewhat difficult because i am following a very stingy brute force, using sieve to calculate values of phi(n), and so far ... it is very slow and inefficient, and takes approximately 2 min just to calculate up to 10^8, any suggestion would be helpful, and hope i can help too if anyone has any questions, though Cyril is really the expert, and has helped me through some problems, and vice versa  If you have read through this whole introduction ... give yourself a pat on the back
Now back to boredom >_> |
|
| Author: | saltpro15 [ Mon Jun 01, 2009 4:46 pm ] |
| Post subject: | RE:Project Euler... |
Shah-Cuber, I'm addicted to SPOJ as well:D my user ID there is dr3w. Our school is actually forming a robotics team next year, what contests do you do?/what is it all about? |
|
| Author: | Shah-Cuber [ Mon Jun 01, 2009 5:03 pm ] |
| Post subject: | Re: Project Euler... |
saltpro15, Our school had two robotics divisions: VEX robotics & FTC robotics I was mainly in the FTC robotics (programmer/builder) along with 4 other people, 3 grade 12's and 1 grade 11, even though we started out with like 20 or so >_> (people eventually quit) For regionals we placed 2nd overall and won alliance round, and moved on to the world championships in Atlanta, where we placed 20th among 150 or so competitors world - wide. For more information about the game and the organization itself, you can visit http://www.firstroboticscanada.org/site/node/928 . Hopefully we will meet you next year if your doing FTC or VEX, though we had numerous difficulties, it proved to be a very fun and educational experience ... though I have grown a hatred towards RobotC >_> Good Luck ! |
|
| Author: | A.J [ Mon Jun 01, 2009 5:49 pm ] |
| Post subject: | RE:Project Euler... |
@ Shah-Cuber - Here's you official welcome to compsci.ca: Welcome to compsci.ca !
Its nice to know that you are participating in project euler and SPOJ too, as they really help you in gaining more knowledge in math and CS alike. And I was talking about #247 (the last question), not #242. And as for #245, try doing #243 first, as it is a slightly easier version of #245. |
|
| Author: | Shah-Cuber [ Mon Jun 01, 2009 8:02 pm ] |
| Post subject: | Re: Project Euler... |
Thanks A.J
Sorry, I must've misread >_> @ A.J - I have also noticed that you are now 12th in Canada ! wow O__O, congratulations ! I must've been gone Project Euler for a long time >_>, well, hopefully within the next week or so (after my work is done) i will start doing some more questions |
|
| Author: | A.J [ Mon Jun 01, 2009 9:35 pm ] |
| Post subject: | RE:Project Euler... |
thanks, I have been working my ass of on them for the last month or two (pardon my language). |
|
| Author: | A.J [ Wed Jun 03, 2009 8:16 pm ] |
| Post subject: | RE:Project Euler... |
Ok, I solved the question. I used priority queues, as I found that the enumerating the squares got a lot faster. The runtime was about 3.976 seconds, which isn't that bad, but certainly could be faster. Ok, right now I have 199 solved. I must try catching to people like Shah-Cuber and Cyril by the end of summer. I am going to the Canada/USA MathCamp, so I'll try coding there. I am going to train a lot this summer on SPOJ, Project Euler, random Olympiads, etc...as I want to try making it to IOI next year. Some of my friends who are reading this post might actually be surprised, since being emo I never want to achieve anything in my life, but this is the reason why: the probability that IOI will EVER take place in the city that you live in out of ALL THE OTHER places in this WORLD while you are in grade 12 (i.e. in you programming peak) is actually very VERY VERY slim. So, I am preparing. |
|
| Author: | Shah-Cuber [ Wed Jun 03, 2009 8:53 pm ] |
| Post subject: | Re: Project Euler... |
Congratulations
1 more till level 5!!! .. than you will see your progress slow down >_> |
|
| Author: | A.J [ Wed Jun 03, 2009 11:41 pm ] |
| Post subject: | RE:Project Euler... |
Yeah, I know...but I didn't finish some of the extremely trivial ones, so I might finish them and then maybe get stuck for a long while |
|
| Author: | A.J [ Fri Jun 05, 2009 7:47 pm ] |
| Post subject: | RE:Project Euler... |
# 248 is out! Ok, this seems easy, but...the numbers get annoying. I am trying to be the top ten to finish it |
|
| Author: | Cyril [ Sat Jun 06, 2009 12:30 am ] |
| Post subject: | RE:Project Euler... |
Wow, A.J. ...your progress is astounding. I don't think 248 is as easy as it seems. It seems like the approach is something like the one for 221- reduce it to a factoring problem in a specific way such that you generate the numbers in order. |
|
| Author: | A.J [ Sat Jun 06, 2009 10:35 am ] |
| Post subject: | RE:Project Euler... |
Thanks Cyril. I realised that I didn't finish a lot of the easier problems, so I managed to finish them. Now, however, I won't be going anywhere...except for maybe trying to solve #248
PS: damn it, while I was sleeping, there already has been 26 people to have solved #248....oh well, so much for top ten  |
|
| Author: | A.J [ Sat Jun 06, 2009 2:24 pm ] |
| Post subject: | RE:Project Euler... |
ok, since I haven't been paying attention to school that much, because I was doing project euler practically 24/7, my mom sort of banned me from doing project euler for a while...I can spend time on it, but only for a small limited amount of time.... EDIT: Yes. I managed to finish #210 (Obtuse Angled Triangles) when my mom wasn't home . Tied for 5th. |
|
| Author: | saltpro15 [ Sat Jun 06, 2009 8:08 pm ] |
| Post subject: | RE:Project Euler... |
I think A.J. may have an addictive personality :p stay away from rubik's cubes! and fallout 3, really addictive... anyways, enough off topic! time to start some project euler |
|
| Author: | A.J [ Sat Jun 06, 2009 8:27 pm ] |
| Post subject: | RE:Project Euler... |
what do you mean by addictive personality? cause I am certainly not addictive... |
|
| Author: | Shah-Cuber [ Sat Jun 06, 2009 8:37 pm ] |
| Post subject: | Re: Project Euler... |
Finishing my homework, I got bored, and noticing i'm falling behind in my Eulering, decided to do #228 (Minkowski Sums), very simple O(n) algorithm, and soon i will get catch up to you guys again (I hope). Now i'm gonna look at #222(Sphere Packing) ... hope to finish it before midnight if i can. A.J, your progress is truly astounding. Good Luck to you too saltpro15
I am proud that i have gotten one after such a long time >_> |
|
| Author: | A.J [ Sat Jun 06, 2009 11:06 pm ] |
| Post subject: | RE:Project Euler... |
Nice Shah-Cuber! |
|
| Author: | Shah-Cuber [ Sat Jun 06, 2009 11:10 pm ] |
| Post subject: | Re: Project Euler... |
Thanks Just got #222 with brute force, i know, i didn't see the pattern, but it was a horrible run time. One of my worst last minute-programming before midnight ever ... |
|
| Author: | A.J [ Sat Jun 06, 2009 11:18 pm ] |
| Post subject: | RE:Project Euler... |
I just finished #201. I found a very elegant solution to it (well, it isn't elegant, just that it is cool )
Congrats Shah-Cuber . I used Haskell to do #222. My program ran in <1s...but mind you, it took me a while to code it in Haskell (as I am new to Haskell... ) |
|
| Author: | Shah-Cuber [ Sun Jun 07, 2009 8:38 pm ] |
| Post subject: | Re: Project Euler... |
According to Project Euler status' so far, the competition is pretty fierce and close. As of 9:32 pm June 7th 2009, the rankings between Cyril, A.J, & I are: 1st: Cyril (225) 2nd: A.J & Shah-Cuber (224) I hope you realize that this is not easy (took an entire day to get approximately 10 problems), and congratulations on everyone's progress so far. As you can see the race is pretty close, and i hope you do not see this as a competition, if it looks that way. The standings on current performance, based on the 25 most recent problems are: 1st: A.J (17) 2nd: Shah-Cuber (16) 3rd: Cyril (13) Happy Eulering |
|
| Author: | A.J [ Sun Jun 07, 2009 8:44 pm ] |
| Post subject: | RE:Project Euler... |
WOW, Shah-Cuber, your progress is AMAZINGLY FAST!!! 10 problems in one day! Wow! I only finished like 3 today! Congratulations! |
|
| Author: | Analysis Mode [ Sun Jun 07, 2009 10:05 pm ] |
| Post subject: | Re: Project Euler... |
SPOJ for the win! |
|
| Author: | Horus [ Sun Jun 07, 2009 10:37 pm ] |
| Post subject: | RE:Project Euler... |
wow... I've known this site last summer, and did a bit of the questions before school started. i've only managed to do the first 9 questions on project euler (3 questions with pencil/paper, 6 questions with turing) and for the Find the 10001st prime, it took my program 30 minutes to find the answer (I used a 1Ghz 256MB RAM computer) I couldn't even understand most of the questions at the back not to mention doing it... I expected people who were on the top of the ranking to be university professors, not grade 10 students, you guys are really amazing. |
|
| Author: | A.J [ Mon Jun 08, 2009 6:28 am ] |
| Post subject: | Re: Project Euler... |
oh yeah, 3rd place  |
|
| Author: | bbi5291 [ Mon Jun 08, 2009 9:26 am ] |
| Post subject: | Re: Project Euler... |
A. J. and Shah-Cuber, how good are you at math? I assumed that one needs to be extremely good at math to solve so many Project Euler problems (notice how Jonathan Schneider is still first in Canada), so I kinda gave up on it after a while... |
|
| Author: | A.J [ Mon Jun 08, 2009 10:29 am ] |
| Post subject: | RE:Project Euler... |
Hey Brian. I am pretty sure that if you were still doing Project Euler, you would be way past me. I am pretty bad at math...so yeah, you don't really need amazing math skills for PE. (Notice how you didn't ask Cyril how good he is in math...see Cyril, you ARE good in math, and don't be telling me otherwise...we are all turning emo...weeeeeeeeeeeeee) |
|
| Author: | bbi5291 [ Mon Jun 08, 2009 11:59 am ] |
| Post subject: | Re: Project Euler... |
Pretty bad? Are you sure? hmm, did you write the CMO? (Anybody who writes the CMO is at least as good as I am at math...) And yeah, I didn't ask Cyril because I already had a good idea of how good he is at math, having met him at stage 2... |
|
| Author: | Alexmula [ Mon Jun 08, 2009 12:03 pm ] |
| Post subject: | RE:Project Euler... |
how can you guys do so many problems I have only done 45 and im pretty much stuck  amazing gr 10s |
|
| Author: | Shah-Cuber [ Mon Jun 08, 2009 3:06 pm ] |
| Post subject: | Re: Project Euler... |
@bbi5291: Regarding myself, i am mostly a physics student. Having written the SIN(Sir Isaac Newton) physics contest this year, i did quite well, though nobody got perfect, it is quite challenging. When doing Project Euler questions, you begin to learn new aspects of mathematics and programming concepts, which will prepare you for more challenging problems. I guess what i'm saying is that you learn while doing more challenging questions in Project Euler. I have no doubt that both A.J and Cyril are better at math than i am, i consider myself more of a moderate mathematician. Not pro, like you guys. Thereby you don't have to be "extremely" good at math to solve so many Project Euler problems, as many of them are repetitions of the same concept of programming/mathematics. @A.J, your progress within these two months are very abnormal and awe inspiring, it took me approximately 6 months to get where i am now. Not only have you surpassed me, but evidently Cyril, which i sometimes considered as impossible (not including Jonathan Schneider), so congratulations, but i bet Cyril is too busy at the moment to do any questions. I also believe, that if Brian did these questions, none of us would have any doubt that you would be #1 in Canada right now. I recommend you try some of these questions more in depth, to get the sense of what i'm trying to explain. Also, congatulations on your CCC stage 2 results, very impressive, and good luck at IOI |
|
| Author: | Shah-Cuber [ Mon Jun 08, 2009 4:05 pm ] |
| Post subject: | Re: Project Euler... |
oh yeah, 3rd place
Got #210(Obtuse Angled Triangles) just when i got home (got some ideas from my friends at school), got it by counting the lattice points in a circle using only integer arithmetics, and i tried optimizing my algorithm, but it did not improve the time much ... Quite easy if you think about it. Wohoo, i'm tied with A.J  |
|
| Author: | Cyril [ Mon Jun 08, 2009 4:55 pm ] |
| Post subject: | RE:Project Euler... |
Oh damn. Owned by you two. I suppose I'll finish up 237 and leave it at that for now- have a French summative to do. You two should look at 219- there's a nice logtime solution, but you have to make a few weird observations. I think Project Euler is more of a test of pure problem solving skills, rather than math or programming. Of course, those are your basic tools, but most of the problems are very easy mathematically and "programmatically" after you explore the nature of the problem and find some crucial properties. I am not a "pro" mathematician, as Shahriar claims- actually, my math is pretty weak. And sometimes I wonder if Jon reads/cares about all of this gossip about him. I suppose he's used to it... Oh yeah- Brian, did you make IChO? |
|
| Author: | bbi5291 [ Mon Jun 08, 2009 6:21 pm ] |
| Post subject: | Re: Project Euler... |
No, I did not make IChO. The primary reason for this is my lack of lab experience - the lab is worth 40% (and the theory 60%). Two of the team members are from private schools, with their abundant resources, and one is from Quebec and enrolled in C?gep... I was at a disadvantage because the labs at my school are absolutely awful, and I had no experience with the experimental techniques. (I gotta admit, Woburn will have almost nothing left after the inevitable decline in computer science in the near future ;-( ) There's always next year, but I think I will have to give up my dream of going to MIT. (Actually, I can probably still make it to MIT if I do lots of volunteer work in the coming year... but then probably no IOI gold ) |
|
| Author: | A.J [ Mon Jun 08, 2009 7:05 pm ] |
| Post subject: | RE:Project Euler... |
...you'll make MIT brian...I am trying for MIT, and I have no chance (they require a really high SAT score, and I have yet to write the SAT's...and I currently have 0 volunteer hours) |
|
| Author: | saltpro15 [ Mon Jun 08, 2009 8:41 pm ] |
| Post subject: | RE:Project Euler... |
well good luck to both of you |
|
| Author: | bbi5291 [ Mon Jun 08, 2009 9:15 pm ] |
| Post subject: | Re: Project Euler... |
A. J., did I mention that Hanson was rejected from MIT? |
|
| Author: | A.J [ Mon Jun 08, 2009 9:39 pm ] |
| Post subject: | RE:Project Euler... |
really? Wow...I have no chance for sure...cut...cut...cut.. @Cyril - btw, I finished #219 recently...you dont even need to make a program to solve this problem (so therefore, my runtime was O(0) ) |
|
| Author: | Cyril [ Mon Jun 08, 2009 9:53 pm ] |
| Post subject: | RE:Project Euler... |
Aww. The DMCI people who went to the second round with you seemed to be astounded by your skills- I thought you'd "have a seat reserved". I can see how chemistry really depends on conditions... Yes, MIT was a dream for me as well, but I think it has more or less crushed itself. Oh well. Apparently they doesn't look at your SAT essay...? And, nice- 219 is totally doable with pencil/paper, but I only realized how small the problem was after I started coding. |
|
| Author: | A.J [ Mon Jun 08, 2009 10:02 pm ] |
| Post subject: | RE:Project Euler... |
Well, I have A LOT of extracurricular activities + a bit of academic activities. I have to improve on my math + CS skills in general and try making IOI next year. If I make it, then I have a higher chance of making it to MIT too (unless MIT doesn't give a damn on whether you are on an Olympiad team or not...) |
|
| Author: | Shah-Cuber [ Mon Jun 08, 2009 10:42 pm ] |
| Post subject: | Re: Project Euler... |
Why is everyone so obsessed with entrance to MIT ? I mean, don't get me wrong, it is one of the top universities, but, realistically, i don't find it beneficial, unless everyone here is gonna major in some CS program. In fact, one of my favorite universities in America, is University of Berkeley, which has one of the best physics program. Regarding the SAT's, two of my friends took it this year for physics, and another friend for mathematics (II). Both said the practical part (i.e the actual calculations) was quite easy, and said it is very easy to get a perfect score in that section. The only challenging part, is the written section, where much of the logic (along with English) skills are required. MIT in my opinion is a over hyped university, but, never give up. You never know, just keep doing contests, maintaining a high average, participating in school events and extracurricular activities, and hopefully, you'll one day gain entrance. |
|
| Author: | Cyril [ Mon Jun 08, 2009 11:02 pm ] |
| Post subject: | Re: Project Euler... |
Shah-Cuber @ Mon Jun 08, 2009 10:42 pm wrote: unless everyone here is gonna major in some CS program.
Haha, I think you may have failed to prove your point. |
|
| Author: | Shah-Cuber [ Mon Jun 08, 2009 11:09 pm ] |
| Post subject: | Re: Project Euler... |
@Cyril: The thing is, you quit on your dream of going to MIT ... |
|
| Author: | Analysis Mode [ Mon Jun 08, 2009 11:13 pm ] |
| Post subject: | Re: Project Euler... |
@Shah-Cuber: I assume you mean University of California Berkeley. Stanford and Princeton also have very strong physics programs and are better known, just because Stanford and Princeton are names people throw around more than UC Berkeley @A.J.: A couple years back, we had a girl in PEG at our school who made it into MIT. From what I hear, she was very involved with the school, on a couple of sports teams, but wasn't nearly as good in CS. And from what bbi5291 told me once (who was told by our CS teacher), David Pritchard, who came in 2nd at the IOI one year and got into MIT, might not have made it in other years, as American universities have a different profile of an ideal student every year (i.e. Hispanic, plays squash, won the World Championships in Magic the Gathering, etc.). I think you get my point. @Cyril: They don't look at your Writing score at all. @Shah-Cuber again: MIT isn't just vaunted for its CS programs. It also has exceptional programs in engineering, physics, etc. As for beneficiality of American universities, it certainly isn't so for your bank account. Academically speaking with regards to undergraduate degrees, American universities offer a wider range of freedom in courses. Take Life Sciences at a Canadian university, for example. After you graduate from the program, your skill set will pretty much be, well, Life Sciencey. In the States, you're given more leeway to explore other options, as you don't decide on your major (called a concentration) until you're in your 3rd year. As for graduate school, American counterparts surpass their Canadian ones, due to an abundance of funding (more so, now that Obama's in office), as well as a large number of excellent faculty (Fields Medal, Nobel Prize, etc. winners). |
|
| Author: | Cyril [ Tue Jun 09, 2009 12:01 am ] |
| Post subject: | RE:Project Euler... |
Shahriar, a crushed dream satisfies the law of conservation of mass- I suppose I'll still shoot for MIT, but I don't expect to get that far. I wouldn't call it quitting. Analysis Mode, are you going for MIT as well? You Woburn gifties seem to be a lot more... ambitious. |
|
| Author: | A.J [ Tue Jun 09, 2009 12:30 am ] |
| Post subject: | RE:Project Euler... |
way to be to the point Cyril
Analysis Mode, do you do project euler? I know that you do SPOJ, but I am just asking. PE is actually quite interesting/challenging...it is taking up WAY too much of my final-exam-preparation-time... |
|
| Author: | Shah-Cuber [ Tue Jun 09, 2009 12:32 am ] |
| Post subject: | Re: Project Euler... |
@Cyril: It also satisfies the Cyril dream duality >_>, having Cyril and his dream exhibit the behaviors of both misconception and apathetic feelings. |
|
| Author: | A.J [ Tue Jun 09, 2009 12:40 am ] |
| Post subject: | Re: Project Euler... |
bbi5291 wrote: Pretty bad? Are you sure? hmm, did you write the CMO? (Anybody who writes the CMO is at least as good as I am at math...) I qualified for the CMO (I believe I got perfect on the CMOQR) but I bombed the it...I only got about 2 questions right...hopefully next year I'll get >3 questions... And Brian, I noticed that you too are writing the Waterloo Local ACM contest. Nice! |
|
| Author: | T.O [ Tue Jun 09, 2009 12:14 pm ] |
| Post subject: | RE:Project Euler... |
what is this |
|
| Author: | A.J [ Tue Jun 09, 2009 1:19 pm ] |
| Post subject: | RE:Project Euler... |
"Waterloo's ACM International Collegiate Programming Contest Team will be chosen according to the results of these contests. All UW students are welcome - come to learn, come for fun, or come to win. Detailed announcement " |
|
| Author: | bbi5291 [ Tue Jun 09, 2009 4:28 pm ] |
| Post subject: | Re: RE:Project Euler... |
Cyril @ Mon Jun 08, 2009 9:53 pm wrote: Aww. The DMCI people who went to the second round with you seemed to be astounded by your skills- I thought you'd "have a seat reserved". I can see how chemistry really depends on conditions...
Yes, MIT was a dream for me as well, but I think it has more or less crushed itself. Oh well. Apparently they doesn't look at your SAT essay...? And, nice- 219 is totally doable with pencil/paper, but I only realized how small the problem was after I started coding. Wow, I generally assume that nobody ever talks about me because I'm overshadowed by Schneider.
What I have heard is that MIT doesn't look at the writing part at all, which includes the essay. So effectively your score is out of 1600. Shah-Cuber @ Mon Jun 08, 2009 10:42 pm wrote: Why is everyone so obsessed with entrance to MIT ? I mean, don't get me wrong, it is one of the top universities, but, realistically, i don't find it beneficial, unless everyone here is gonna major in some CS program.
Well, extrapolating from others' experiences, I should have no problem getting into UW. It is definitely an excellent university and the computer science program is one of the best in the world, rivalling or surpassing that of MIT. And I don't like the USA in general, either, especially the idea of living there (I'd like to think that Obama can change something, but absolute power corrupts absolutely). However, MIT is a challenge, whereas relative to my standpoint UW is not. Also, as Analysis Mode hinted, the social climate is very different at elite American schools than it is at the most elite of Canadian schools. But even if I was somehow prevented from attending MIT, I would still like very much to be admitted. Because I see a lot of smart people doing amazing things before, during, and after their studies at MIT (Schneider is an example at least for the "before" part, and one of the mentors at the CCPO made IChO in grade 9, finished undergrad in 2 years, and is at MIT for grad school now), and I would like nothing else but to be their equal. And if I am truly their equal, MIT should accept me as well. ("MIT" may be replaced by "Stanford", "Caltech", "Princeton", whatever.) |
|
| Author: | Shah-Cuber [ Tue Jun 09, 2009 5:23 pm ] |
| Post subject: | Re: Project Euler... |
bbi5291 wrote: (I'd like to think that Obama can change something, but absolute power corrupts absolutely) Agreed ... |
|
| Author: | A.J [ Tue Jun 09, 2009 5:39 pm ] |
| Post subject: | RE:Project Euler... |
I am sorry to announce that I am officially stopping Project Euler (for about 1 month). I have to start studying for my exams (I mean REALLY start). So, I tried to go out with a bang...and failed  . I solved 5 questions today (which is nothing compared to Shah-Cuber's 10-questions-in-a-day record  ), but it does leave Cyril and Shah-Cuber a high target to reach : 236.
The questions I finished today were actually pretty trivial: #194 - some math, but then just computation #203 - .......bash #215 - cool, and a bit challenging, DP #217 - easy DP #228 - one insight needed...then becomes trivial So, it is with a heavy heart that I bid my dear friend Euler farewell... (P.S: oh who am I kidding....there are 3 questions that I will try squeezing in during exams, namely #143, #200 and #227  ) |
|
| Author: | saltpro15 [ Tue Jun 09, 2009 7:56 pm ] |
| Post subject: | RE:Project Euler... |
A.J. how do you have time to do all those? I have only solved #5 so far, as I have no free time to work on them, though I'd like to... |
|
| Author: | Shah-Cuber [ Tue Jun 09, 2009 8:08 pm ] |
| Post subject: | Re: Project Euler... |
I'm not sure how to put this ... ummm ... YOU GOT #198(Ambiguous Numbers) ?!?!?!?!?!? How ?!? Inconceivable ?!?! Impossible ?!? than again ... you are you ... haha I still believe your performance on project Euler is truly astounding, and now you are beating me by 10 questions! Considering the fact that only 2 days ago, we were tied >_> But i figured, you will never quit Eulering, simply because it is very addictive ... no one can escape .... it is inevitable ... Good luck on the exams I'm studying too ...
Hint for #227: I just created transition matrix, and solved a system of linear equation 
Good luck! hmmm ... maybe this is my chance on revenge ? #219 here i come (as Cyril recommended) |
|
| Author: | A.J [ Tue Jun 09, 2009 8:08 pm ] | ||
| Post subject: | RE:Project Euler... | ||
I don't have time to do all those...that's the point I am trying to make (shoots self in the head)....damn, there really needs to be an 'emo'ticon here
#198 isn't that hard, Shah-Cuber. Here's a hint:
It is kind of obscure, but I used The On-Line Encyclopedia of Integer Sequences to help me. And I am pretty sure that Cyril and you will be way ahead of me pretty soon...so I am not falling for that trick again |
|||
| Author: | Shah-Cuber [ Tue Jun 09, 2009 8:39 pm ] |
| Post subject: | Re: Project Euler... |
Fortunately i got #219 ... through DP though ... sorry i didn't notice the recurrence of the pattern >_> @A.J: HAHA, who doesn't use the OEIS ... thanks for the spoiler >_> |
|
| Author: | A.J [ Tue Jun 09, 2009 8:42 pm ] |
| Post subject: | RE:Project Euler... |
#219 is one of those problems that doesn't require a program. But it can also be done using a program. I used the recurrence to find the first 10 numbers in the sequence, then I tried noticing a pattern, and then extrapolate the required term from the sequence continuing this pattern. I think the DP 'step' you had is probably the same as the recurrence I found. |
|
| Author: | Analysis Mode [ Tue Jun 09, 2009 10:18 pm ] |
| Post subject: | Re: Project Euler... |
@A.J.: I don't do Project Euler. I need to get in top 10 in Canada on SPOJ and then I'll consider it. Then again, I have to study for the Canadian Biology Olympiad, practice for CCC, study for Reach, etc. over the break. SPOJ is more practical practice for CCC. Lots of good problems. @Cyril: No, I'm not aiming for MIT. I'll be going into pre-med at whatever university I attend, and MIT pre-med just doesn't appeal to me as much as other universities. And not to mention having to take Physical Education as a mandatory course. Oh, and there aren't any hot girls at MIT either, so that's another no-no (just kidding, if any of you happens to be a hot girl from MIT) To all: I would suggest you read this: http://www.theamericanscholar.org/the-disadvantages-of-an-elite-education/; It's a lengthy article by a former Yale professor about the learning environment and mentality American schools provide with their students. |
|
| Author: | A.J [ Tue Jun 09, 2009 10:27 pm ] |
| Post subject: | RE:Project Euler... |
yeah, I should really start SPOJ.....and I also have to practice for CCC (somehow) and Reach (somehow)... |
|
| Author: | Shah-Cuber [ Sun Jun 14, 2009 1:29 pm ] |
| Post subject: | Re: Project Euler... |
The post is starting to become outdated ... so i'll say some things that have been going on, on Project Euler, the past few days. First of all, congratulations to A.J for now becoming #1 in Canada in such a fast time, in such short days, while having exams and projects due. This is very impressive, and kinda scary (He is above Schneider), but i suspect his too busy at the moment to do anything. Also surprisingly, all of us (Cyril, A.J, and I), did Chess AI's for our final ISU projects ... I handed mine in friday. I used alphabeta pruning/minmax, and i believe A.J did the same, but Cyril implemented heuristics. Also, A.J's is 3D while mine and Cyril's are not, (i had basically two days to do it, so not enough time), and all of the languages used between us is different. I used Java, Cyril used VB, and A.J used C++, so i just said that, cause i thought it was interesting and awkward that all of us did Chess AI. Besides that, question #249 and #250 have been added ... possible DP, i'll work on them in the week to come ... maybe not, because i have exams coming up. Currently i'm working on #214 (Totient Chains), hopefully i'll get it by the end of today. What else ... hmm, i think thats it, anyways good luck to all! Happy Eulering |
|
| Author: | A.J [ Sun Jun 14, 2009 2:02 pm ] |
| Post subject: | RE:Project Euler... |
Thanks Cyril And btw, the 3D chess our group handed in this year, sadly, didn't include AI (I didn't have time). However, the chess game I made last year did include AI =). I am going to continue the AI at summer and I am going to add it to our current 3D chess program. |
|
| Author: | Cyril [ Tue Jun 16, 2009 3:56 am ] |
| Post subject: | RE:Project Euler... |
Gaaaaaaah. It's 4:55 am. I hear birds. I see dawn. After 2 hours of frantic debugging, I am now the 106th solver of #248. To my dismay, there were much nicer methods posted on the forum. Must... stop... |
|
| Author: | bbi5291 [ Tue Jun 16, 2009 8:00 am ] |
| Post subject: | Re: Project Euler... |
Analysis Mode @ Tue Jun 09, 2009 10:18 pm wrote: To all: I would suggest you read this: http://www.theamericanscholar.org/the-disadvantages-of-an-elite-education/;
It's a lengthy article by a former Yale professor about the learning environment and mentality American schools provide with their students. I should point out that my understanding of this article is that those students adversely affected by an elite education are usually the hoop-jumper type. I think less than 5% of all students accepted to elite American schools really fit my definition of "intellectual", and those schools are probably not the best environments for them. But for those who really are intellectuals, schools like MIT provide an encouraging social environment that is somewhat lacking from many Canadian schools, and have state-of-the-art facilities for research and that sort of thing... |
|
| Author: | Shah-Cuber [ Tue Jun 16, 2009 12:06 pm ] |
| Post subject: | Re: Project Euler... |
Easiest programming exam ever
Now only two more left ... |
|
| Author: | Shah-Cuber [ Tue Jun 16, 2009 12:12 pm ] |
| Post subject: | Re: Project Euler... |
Whoa ... just checked Project Euler statistics ... Not only is A.J #1 now (congratulations), but Cyril is catching up fast ... uhoh, well i'll start doing some questions right now, since i just came out of my exam, i'm crammed with knowledge (noob knowledge that is). Must savor the everlasting pleasure of being 1 rank away from Schneider, before Cyril takes it away >_> |
|
| Author: | Shah-Cuber [ Tue Jun 16, 2009 1:14 pm ] |
| Post subject: | Re: Project Euler... |
Yay, got #214 (Totient Chains), sieved phi values up to 40000000, then recursively calculated the size of the chains
Not bad, Now i'm attempting #245 (Coresilience) again ... though it fails after 1 < n <= 10^9, must optomize somehow ... Well, good luck to all
Probably have to study at the same time |
|
| Author: | Analysis Mode [ Tue Jun 16, 2009 2:11 pm ] |
| Post subject: | Re: Project Euler... |
You guys are lucky Jon Schneider doesn't seem to use these forums. |
|
| Author: | bbi5291 [ Tue Jun 16, 2009 3:02 pm ] |
| Post subject: | Re: Project Euler... |
Why, what do you think is here that Schneider would consider offensive? (You should know that it's very difficult to actually provoke a negative emotional response from the science/math type in any case...) |
|
| Author: | Analysis Mode [ Tue Jun 16, 2009 3:40 pm ] |
| Post subject: | Re: Project Euler... |
As in it would be a kick-start for him to get working again. |
|
| Author: | saltpro15 [ Tue Jun 16, 2009 3:54 pm ] |
| Post subject: | Re: RE:Project Euler... |
A.J @ Tue Jun 09, 2009 wrote: yeah, I should really start SPOJ.....and I also have to practice for CCC (somehow) and Reach (somehow)...
YES, the more SPOJ'ers the merrier |
|
| Author: | A.J [ Tue Jun 16, 2009 4:07 pm ] |
| Post subject: | RE:Project Euler... |
I don't mind if schneider starts. In fact, I sent him a message ASKING him to continue...I don't feel nice when I beat him knowing that he hasn't solved anything for over a month..... |
|
| Author: | A.J [ Wed Jun 17, 2009 11:44 am ] |
| Post subject: | RE:Project Euler... |
So, I have yet to solve #245/#246. Since I have exams coming up, and since I don't want to spend time on these questions, I have devised a plan. I coded a brute force solution to #245 that (according to my calculations, which is usually wrong...) will end about 5 days later, which is the day of my last exam! So, when this program finishes, I'll have done all my exams, and I can continue working on these problems. Although, if my calculations are off by +/2 days, I guess I'll just scrap this program and actually try making an efficient one... All these efforts just to make sure I don't work on these problems...that takes some serious lack of control from my part! Ok, now I am off to study for my Calculus and Chemistry exams (which, by the way, are tomorrow)! |
|
| Author: | Shah-Cuber [ Thu Jun 18, 2009 10:41 am ] |
| Post subject: | Re: Project Euler... |
So i checked Euler statistics this morning, and i noticed something strange ... Did anyone else notice someone by the ID name of "Crapptoilet" ? It seems as if overnight, this person has become 4th in Canada, overtaking both Cyril and I O.O I find this a bit strange ... Since i have never noticed this person in the top 100 people in Canada ... weird ... A.J and Schneider, watch out! P.S: It also say's on his profile page, that his just testing this ... |
|
| Author: | A.J [ Thu Jun 18, 2009 7:14 pm ] |
| Post subject: | RE:Project Euler... |
yeah, he has collected answers to project euler from over the internet and he is 'testing them out' (I messaged him to remove the website from where he got the solutions from....) This is sooo cheap, and we should talk to the people in charge to try removing him (I know that we can't...but we'll try!) |
|
| Author: | A.J [ Fri Jun 19, 2009 11:27 am ] |
| Post subject: | RE:Project Euler... |
NOOOOO! My program for #245, that is supposed to run for 5 days...ruined! Apparently there was a minor power outage at my house while I was writing my exams at school....wow, talk about bad luck! Well, I guess that means I just have to try finishing #245 the efficient way (which will take me some time....) |
|
| Author: | bbi5291 [ Fri Jun 19, 2009 11:48 am ] |
| Post subject: | Re: Project Euler... |
haha, I guess from now on you will include code to save your program's state to disk |
|
| Author: | Shah-Cuber [ Fri Jun 19, 2009 3:30 pm ] |
| Post subject: | Re: Project Euler... |
Awww, that sucks, my program for #245 still can't calculate up to10^11, however, i have optomized my algorithm during the past few days, and it has speed up the time greatly! But it still cannot calculate it ... currently i have set my eyes on #194, #195, #198 and #200, hopefully i will get them by Wednesday? There must be some very clever DP for #245, but i can't get it, mine is brute force
oh well, good luck! |
|
| Author: | Shah-Cuber [ Fri Jun 19, 2009 9:00 pm ] |
| Post subject: | Re: Project Euler... |
Got #200
AHAHAHA, Brute Force FTW ! |
|
| Author: | A.J [ Fri Jun 19, 2009 10:08 pm ] |
| Post subject: | RE:Project Euler... |
#245 doesn't require any DP. The observations you have made so far should suffice for an efficient brute force solution |
|
| Author: | Shah-Cuber [ Sat Jun 20, 2009 4:12 pm ] | ||
| Post subject: | Re: Project Euler... | ||
Got #195(Inscribed circles of triangles with one angle of 60 degrees)
I used a parametrization of 60-degree triangles ... lots of algebra needed, at least for my part, oh well ... it broke the 1 min rule for my program, ~ 5 min ... sad ... now for #251
http://projecteuler.net/index.php?section=problems&id=251 For those wondering, wolfram alpha won't help that much: http://www77.wolframalpha.com/input/?i=((a%2Bbsqrt(c))^(1/3))+%2B+((a-bsqrt(c))^(1/3))+%3D+1 I bet everyone already checked this once they saw the problem, ahahaha I already discussed some of the matters for #251 with A.J, and we have come up with some aspects for this problem. First of all, the equation given on wolfram alpha can be simplified to: 8a^3 + 15a^2 - 27b^2*c + 6a - 1 = 0 Following this, A.J had made some progress to outputing the 149 triples where a+b+c <= 1000, and the following values were generated:
However, the problem is that, all we have noticed is a = 2(mod 3) ... and nothing else, so we were hoping if anyone else notices anything that might help. I recommend making a small brute force program first to check, as it might help you better understand the situation. Thank you, and good luck ! Find how many Cardano Triplets exist such that a+b+c <= 100000000 ... |
|||
| Author: | A.J [ Sat Jun 20, 2009 4:26 pm ] |
| Post subject: | RE:Project Euler... |
The proof that a = (2 mod 3): Rearranging the following equation: 8a^3 + 15a^2 - 27b^2*c + 6a - 1 = 0 We get: 8a^3 + 15a^2 + 6a - 1 = 27b^2*c Since RHS is obviously divisible by 3, therefore LHS shouls also be divisible by 3. So, it follows that a = 2 (mod 3). |
|
| Author: | A.J [ Sun Jun 21, 2009 1:48 pm ] |
| Post subject: | RE:Project Euler... |
Ok, I have found something else some time back. a^2 - b^2*c = k^3 (for some odd k < 0) I am pretty sure the solutions involves this....I am just not sure how yet... EDIT: Ok, Shah_Cuber observed that a < b + c. That limits 'a' to 50,000,000...but it is still too big... EDIT2 : Nevermind...that might actually be wrong... |
|
| Author: | Shah-Cuber [ Sun Jun 21, 2009 2:27 pm ] | ||
| Post subject: | Re: Project Euler... | ||
For those wondering, we both have tried parameterization, and it has failed, so we came up with the following algorithm, which is quite slow, even in C++ (A.J) and Java (me). Spoiler alert!
We need help, any observations other then a = (2 mod 3) ? This is very irritating, and time consuming (wasted my weekend >_>) ... moving on to #242 ... |
|||
| Author: | saltpro15 [ Sun Jun 21, 2009 3:41 pm ] |
| Post subject: | RE:Project Euler... |
Quote: 100000000!
what?! |
|
| Author: | Shah-Cuber [ Sun Jun 21, 2009 3:56 pm ] |
| Post subject: | Re: Project Euler... |
@saltpro15: Read the question: http://projecteuler.net/index.php?section=problems&id=251 Or, you might have meant that you were shocked. If so, then yes >_> |
|
| Author: | saltpro15 [ Sun Jun 21, 2009 4:36 pm ] | ||
| Post subject: | RE:Project Euler... | ||
Shocked indeed. That's ridiculous edit : I'm a little bamboozled, why is my solution for the very simple Euler #9 failing?
|
|||
| Author: | A.J [ Sun Jun 21, 2009 5:35 pm ] |
| Post subject: | RE:Project Euler... |
??? why are you incrementing a, b and c? so, according to your program, a = b = c? Which isn't true try iterating through a and b, and check if sqrt(a^2 + b^2) is an integer, and if a + b + sqrt(a^2+b^2) = 1000 |
|
| Author: | saltpro15 [ Sun Jun 21, 2009 5:39 pm ] |
| Post subject: | RE:Project Euler... |
alright, thanks AJ |
|
| Author: | A.J [ Sun Jun 21, 2009 6:20 pm ] | ||
| Post subject: | RE:Project Euler... | ||
In fact, you don't need a program for this problem. There exists a Pythagorean-triple that goes something like this: a= 2mn b= m^2 -n^2 c = m^2 + n^2 where m and n are positive integers. (Note the following spoiler only gives you a hint, not the whole solution itself)
|
|||
| Author: | Analysis Mode [ Sun Jun 21, 2009 8:19 pm ] |
| Post subject: | Re: Project Euler... |
@A.J.: You neglected to mention that m and n need to be coprime and only one of them be even. |
|
| Author: | A.J [ Sun Jun 21, 2009 8:30 pm ] |
| Post subject: | RE:Project Euler... |
@Analysis Mode - Those pieces of information don't necessarily have to be true since this triple doesn't have to be primitive. |
|
| Author: | saltpro15 [ Sun Jun 21, 2009 9:06 pm ] |
| Post subject: | RE:Project Euler... |
well, got it anyway. Thanks to AJ. |
|
| Author: | saltpro15 [ Sun Jun 21, 2009 9:08 pm ] |
| Post subject: | RE:Project Euler... |
so for #251, you have to test for input up to 100000000! ?. Because that's just ridiculous, no way that will run in 1 min |
|
| Author: | Shah-Cuber [ Sun Jun 21, 2009 9:20 pm ] |
| Post subject: | Re: Project Euler... |
Yes, you have to gain x number of Cardano Triplets, with a + b + c <= 10^8. The method which i explained before is quite slow (took 149438 milliseconds to calculate only up to 10^4!). I am trying parameterization again, but with no success ... However there is always a solution which is under one minute, remember, "Each problem has been designed according to a "one-minute rule". It may take several hours/days/weeks? to get the algorithm, but it is always possible under one minute It's just a matter of thinking/solving equations ... which is after all the intention of Project Euler ... |
|
| Author: | A.J [ Sun Jun 21, 2009 10:05 pm ] |
| Post subject: | RE:Project Euler... |
In fact, most of the problems have an optimal solution that can run in a few seconds. While there are problems where the runtime is about 1 min. |
|
| Author: | Cyril [ Sun Jun 21, 2009 11:47 pm ] |
| Post subject: | RE:Project Euler... |
Bah. Quadratic Diophantine equations are not so bad, but it becomes quite annoying when it's cubic. For most things involving quadratics, you have stuff like the Pythagorean triple parametrization, and the ternary tree method. I'm not going to attempt #251 for a while. And I think #200 fails to afford a sub-1 minute solution... as long as you don't make that certain heuristic. I was sort of disappointed/annoyed with that one. |
|
| Author: | A.J [ Mon Jun 22, 2009 3:13 pm ] |
| Post subject: | RE:Project Euler... |
Ok, I think I am done #251. I just have to code up my solution. I actually had everything I needed about 20 minutes after the problem was released...I was just too stupid to notice it....wow... |
|
| Author: | darkraven [ Tue Jun 23, 2009 7:31 am ] |
| Post subject: | Re: Project Euler... |
a=3*k-1 b^2*c=k^2*(8*k-3) but how to count them?? |
|
| Author: | A.J [ Tue Jun 23, 2009 10:08 am ] |
| Post subject: | RE:Project Euler... |
er...that's not what I used, but sort of similar. And try not to post too much here, as Project Euler doesn't like us discussing these problems. |
|
| Author: | Luckytoilet [ Tue Jun 23, 2009 2:29 pm ] |
| Post subject: | Re: Project Euler... |
Hi, I'm new here and I go by the name 'Crappytoilet' on ProjectEuler; I think I may have offended some people here: Quote: So i checked Euler statistics this morning, and i noticed something strange ... Did anyone else notice someone by the ID name of "Crapptoilet" ? It seems as if overnight, this person has become 4th in Canada, overtaking both Cyril and I O.O
I find this a bit strange ... Since i have never noticed this person in the top 100 people in Canada ... weird ... A.J and Schneider, watch out! P.S: It also say's on his profile page, that his just testing this ... Quote: yeah, he has collected answers to project euler from over the internet and he is 'testing them out' (I messaged him to remove the website from where he got the solutions from....)
This is sooo cheap, and we should talk to the people in charge to try removing him (I know that we can't...but we'll try!) Please note that I'm merely collecting solutions, and don't mean offense to anyone here. After recieving a message from 'amlesh44' I've immediately removed the URL from my profile; I could also remove my nationality from my profile if it offends you. Thanks. |
|
| Author: | endless [ Tue Jun 23, 2009 2:47 pm ] |
| Post subject: | RE:Project Euler... |
not that it bothers me, as I'm not ranked very high, but i think removing your nationality would be appropriate so as not to skew the standings. |
|
| Author: | Shah-Cuber [ Tue Jun 23, 2009 3:48 pm ] |
| Post subject: | Re: Project Euler... |
Much appreciated
I also recommend actually doing some of these problems for yourself, as it is an enriching experience. |
|
| Author: | A.J [ Tue Jun 23, 2009 4:05 pm ] |
| Post subject: | Re: Project Euler... |
Luckytoilet wrote: After recieving a message from 'amlesh44' I've immediately removed the URL from my profile; I could also remove my nationality from my profile if it offends you. Yeah, hi, I am amlesh44, nice to meet you. Why are you collecting solutions and entering them onto the site? You don't gain much knowledge (I guess you could learn a little). I don't mind whatever your 'nationality' is, I just wanted to know whether all the problems you solved are from 'collecting' them? Or did you try solving any of them? Just asking |
|
| Author: | Luckytoilet [ Tue Jun 23, 2009 5:22 pm ] |
| Post subject: | Re: Project Euler... |
Hi: My original account was called Luckytoilet; though because I'm not very smart I've only solved ~70 questions. Then I got bored of actually solving the problems, and created a new account to check 'cheated' solutions. Then I created a website of solutions so others like me wouldn't have to search through the internet to get them. |
|
| Author: | A.J [ Tue Jun 23, 2009 5:25 pm ] |
| Post subject: | RE:Project Euler... |
why do you want to ruin it for others? Or even encourage this sort of thing? Why would people like you want to solve these questions via cheating? |
|
| Author: | Luckytoilet [ Tue Jun 23, 2009 5:27 pm ] |
| Post subject: | Re: RE:Project Euler... |
A.J @ Tue Jun 23, 2009 5:25 pm wrote: why do you want to ruin it for others? Or even encourage this sort of thing? Why would people like you want to solve these questions via cheating?
I saw Haskell Wiki, any many other solution lists, and figured it was ok to compile them into one. |
|
| Author: | A.J [ Tue Jun 23, 2009 5:30 pm ] |
| Post subject: | RE:Project Euler... |
Well....it isn't ok. I would advise you to stop broadcasting these solutions....as I don't mind you wanting to cheat your way through these problems, but 'helping' others isn't right. So please stop showing these solutions on the internet. (and a mod better not lock this thread.....I am serious, don't lock this thread as it is quite important to a lot of people) |
|
| Author: | Analysis Mode [ Tue Jun 23, 2009 7:17 pm ] |
| Post subject: | Re: Project Euler... |
You know, if this was the USACO Training Pages you were posting solutions for, you'd be banned for life. |
|
| Author: | A.J [ Tue Jun 23, 2009 7:20 pm ] |
| Post subject: | RE:Project Euler... |
@Analysis Mode - Yes, that's true. I didn't know you did USACO though. Where are you on the training pages? I stopped 1 question before Ch 6 about 2 months ago ....and started Project Euler
Well, since it's project euler, I guess he could continue doing what he does... (but I don't like the fact that he displays these solutions...) |
|
| Author: | Analysis Mode [ Tue Jun 23, 2009 8:02 pm ] |
| Post subject: | Re: Project Euler... |
lol, I'm somewhere in Chapter 1. Thing is, I know everything in Chapter 1,2, and maybe a bit of 3, as well as stuff here and there (convex hull, max flow, etc.) I wouldn't be learning any new algorithms, so I lack the motivation to work. However, I do the monthly contests. also, on a similar note, here's the latest news from SPOJ (which I do enjoy doing): " 2009-06-22 22:24:04 (reg) To cheat or not to cheat - that is the question! by Michał Małafiejski If you have multiple accounts for testing purpose only, if you send not your own source codes, or if you are just a 'cheater' - please consider: - disqualifying your submissions - checking 'Remove me from the user ranking (main contest)' in your profile" |
|
| Author: | A.J [ Tue Jun 23, 2009 9:15 pm ] |
| Post subject: | RE:Project Euler... |
Haha, nice
Too bad Project Euler has nothing like that... |
|
| Author: | bbi5291 [ Wed Jun 24, 2009 8:09 am ] |
| Post subject: | Re: Project Euler... |
Analysis Mode @ Tue Jun 23, 2009 8:02 pm wrote: Thing is, I know everything in Chapter 1,2, and maybe a bit of 3, as well as stuff here and there (convex hull, max flow, etc.) I wouldn't be learning any new algorithms, so I lack the motivation to work.
It's not about algorithms, it's about problem solving. You might know shortest paths, flood fill, DP, MST, and convex hull (wait, do you know Eulerian paths though?) but most problems on the USACO training webpage are ad hoc. Can you solve Shaping Regions (rect1)? I'd love to see that. |
|
| Author: | A.J [ Wed Jun 24, 2009 8:52 am ] |
| Post subject: | RE:Project Euler... |
Yeah, I remember solving those problems..... Shaping regions was a cool problem, I liked it. I got stuck on a similar problem, and that's why I stopped for while (and then later I continued PE). Does anyone know what's in Ch6? Are there questions to solve like Ch1 -> Ch5? Or is it different? |
|
| Author: | bbi5291 [ Wed Jun 24, 2009 9:08 am ] |
| Post subject: | Re: Project Euler... |
There are three problems in Chapter 6, as far as I know: rectbarn, cowxor, and vans. You can view them by going to the problem statement for some problem to which your currently have access, and editing the URL. |
|
| Author: | A.J [ Wed Jun 24, 2009 9:55 am ] |
| Post subject: | RE:Project Euler... |
thanks for those question! I'll do them later. |
|
| Author: | Shah-Cuber [ Thu Jun 25, 2009 2:29 pm ] |
| Post subject: | Re: Project Euler... |
Finally got #251 ... ran it for ~ 30 min ... the rearrangement of the equation was factorized several times, thanks to wolfram alpha, and just looped through each possible values, and had recursive function to generate the prime factors of the factorized values ... may seem straight forward, but it was actually kinda hard ... oh well ... #252 in t - minus: 1 day, 16 hours, 25 minutes |
|
| Author: | Analysis Mode [ Fri Jun 26, 2009 4:00 am ] |
| Post subject: | Re: Project Euler... |
I know the concept of eulerian paths, though I dont think ive run into a problem involving it, nor have i thought about it. ok youre right, but that doesnt change the fact that im not motivated to work on usaco. just saw this: for those of you who dont use spoj, you should read vdmedragon post. http://www.spoj.pl/forum/viewtopic.php?f=3&t=5675&sid=312678274b1391dcbf284b07a3bbfe99 yeah that guys got anger management problems. |
|
| Author: | exstac [ Sat Jun 27, 2009 6:56 am ] |
| Post subject: | Re: Project Euler... |
I couldn't resist the urge to comment on your discoveries regarding problem 251. I implemented a brute force solution for a+b+c<=1000 to see if I could see any patterns in the solutions. My first observation was that a = n*3+2 as stated previously in this thread. I then discovered that there always exists a solution (given a = n*3+2) such that b = 3*a+1 and c = 3*a - b. Another solution that also always exists is a = n*3+2, b = 1, c = x (I won't tell you what x is here). Unfortunatly my cleverness ended here (actually it ended just a bit further up the road but I won't write about those last revelations) and I could only come up with gruesomely slow brute force solution. It will probably be complete in the beginning of next week. Could someone give me a hint or point me in the right direction? |
|
| Author: | A.J [ Sat Jun 27, 2009 1:37 pm ] |
| Post subject: | RE:Project Euler... |
@exstac - well, what I did was recognize that the equation simplified to: ( (a + 1)/3 )^2 * (8a - 1)/3 = b^2 * c It now just becomes a factoring exercise now... Try doing something similar to this in your case..I am pretty sure you'll get somewhere 
btw, what's your username on project euler. |
|
| Author: | exstac [ Sat Jun 27, 2009 1:45 pm ] |
| Post subject: | RE:Project Euler... |
The same as here, I'm not that good at project euler. I hope that this will be my first "high level problem". Edit: Looked a little at your tip and found that it was exactly what I had already found out. In my last post I wrote that b = (a+1)/3 and c = 3a-b = (8a-1)/3 The LHS of the equation in your post is b^2*c (with my values of b and c). But according to my observations these relations between a, b and c does not generate all solutions =(. I'll look into this a little further. I must have overlooked something. |
|
| Author: | A.J [ Sat Jun 27, 2009 5:07 pm ] |
| Post subject: | RE:Project Euler... |
No, it actually does generates all triples... Also, note that a = 2 (mod 3). I actually thought that I was overlooking something too, but I actually had everything I needed all along! I just hadn't realised it..... Just try building integers 'b' and 'c' from:( (a + 1)/3 )^2 * (8a - 1)/3 = b^2 * c I am doing pretty bad in PE also...I haven't solved a single problem in a LONG time..... #252 is actually quite easy, but since I am in California (oh yeah!) at my uncle's, I can't get much time to code anymore..... And exstac, I am pretty sure you'll figure it out soon =) |
|
| Author: | Cyril [ Sat Jun 27, 2009 10:25 pm ] |
| Post subject: | RE:Project Euler... |
Divide and conquer for 252? Reminds me of the weird huge cases for IOI 2008's Pyramid Base. Or maybe it's easier- triangulate the points and combine to make convex holes? |
|
| Author: | A.J [ 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 =) |
|
| Author: | Shah-Cuber [ 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
Regarding #252, Divide & Conquer seems the way to go ... |
|
| Author: | A.J [ 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') |
|
| Author: | Shah-Cuber [ 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 ), 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. |
|
| Author: | A.J [ 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? |
|
| Author: | endless [ 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.  |
|
| Author: | bbi5291 [ 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? ) |
|
| Author: | A.J [ 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.... |
|
| Author: | darkraven [ Tue Jun 30, 2009 11:10 pm ] |
| Post subject: | Re: Project Euler... |
Passed #251 my program run 24 seconds |
|
| Author: | A.J [ Wed Jul 01, 2009 12:00 am ] |
| Post subject: | RE:Project Euler... |
nice =), good job how did you finally solve it? |
|
| Author: | darkraven [ Wed Jul 01, 2009 2:10 am ] | ||
| Post subject: | Re: Project Euler... | ||
it's hard to explain.
|
|||
| Author: | darkraven [ Wed Jul 01, 2009 4:56 am ] |
| Post subject: | Re: Project Euler... |
solve #252 using a dynamic programming method |
|
| Author: | Shah-Cuber [ 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 >_> |
|
| Author: | Shah-Cuber [ 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? |
|
| Author: | A.J [ 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
EDIT: Just one more to 100% =) |
|
| Author: | darkraven [ Wed Jul 01, 2009 7:45 pm ] |
| Post subject: | RE:Project Euler... |
@Shah-Cuber,My user name on Project Euler is DarkRaven,I've sovled 39 problems |
|
| Author: | A.J [ Thu Jul 02, 2009 10:38 am ] |
| Post subject: | RE:Project Euler... |
Yay, I got #245! I am at 100%! Whew, now to relax till #253 comes out
And is it just me, or is CrappyToilet not a member on PE anymore? |
|
| Author: | saltpro15 [ Thu Jul 02, 2009 12:11 pm ] |
| Post subject: | RE:Project Euler... |
wow, congrats AJ, that's ridiculous. I'm far too addicted to SPOJ to work on Euler for now, but I have all boring year in CS class to work on it... |
|
| Author: | Cyril [ Thu Jul 02, 2009 1:38 pm ] |
| Post subject: | RE:Project Euler... |
Wow- congratulations! Perhaps I will do some sort of mathematical overhaul, so I can be in shape to match your achievement. Perhaps I am too lazy. CrappyToilet exists, but is no longer associated with Canada. |
|
| Author: | bbi5291 [ Thu Jul 02, 2009 3:05 pm ] |
| Post subject: | Re: Project Euler... |
Uh-oh, now I'm scared. If Cyril isn't good enough at math, I may as well give up now. |
|
| Author: | A.J [ Thu Jul 02, 2009 9:28 pm ] |
| Post subject: | RE:Project Euler... |
I can't seem to find CrappyToilet on the rankings anymore...maybe I am just blind... @ Brian- Obviously, Cyril is being modest. He is really good at math =). It is me who has to get in shape to match his level of skill. |
|
| Author: | Cyril [ Thu Jul 02, 2009 11:54 pm ] |
| Post subject: | RE:Project Euler... |
Huh? What in the world did I do to deserve this? Having no background in math other than random reading, I am certainly far below you two. |
|
| Author: | bbi5291 [ Fri Jul 03, 2009 11:49 am ] |
| Post subject: | Re: Project Euler... |
*sigh* all this modesty starts to become a source of irritation after a while. I met you at stage 2, I know how good you are at math. Heck, you even knew some theorem in computer science that I didn't know. Unless the real Cyril Zhang has been kidnapped and you are some sort of impostor? |
|
| Author: | A.J [ Fri Jul 03, 2009 1:28 pm ] |
| Post subject: | RE:Project Euler... |
That's right Cyril. You be modest one more time and I'll fly down to Ottawa and personally deal with you |
|
| Author: | Shah-Cuber [ Fri Jul 03, 2009 6:05 pm ] |
| Post subject: | Re: Project Euler... |
You all forget that his an evil robot sent to destroy the universe ... on a side note, i am beginning to dream nightmares about ambiguous numbers ... It is impossible ... on another side note, i am now discovering the beauty of the Farey sequences and am developing an irrational fear of the V-Cube 7 *shivers* |
|
| Author: | A.J [ Fri Jul 03, 2009 8:20 pm ] |
| Post subject: | RE:Project Euler... |
| nice |
|
| Author: | Cyril [ Fri Jul 03, 2009 9:18 pm ] |
| Post subject: | RE:Project Euler... |
Ahhh, programmer violence! At least I'm no longer in Ottawa. Shah-Cuber will NOT tell you where I live. |
|
| Author: | A.J [ Fri Jul 03, 2009 10:47 pm ] |
| Post subject: | RE:Project Euler... |
Really? I thought that camp thing lasted for the whole summer...oh well. I will find out where you live!! ( ) |
|
| Author: | Shah-Cuber [ Fri Jul 03, 2009 10:51 pm ] |
| Post subject: | Re: Project Euler... |
I was kept to secrecy against my will  |
|
| Author: | saltpro15 [ Sun Jul 05, 2009 5:56 pm ] |
| Post subject: | RE:Project Euler... |
haha, imagine actually waking up with a programmer 3 inches from your face with a big ol' kitchen knife... edit : forget the knife, they'd probably beat you to death with a keyboard |
|
| Author: | Shah-Cuber [ Mon Jul 06, 2009 6:00 pm ] |
| Post subject: | Re: Project Euler... |
5 days of struggling with #246 ... I hate geometry problems >_> Just calculate a given point from the center of the ellipse ... 'nough said ... Used Wolfram Alpha for most of the calculations =P |
|
| Author: | bbi5291 [ Tue Jul 07, 2009 5:30 pm ] |
| Post subject: | Re: Project Euler... |
Instead of using Wolfram Alpha, why not download the engine it uses for its calculations - Wolfram Mathematica? http://*********** lol, the domain is censored, but the link still works |
|
| Author: | Dan [ Tue Jul 07, 2009 6:22 pm ] |
| Post subject: | Re: Project Euler... |
bbi5291 @ 7th July 2009, 5:30 pm wrote: lol, the domain is censored, but the link still works Theres a reason for that, no links to warez. |
|
| Author: | Shah-Cuber [ Tue Jul 14, 2009 6:53 pm ] |
| Post subject: | Re: Project Euler... |
Finally level 6 ... 
I have a headache right now, but it took me a week to solve #248, which is numbers for which Euler's totient function equals 13!, a lot of little details to deal with primes, ahhg! ... it was hardcoded ... Well, at least I can rest now ... They changed the problem a while back from 100,000 to 150,000 for the number to find. ... great ... i still have to finish Coresilience and Ambiguous Numbers, this is torture. I'll sleep now ... |
|
| Author: | A.J [ Tue Jul 14, 2009 10:52 pm ] |
| Post subject: | RE:Project Euler... |
I am kind of bored now that there aren't any more PE questions to do....it has been about 2 weeks w/out PE.. so I am suggesting new questions to them and I got addicted to SC.... (I am in a MathCamp at washington....it is soooooooo fun!) |
|
| Author: | matt271 [ Thu Jul 16, 2009 12:20 am ] | ||
| Post subject: | Re: Project Euler... | ||
to anybody who cares... i think i have the best solution to Problem 40 Quote: An irrational decimal fraction is created by concatenating the positive integers:
0.123456789101112131415161718192021... It can be seen that the 12^(th) digit of the fractional part is 1. If d_(n) represents the n^(th) digit of the fractional part, find the value of the following expression. d_(1) ? d_(10) ? d_(100) ? d_(1000) ? d_(10000) ? d_(100000) ? d_(1000000) my solution in c99 is: (i hope this hides for non-spoilers)
the c code itself is not that impressive, but the math i used i think is. i have (what i like to think is) a brilliant method to derive the numbers u see in array a[]
does anybody care? anybodys thoughts? i wanted to post this on the thing for it, but its locked for archive. |
|||
| Author: | Cyril [ Thu Jul 16, 2009 2:00 am ] |
| Post subject: | RE:Project Euler... |
Haha, I suppose naming a function after yourself is the best alternative to becoming famous enough as to have others do it for you. Anyways, nice, clean, morally justified solution- out of laziness, I just used an ostringstream and bashed it. |
|
| Author: | A.J [ Wed Jul 22, 2009 11:52 am ] |
| Post subject: | RE:Project Euler... |
Very nice solution Matt. I like the clean code (you don't see that very often nowadays). However, I do not believe that you have the best solution. Your method is certainly a good method, but I think there's a better one. However, I might be mistaken. Once again, I like the cleanliness in the code. |
|
| Author: | Cyril [ Thu Jul 23, 2009 11:09 am ] |
| Post subject: | RE:Project Euler... |
http://www.research.att.com/~njas/sequences/A033307 Oh wow, there's a closed-form formula. But this is impractical, as there would be precision errors with computing the Lambert W-function. Interesting though. |
|
| Author: | Shah-Cuber [ Mon Apr 26, 2010 2:24 am ] |
| Post subject: | Re: Project Euler... |
Weeeeee - It's 3 am Renewing post after 9 months ... Coming back for new problems & more headaches 
Enjoy! |
|
| Author: | A.J [ Mon Apr 26, 2010 7:04 am ] |
| Post subject: | RE:Project Euler... |
Well, the latest problem, p289, is giving me quite some trouble. However the latest few, < 289, were pretty easy. Maybe Project Euler wants < 50 people to have solved all the problems |
|