Editorial for DMOPC '21 Contest 10 P4 - Bitwise Telephone


Remember to use this editorial 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: Riolku

Subtask 1 Hint

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

Subtask 1

If the robots generate T, output 0. Otherwise, we can change the last number to a_i XOR X XOR T 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 a_i = 2^{30}-1.

For any AND seen along the way, unless a_i = 2^{30}-1, 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 \mathcal O(a_i) transitions.

Subtask 4 Hint

SOS

Subtask 4

We can optimize the transitions to \mathcal O(\log a_i) 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 T. For OR operations, this makes sure that we turn on all bits in T 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 T 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:

1. 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 0, 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 0-1 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 T (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 a_i and T since they are now safe.

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

What remains is simply to prove that the number of nodes we visit is \mathcal O(N). 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 T 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 ORs 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 blin00 for this neat solution!


Comments

There are no comments at the moment.