Обсуждение @ 2004. Учёные из Спилково @ Timus Online Judge

Idea.

Послано IgorKoval [PskovSU] 11 янв 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.

Послано Vedernikoff 'Goryinyich' Sergey (HSE: АОП) 11 янв 2014 22:50

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

Re: Idea.

Послано IgorKoval [PskovSU] 13 янв 2014 21:12

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

Re: Idea.

Послано Vedernikoff 'Goryinyich' Sergey (HSE: АОП) 13 янв 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.

Послано QProgS 28 янв 2014 19:32

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

Обсуждение задачи 2004. Учёные из Спилково