Problem 173 & 174

A place to air possible concerns or difficulties in understanding ProjectEuler problems. This forum is not meant to publish solutions. This forum is NOT meant to discuss solution methods or giving hints how a problem can be solved.
Forum rules
As your posts will be visible to the general public you
are requested to be thoughtful in not posting anything
that might explicitly give away how to solve a particular problem.

This forum is NOT meant to discuss solution methods for a problem.

In particular don't post any code fragments or results.

Don't start begging others to give partial answers to problems

Don't ask for hints how to solve a problem

Don't start a new topic for a problem if there already exists one


See also the topics:
Don't post any spoilers
Comments, questions and clarifications about PE problems.
User avatar
daniel.is.fischer
Posts: 2400
Joined: Sun Sep 02, 2007 11:15 pm
Location: Bremen, Germany

Problem 173 & 174

Post by 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.
Il faut respecter la montagne -- c'est pourquoi les gypaètes sont là.
User avatar
stijn263
Posts: 1505
Joined: Sat Sep 15, 2007 11:57 pm
Location: Netherlands

Re: Problems 173 & 174

Post by stijn263 »

what's the reason that there's 2 new problems this week? (i'm not complaining, just wondering :))
User avatar
daniel.is.fischer
Posts: 2400
Joined: Sun Sep 02, 2007 11:15 pm
Location: Bremen, Germany

Re: Problems 173 & 174

Post by daniel.is.fischer »

They're too closely related to publish separately. Besides, it's a nice year's end gift, we thought :D
Il faut respecter la montagne -- c'est pourquoi les gypaètes sont là.
User avatar
stijn263
Posts: 1505
Joined: Sat Sep 15, 2007 11:57 pm
Location: Netherlands

Re: Problems 173 & 174

Post by stijn263 »

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

o well, i guess they can't all be as tough as 161, that one still gives me headaches :?
User avatar
daniel.is.fischer
Posts: 2400
Joined: Sun Sep 02, 2007 11:15 pm
Location: Bremen, Germany

Re: Problems 173 & 174

Post by 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 :wink:
Il faut respecter la montagne -- c'est pourquoi les gypaètes sont là.
User avatar
stijn263
Posts: 1505
Joined: Sat Sep 15, 2007 11:57 pm
Location: Netherlands

Re: Problems 173 & 174

Post by stijn263 »

Euler wrote: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 :-)
User avatar
daniel.is.fischer
Posts: 2400
Joined: Sun Sep 02, 2007 11:15 pm
Location: Bremen, Germany

Re: Problems 173 & 174

Post by daniel.is.fischer »

170 was considered medium, 163 medium to hard. You see, judgement differs 8-)
Il faut respecter la montagne -- c'est pourquoi les gypaètes sont là.
User avatar
hk
Administrator
Posts: 11192
Joined: Sun Mar 26, 2006 10:34 am
Location: Haren, Netherlands

Re: Problems 173 & 174

Post by 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.
Image
User avatar
stijn263
Posts: 1505
Joined: Sat Sep 15, 2007 11:57 pm
Location: Netherlands

Re: Problems 173 & 174

Post by 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 ;)
User avatar
hk
Administrator
Posts: 11192
Joined: Sun Mar 26, 2006 10:34 am
Location: Haren, Netherlands

Re: Problems 173 & 174

Post by 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.
Image
User avatar
stijn263
Posts: 1505
Joined: Sat Sep 15, 2007 11:57 pm
Location: Netherlands

Re: Problems 173 & 174

Post by 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 :D

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 :oops:
User avatar
daniel.is.fischer
Posts: 2400
Joined: Sun Sep 02, 2007 11:15 pm
Location: Bremen, Germany

Re: Problems 173 & 174

Post by 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'.
Il faut respecter la montagne -- c'est pourquoi les gypaètes sont là.
xenon
Posts: 63
Joined: Wed Sep 20, 2006 7:09 pm

Re: Problems 173 & 174

Post by 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.
User avatar
ed_r
Posts: 1009
Joined: Sun Jul 29, 2007 10:57 am

Re: Problems 173 & 174

Post by ed_r »

hk wrote:... 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. :D
!647 = &8FDF4C
User avatar
daniel.is.fischer
Posts: 2400
Joined: Sun Sep 02, 2007 11:15 pm
Location: Bremen, Germany

Re: Problems 173 & 174

Post by 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.
Il faut respecter la montagne -- c'est pourquoi les gypa&egrave;tes sont l&agrave;.
User avatar
ed_r
Posts: 1009
Joined: Sun Jul 29, 2007 10:57 am

Re: Problems 173 & 174

Post by 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 ...?
!647 = &8FDF4C
User avatar
stijn263
Posts: 1505
Joined: Sat Sep 15, 2007 11:57 pm
Location: Netherlands

Re: Problems 173 & 174

Post by 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
Posts: 59
Joined: Wed Oct 31, 2007 4:28 pm

Re: Problems 173 & 174

Post by 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.
User avatar
daniel.is.fischer
Posts: 2400
Joined: Sun Sep 02, 2007 11:15 pm
Location: Bremen, Germany

Re: Problems 173 & 174

Post by 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.
Il faut respecter la montagne -- c'est pourquoi les gypa&egrave;tes sont l&agrave;.
joshbowman205
Posts: 59
Joined: Wed Oct 31, 2007 4:28 pm

Re: Problems 173 & 174

Post by 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
Post Reply