Problem 173 & 174

[daniel.is.fischer]

Problem 173 & 174 will be accessible on Saturday, 22. December at 1 pm (GMT).
There might be a problem with e-mail notification, so I announce it also here.

[stijn263]

what's the reason that there's 2 new problems this week? (i'm not complaining, just wondering )

[daniel.is.fischer]

They're too closely related to publish separately. Besides, it's a nice year's end gift, we thought

[stijn263]

ah, i see what you mean now . they were quite easy though, even easier than 172

o well, i guess they can't all be as tough as 161, that one still gives me headaches

[daniel.is.fischer]

They can't and shouldn't all be as tough. But keep a supply of acetyl-salicylic acid, you might need it every now and then

[stijn263]

POLITE REQUEST (Sat 22 Dec 07)
It is now the intention of the Project Euler team to rotate the difficulty of new problems through an easy-medium-hard-medium- cycle. As the background of members differs significantly, seasoned programmers may find some "hard" problems not too challenging, whereas members who have less experience might find some of the "easy" problems challenging enough. For this reason could members please restrict comments in the forum to methodology, interesting properties/observations, and extension challenges. It could be very discouraging for someone who has battled for hours through research and failed attempts to finally solve the problem and then to read in the first fews posts of the forum comments like, "This was too easy!"
Thanks, euler

that makes sense, i edited my post a bit . btw, are 161, 163, 167 and 170 considered as being hard problems? they did give me a lot of trouble, that's for sure

[daniel.is.fischer]

170 was considered medium, 163 medium to hard. You see, judgement differs

[hk]

We thought 167 (Ulam) not very hard, more on the hard side of medium, if one had taken the trouble to look up the information that the differences would get cyclic. From the number of solvers we underestimated the difficulty of that one.

[stijn263]

i like to solve every problem without looking anything up. finding the cyclic differences property took me quite some time, since the period is pretty large. i think a lot of people try and solve problems without looking things up

at least 161 is considered hard. you might even think about considering it as impossible

[hk]

Of course it's more rewarding to find out such things yourself. In that case the Ulam problem surely becomes much harder.
OTOH Could one solve http://projecteuler.net/index.php?secti ... lems&id=57 without looking up things about continued fractions? (Unless one has had continued fractions as subject for an academic course).
Project Euler is aimed at a general public with the will to learn. It's public is a very wide audience. Also their education dates from the mid 50's until still going on.
From the contibutions in the forum might be expected that they might be helpful for those that struggled their way to the answer.
In that light contributions like "Simple DP approach" might be conversation between ICT guys but should be avoided in the forum. Please give others a chance to learn from what you know.

[stijn263]

of course i have to look up some mathematical things every now and then, but when solving a problem i try to avoid that as long as possible

however i'm looking up Maple or C++ stuff constantly, and learning a lot about both languages while doing so

good point about the forum contributions, as a student mathematics i'm probably using terms not everyone is familiar with. i think i've used "easy DP problem" and "just solved the diophantine equation" more than once

[daniel.is.fischer]

It's okay to use such terms, only give a little detail of what sort of DP, what state do you keep in which variable etc, what theory is behind your solution of the diophantine equation... So people might say, 'Oh, cool seems to be really easy if one knows continued fractions, must read about them'.

[xenon]

It's quite common to use qualifiers to classify methods, both in programming and in math. Those qualifiers should be taken value-free, of course. If a math-guy says: "I was able to reduce this ugly looking differential equation to a rather simple polynomial, thereby making the solution trivial", he doesn't mean that whoever wrote down the equation made a mess of it and that you have to be a complete moron if you can't solve it. The term 'Simple DP' is quite often used to describe the fact that you don't need the more obvious non-polynomial time brute-force method, and in no way to belittle people who can't solve the problem. But I agree that those descriptions can act as spoilers and should therefor be avoided in a forum.

[ed_r]

... contributions like "Simple DP approach" might be conversation between ICT guys but should be avoided in the forum. Please give others a chance to learn from what you know.

Like this, you mean?

• forum> Here's my code.
  forum> It uses a sieve and performs in 52ms
  forum> <code...>

Not great for those unfamiliar with sieving or with Delphi !

I guess we must all try harder.

[daniel.is.fischer]

@xenon: I think you misunderstood. My point is 'simple DP' alone isn't helpful for those who didn't see it. So be kind to them and explain a little, so that others might learn how to reduce it to a simple problem themselves. It's no use reading something like '1ms', followed by 15 characters of J or two pages of cpp-macros. A description of the algorithm in understandable terms is far more helpful, even for those who used the same algo, but cannot guess because they wrote it in 10 lines of clean.

@ed_r: At least it contains the word 'sieve', a starter for research (google for 'sieving algorithms' or 'prime sieves' or so, follow a few links, you have an idea). But more info wouldn't harm and we all should try harder indeed.

[ed_r]

Have you seen those FAQs, reviews, etc. that end with a site-generated question: "Was this (FAQ/review/whatever) helpful to you?" ?

I wonder if such a thing could be added to the PE problem forums? It might work quite well, with the show-offs who previously posted terse comments (regrettably, I include myself there) now feeling the need to compete on clarity too. PE could have a hall of fame for helpful posters, with quarterly prizes, £100 cheques, all-inclusive holidays, ... oh hang on, I'm getting carried away But I think you get the idea.

Colin, as if you didn't have enough to do already ...?

[stijn263]

i think that everyone that uses a approach different from the ones explained before, should try to explain his approach to the problem. this isn't always as easy (sometimes i even find it hard to explain what i'm doing in dutch) but it does add something for other users. explaining an algorithm that has been clearly explained before doesn't add much imo. so in that case, you could just mention some things you encountered or whatever

[joshbowman205]

I agree with whoever said that posting your solution isnt all that helpful. Functional languages look like a mess to me and a fair few posters seem to hate whitespace to the extent that the code becomes impossible to follow.

I try and post a short pseudo version where possible. Just show what i iterated on or was counting

as for the problem im still waiting for a hard one.. seems we have had a run of easy problems.

[daniel.is.fischer]

Yes, we made up a little for a run of hard ones. Look at the number of solutions most problems after #140 got. We have the bunch of people being able to solve almost anything in a couple of hours (not always the same bunch), but a problem getting fewer solutions in months 2 to 7 of their public life than in the first week seems hard for most. We are happy to have some brilliant people around, but we don't want to put off those with less background and experience. Catering for both groups is difficult.

[joshbowman205]

I see your point it is difficult selecting problems for such a wide range. I wonder if perhaps some of the later problems are not attempted at all, rather than being harder. If a new user solves problems by difficulty some of the older problems have been completed by larger numbers of people and would be attempted first. It could be that people dont have time to complete ~100 problems before attempting some of the more recent ones. No idea if the stats back this up