Project Euler...

[Analysis Mode]

You know, if this was the USACO Training Pages you were posting solutions for, you'd be banned for life.

[A.J]

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

[Analysis Mode]

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"

[A.J]

Haha, nice

Too bad Project Euler has nothing like that...

[bbi5291]

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.

[A.J]

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?

[bbi5291]

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.

[A.J]

thanks for those question! I'll do them later.

[Shah-Cuber]

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

[Analysis Mode]

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.

[exstac]

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?

[A.J]

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

[exstac]

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.

[A.J]

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 =)

[Cyril]

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?