TLE '17 Contest 5 P6 - Circuits

View as PDF

Submit solution


Points: 20 (partial)
Time limit: 1.0s
Memory limit: 256M

Author:
Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig
A generic circuit.

There is a circuit with N input gates, and M MOOSE gates.

A MOOSE gate computes the negation of the AND of the inputs. That is, it outputs 0 if both inputs are 1, otherwise it outputs 1.

The gates are numbered 1,\ldots,N+M starting with the N input gates. Gate number N+M is the output gate.

Each MOOSE gate's input is from two gates with smaller IDs.

At the moment all inputs have the same value x, which is unknown, but can either have the value 0 or 1.

You want to change as many of the inputs to fixed values (0 or 1) instead of x as possible so that the output of the circuit (the value of gate N+M) is the same as the output before fixing any inputs. That is, if y_0 is produced when x = 0 and y_1 is produced when x = 1, then the fixed circuit should still produce y_0 when x = 0 and y_1 when x = 1. Output one such optimal choice of hard-wiring.

Constraints

For all subtasks:

1 \le N \le 10^5

1 \le M \le 2\times 10^5

Subtask Points Additional Constraints
1 10 N \le 5, M \le 50
2 30 N \le 2 \times 10^2, M \le 2\times 10^4
3 60 No additional constraints.

Input Specification

The first line of input will contain two space-separated integers, N and M.

The next line of input will contain 2M space-separated integers. The 2i-1^{th} and 2i^{th} integers specify the inputs to gate N+i. These integers are guaranteed to be positive and less than i.

Output Specification

Output a single line with N characters, denoting an optimal assignment. The i^{th} character can either be 0 (set to false), 1 (set to true), or x (set to x). If there are multiple solutions, output any of them.

Sample Input 1

2 1
1 2

Sample Output 1

x1

Sample Input 2

3 6
1 3 1 2 4 5 4 5 7 6 8 8

Sample Output 2

10x

Sample Input 3

4 18
1 1 2 2 5 6 1 2 7 8 9 9 3 3 4 4 11 12 3 4 13 14 15 15 10 10 16 16 17 18 10 16 19 20 21 21

Sample Output 3

0000

Comments

There are no comments at the moment.