Discussion @ 2004. Scientists from Spilkovo @ Timus Online Judge

Idea.

Posted by IgorKoval [PskovSU] 11 Jan 2014 19:28

Please, give me some hints and idea. I write bruteForce but i see no hints. Only random 0 and 1.

Re: Idea.

Posted by Vedernikoff 'Goryinyich' Sergey (HSE: АОП) 11 Jan 2014 22:50

Length of the answer is 2^n + n - 1, it can be constructed with brute-force

Re: Idea.

Posted by IgorKoval [PskovSU] 13 Jan 2014 21:12

Thank you. Please, give me more hints. =)

Re: Idea.

Posted by Vedernikoff 'Goryinyich' Sergey (HSE: АОП) 13 Jan 2014 23:11

Above hint is more than enough to solve it. The only possible latest hint: during BF, when construct a sequence, think how to check in O(1) that the new suffix of length n didn't occur in the sequence before.

Re: Idea.

Posted by QProgS 28 Jan 2014 19:32

it's just a De Bruijn sequence
http://en.wikipedia.org/wiki/De_Bruijn_sequence

Discussion of Problem 2004. Scientists from Spilkovo