Project Euler Forum

i am not sure that i understand problem 300 wording

the problem saying :

Assuming that H and P elements are equally likely to occur in any position along the string, the average number of H-H contact points in an optimal folding of a random protein string of length 8 turns out to be 850 / 28=3.3203125.

What is the average number of H-H contact points in an optimal folding of a random protein string of length 15?

does this mean that for each possible string there are different folds and some of them are optimal (contain the maximum number of H-H contacts ) and i have to count for each string how many optimal folds exist and compute
(number of optimal folds for all strings of length n) / 2^n ?

elr wrote:

What is the average number of H-H contact points in an optimal folding of a random protein string of length 15?

does this mean that for each possible string there are different folds and some of them are optimal (contain the maximum number of H-H contacts )

Yes.

elr wrote: and i have to count for each string how many optimal folds exist and compute
(number of optimal folds for all strings of length n) / 2^n ?

No. You are asked for the number of H-H contacts. So for each string find the optimum, i.e. the maximal number of H-H contacts it can have. Then find the average of those 2^n numbers of H-H counts.

thank you !

Give your answer using as many decimal places as necessary for an exact result.

how many decimal places would give an exact result ?
i run my algorithm several times with and without optimizations
and in all times i got the same sum of optimal h-h contacts for each string
(my sum begin with 26),my algorithm works very well for the example at the
problem page (n=8) so i believe that for some reason i submitting either shorter or longer
number than i should submit

elr wrote:

Give your answer using as many decimal places as necessary for an exact result.

how many decimal places would give an exact result ?

Since the answer in fraction form is s/2¹⁵ for some s, you can rewrite it as (s 5¹⁵) / 10¹⁵, so it won't be more than 15 decimal places.If your s is even (or is divisible by some power of 2) then you can cancel some twos and you will need fewer decimal places.

another question : there could be an invalid fold ?
does a fold that contain empty space like
HHH
HEH
HHH
where E is not H or P considered to be a valid fold ?
(i know that such fold might not be an optimal one,but i am wondering if its a valid fold)

The folded protein is allowed to enclose spaces.

Could anyone tell me how fast the program is expected to be? I'm a little over 1 minute here. Is it one of those problems where you can't write a program much much faster than 1 min? Thanks.

oleglyamin wrote:Could anyone tell me how fast the program is expected to be? I'm a little over 1 minute here. Is it one of those problems where you can't write a program much much faster than 1 min? Thanks.

Mine finds the correct answer in 1.5 sec, and it runs in Java. I suspect C++ could do the job in 200-400 ms.

Thank you, thundre. ~1 sec is astonishingly fast for me. I managed to push it to 30 seconds by reusing some intermediate results. And I have an idea how to reuse them even more, although I suspect it's not gonna improve my time by as much as 29 sec. Looking forward to see smart solutions in the closed forum.

jaap wrote: Tue Jul 12, 2011 4:26 pm Since the answer in fraction form is s/2¹⁵ for some s, you can rewrite it as (s 5¹⁵) / 10¹⁵, so it won't be more than 15 decimal places.If your s is even (or is divisible by some power of 2) then you can cancel some twos and you will need fewer decimal places.

I was trying to be clever and defined my answer to be str(d/10^15) + "." + str(d%10^15) where d = s*5^15. This doesn't work! Proof is exercise for the reader.

Don't be like me and waste hours over this stupid error :'(

oleglyamin wrote: Fri Jul 04, 2014 1:29 pm Thank you, thundre. ~1 sec is astonishingly fast for me. I managed to push it to 30 seconds by reusing some intermediate results. And I have an idea how to reuse them even more, although I suspect it's not gonna improve my time by as much as 29 sec. Looking forward to see smart solutions in the closed forum.

Actually using only naïve observations, no complicated mathematics, no terms you'd need to Wiki, I got it down to less than 2s on C++.