## Editorial for DMOPC '21 Contest 10 P4 - Bitwise Telephone

**only**when stuck, and

**not to copy-paste code from it**. Please be respectful to the problem author and editorialist.

**Submitting an official solution before solving the problem yourself is a bannable offence.**

Author:

## Subtask 1 Hint

Suppose the robots currently generate . What should we change the last number to in order to have the output be ?

## Subtask 1

If the robots generate , output . Otherwise, we can change the last number to XOR XOR and win in one move.

## Subtask 2 Hint 1

Work backward.

## Subtask 2 Hint 2

If the last operation is `OR`

or `XOR`

, what happens?

## Subtask 2 Hint 3

If we work backward, what `AND`

values must be changed?

## Subtask 2

We work backward. If we see an `XOR`

or `OR`

, we can win instantly, since for `XOR`

we proceed as in subtask 1, and for the `OR`

case we set .

For any `AND`

seen along the way, unless , this operation will force a bit low, which means we have to change it.

## Subtask 3 Hint

DP

## Subtask 3

Dynamic Programming. Our state is `dp[index][value]`

, meaning that after the first `index`

operations we have a value of `value`

, with transitions.

## Subtask 4 Hint

SOS

## Subtask 4

We can optimize the transitions to by applying SOS dp. Consider the `value`

we have in our dp state as a bitmask. For `AND`

transitions we compute the minimum over all supermasks, and for `OR`

transitions we compute the minimum over all submasks. For `XOR`

we compute the minimum over all masks.

## Subtask 4 Alternate Solution Hint

If we are going to bribe a robot, what is a good value to bribe it to?

## Subtask 4 Alternate Solution

Observe that at each `AND`

or `OR`

, either it is optimal to leave the robot be, or to bribe it to change the value to . For `OR`

operations, this makes sure that we turn on all bits in that are on, and leave be any other bits, which is optimal. `AND`

is similar.

## Subtask 5

This subtask is intended for suboptimal implementations of intended.

## Subtask 6 Hint 1

Classify errors into two types: `has_high_need_low`

, meaning that the current output has a `1`

but has a `0`

, and `has_low_need_high`

, the opposite. We can represent these as bitmasks.

Bribing an `AND`

bot fixes all of `has_high_need_low`

, and bribing an `OR`

bot fixes all of `has_low_need_high`

. `XOR`

fixes both.

## Subtask 6 Hint 2

The solution involves quite a bit of casework.

## Subtask 6

Work backwards as before. If we encounter an `OR`

operation, we should bribe in two cases:

`has_high_need_low = 0`

, since then we can win instantly.
2.

`has_high_need_low`

has some bits that are on that are also on in `a_i`

. In this case not bribing would mean we lose.
When we bribe an `OR`

bot, we set `has_low_need_high`

to , since we can fix all such errors, and furthermore, we have to update `has_high_need_low`

. We can use a prefix array to update this.

Furthermore, if we bribe an `OR`

bot and we've seen but not used an `AND`

operation, we can use that `AND`

operation to win instantly. For this purpose, we should keep track of the last `AND`

we saw.

`AND`

operations proceed symmetrically to `OR`

operations. If we encounter an `XOR`

operation, we win instantly.

## Subtask 6 Alternate Solution Hint 1

Graph Theory?

## Subtask 6 Alternate Solution Hint 2

Our node is `(index, mask)`

, for some meaning of `mask`

. Work backward again.

## Subtask 6 Alternate Solution Hint 3

`mask`

is a bitmask representing the bits that are correctly set by a later operation.

## Subtask 6 Alternate Solution

Run BFS on the graph. `mask`

is initially zero.

When we process a node, first check if we need to do anything. If applying the operation to the prefix of the operations up to `index`

with the value gives (ignoring the bits in `mask`

), then we exit.

Otherwise, check the operation. If it's `XOR`

, bribe the robot and push to the back of the queue. Ignoring `XOR`

robots is never optimal.

If it's `AND`

, check if we must apply it. If we don't bribe the robot, add to the mask any bits off in and since they are now safe.

If we do bribe the robot, add to the mask all bits off in .

What remains is simply to prove that the number of nodes we visit is . The question is, for a given index, how many masks are possible?

Four masks are possible. For the `OR`

operations, either we bribed (at least) one and as such all bits on in are in the mask, or we didn't bribe any and as such the bits are a combination of all the matching bits across all the `OR`

s seen so far. A similar logic applies to the `AND`

operations, giving four masks possible (though in practice it's less, since a full mask is an instant win).

Thanks to

for this neat solution!
## Comments