Project Euler Forum

In the note to the problem it was written:
For example, on a row measuring eight units in length you could use red (3), black (1), and red (4).
My question is:
If one uses (from left to right) red (4), black (1), and red (3) is it considered different from the arrangement in the example?

Thanks!

Yes, of course they are different. Otherwise there wouldn't be 17 possibilities for length 7 but only 11.

I'm having a bit of difficulty with this one. I wrote a script using an analytical approach which works fine for 4 to 10 units in length, but it seems to skip one solution when the total length is 11. Seeing as 11 is the first opportunity to have three red blocks (in a 3-1-3-1-3 setting), I'm wondering whether this is the one i miss. It seems a logical answer but the way I read the problem, it suggests that max 2 red blocks are allowed.

Do solutions with more than 2 red blocks in fact count? If so, it should definitely be clarified on the problem page.

Sedsarq wrote:Do solutions with more than 2 red blocks in fact count? If so, it should definitely be clarified on the problem page.

Yes you must count solutions with more than 2 red blocks. The only stipulation given in the problem is that the length of a red block must be at least 3.

thundre wrote: Yes you must count solutions with more than 2 red blocks. The only stipulation given in the problem is that the length of a red block must be at least 3.

Alright, thanks for the reply. I'll have another look at my algorithm tomorrow. I still think the sentence

"A row measuring seven units in length has red blocks with a minimum length of three units placed on it, such that any two red blocks (which are allowed to be different lengths) are separated by at least one black square"

is not very clear that you're allowed more than two red blocks once you have enough length.

I don't really see where the confusion lies. The phrase '.. has red blocks ..' doesn't put any restriction on the number, and the phrase 'any two red blocks' actually quite pointedly suggests there can be more - otherwise 'any' doesn't really make any sense.

Yes, good point. Looking at it again, it makes a lot of sense =) I think I need to learn how to pause a problem and go to bed when it gets too late...

Hi,

was anyone able to solve this problem in a reasonable time using permutations? Or am I trying to achieve impossible here?

Thanks
Ivan

McIvan wrote:Hi,

was anyone able to solve this problem in a reasonable time using permutations? Or am I trying to achieve impossible here?

Thanks
Ivan

I don't think it can be solve with permutations, the answer is a big number.
Try to see how it depends on the previous rows

Usuario wrote:

McIvan wrote:Hi,

was anyone able to solve this problem in a reasonable time using permutations? Or am I trying to achieve impossible here?

Thanks
Ivan

I don't think it can be solve with permutations, the answer is a big number.
Try to see how it depends on the previous rows

If you mean by permutation a combinatorial approach, than the answer is: yes, it is possible.

Martin

I know I am very late but this may help others. It most definitely is possible to solve this using combinatorics, as I have done so. You can create a simple algorithm using pure Mathematics and no dynamic programming. You can see my solution in the Thread, if you solve the question.

I'm pulling my hair out here. I feel like my algorithm is correct, I've worked out by hand what all the solutions are up to length 13 and they match what my program spits out.

Could someone tell me if the answer for a length of 13 is 305, so I can at least know if I'm doing it correctly by hand, before I spend an ungodly amount of time trying higher lengths

edit: so I noticed a pattern when solving by hand, and then got the final with pen and paper basically. The answer for 13 is 305, so I'll have to figure out where I went wrong, but I'll leave this for future people (unless it shouldnt be, in which case sorry for making you delete it mods)

Alobar wrote: Fri Aug 16, 2019 11:46 pm Could someone tell me if the answer for a length of 13 is 305, so I can at least know if I'm doing it correctly by hand, before I spend an ungodly amount of time trying higher lengths

305 is correct for a length of 13.