De Bruijn sequences (2) P55027


Statement
 

pdf   zip

html

As you may remember, a binary de Bruijn sequence of order n is a cyclic sequence of zeros and ones such that every possible subsequence of n consecutive digits appears exactly once.

Regarding the problem about de Bruijn sequences of the last UPC semifinal, Masao did not like that some precomputed solutions were accepted. In the good old days, when men were real men, and Masao was a UPC world-finalist of the ACM contest (and a real man, like now), things were not so easy! Therefore, let us make that problem a little tougher.

Input

Input consists of several cases. Every case begins with an integer number n, followed by a number r, followed by r restrictions, each consisting of a pair of integer numbers i and v, which state that the i-th leftmost position of the sequence must be v. Assume 2 ≤ n ≤ 20, 0 ≤ i < 2n and v ∈ {0, 1}. The positions are all different.

Output

For every case, print the lexicographically smallest de Bruijn sequence of order n that fulfills all the restrictions. If such a sequence does not exists, state so as shown in the sample output.

Observation

The private test cases are chosen so that a “reasonable” brute-force algorithm should be accepted, if written non-recursively.

Public test cases
  • Input

    3 0
    3 1    0 1
    2 2    0 1  2 1
    4 5    3 1  11 0  9 1  15 0  6 0
    

    Output

    00010111
    10001011
    no solution
    0011010111100100
    
  • Information
    Author
    Xavier Martínez
    Language
    English
    Official solutions
    C++
    User solutions
    C++
    Event
    Vuitè Concurs de Programació de la UPC - Final
    Date
    2010-09-22