DMOPC '21 Contest 10 P4 - Bitwise Telephone

View as PDF

Submit solution

Points: 17 (partial)
Time limit: 2.0s
Memory limit: 256M

Problem type

Vivy is playing a game of bitwise telephone!

In this game, N robots are sitting in a line. You give them the number S to start. In an ideal world, the robots would simply transmit the number down the line. However, these robots are a bit mischievous.

Each robot has an integer a_i and an associated operation, one of AND, OR, or XOR. When a robot receives a number, it will modify the number with its operation and a_i. For instance, if the operation is XOR and the number received is x, the robot will pass on x \oplus a_i.

Vivy wants the number T to appear at the end of this chain. However, to do so, she might have to bribe some robots. If she bribes a robot, she can change their value a_i to whatever she likes.

Vivy wonders: what is the minimum number of robots she must bribe to get T to appear at the end of the chain?


1 \le N \le 10^6

0 \le S, T, a_i < 2^{30}

Subtask 1 [5%]

All operations are XOR.

Subtask 2 [30%]

S = 0

T = 2^{30}-1

Subtask 3 [10%]

1 \le N \le 100

0 \le S, T, a_i < 2^{10}

Subtask 4 [20%]

1 \le N \le 100

0 \le S, T, a_i < 2^{17}

Subtask 5 [15%]

1 \le N \le 5 \times 10^3

Subtask 6 [20%]

No additional constraints.

Input Specification

The first line contains N, S, and T.

The next N lines contain a description of the robot. Each line first contains a character denoting the operation, either A denoting AND, O denoting OR, or X denoting XOR. After the operation is the integer a_i.

Output Specification

Output the minimum number of robots you must bribe to get T as the output. If you cannot produce T, output -1.

Sample Input

5 1 5
A 4
A 1
O 4
O 3
X 0

Sample Output



Bribing the fourth robot to change their number to 1 will produce T as output. Note that the output without bribing anyone would be 7.


There are no comments at the moment.