Problem 219

[GoSlow2GoFast]

I thought I had this figured out, but my answer doesn't check out, so I wonder if I'm missing something. Can anyone confirm if these values would be correct?

C(4)=20
C(5)=27
C(6)=35
C(7)=44
C(8)=54
C(9)=65

~gs2gf

[Ikcelaks]

C(4) should be computable by hand. Try it.

[GoSlow2GoFast]

Yes, agreed. I had done the following to come up with C(4) = 20, am I missing something?

00, 01, 10, 11
4*4 + 4 = 20

~gs2gf

[harryh]

Isn't it cheaper to choose:
000, 001, 01, 1 ?
(it only costs 4*3+6=18)

[GoSlow2GoFast]

So under that approach, an alternative minimum cost solution to C(6) would be.

00000, 00001, 0001, 001, 01, 1
5*4 + 15 = 35

~gs2gf

[harryh]

That's true; no one claims that the solution for minimum cost has to be unique.

[GoSlow2GoFast]

But that approach seems to break down for C(8) where starting with "11" rather than "1" yields a minimal cost.

000001, 000000, 00001, 0001, 001, 01, 10, 11
8*4 + 22 = 54

0000000, 0000001, 000001, 00001, 0001, 001, 01, 1
7*4 + 28 = 56

~gs2gf

[harryh]

Clearly then, "that approach" does not always produce a minimum cost.

[quilan]

Hrmm, it's frustrating to have a wonderful algorithm that I can't submit until Monday when I get to work. It looks like it's perfect.

Edit: I'm glad I had a background in compression technologies. Certainly helpful here.

[Assato]

I think I'm doing something wrong here... I get the right answer for n = 6 and for n = 8, but a wrong answer for 10^9.

Can anyone confirm my values for:

Cost(1000) = 62054
Cost(10^6) = 1888115810

Thanks a lot.

Edit: Nevermind, found my mistake (and my values were wrong, for future reference). Correct values should be:

Cost(1000) = 21708
Cost(1e6) = 43137383