Official

F - Spices Editorial by en_translator


The following greedy algorithm yields the correct answer.

  • First, sort the spices in the increasing order of their prices. In other words, determine a permutation \((p_1, p_2, \ldots, p_{2^N-1})\) of \((1, 2, \ldots, 2^N-1)\) such that \(c_{p_1} \leq c_{p_2} \leq \cdots \leq c_{p_{2^N-1}}\).

  • Also, let \(S\) be a empty set.

  • Then, for each \(i = 1, 2, \ldots, 2^N-1\), do the following:

    • Check if hotness \(p_i\) can be obtained from some elements of \(S\), i.e. check if there exist \(x_1, x_2, \ldots, x_m \in S\) such that \(p_i = x_1 \oplus x_2 \oplus \cdots \oplus x_m\).
    • If it cannot be obtained, then add \(p_i\) to \(S\).
  • Finally, output \(C(S) := \sum_{i \in S} c_i\) as the answer.

In order to determine if \(p_i\) can be obtained from some elements of \(S\), store for each of \(1, 2, \ldots, 2^N-1\)

\(b[i] := \) ( Can hotness \(i\) be obtained from the elements currently contained in \(S\)? true / false )

and update \(b\) in an \(O(2^N)\) time every time an element is added to \(S\).

Here, when \(m\) kinds of hotness \(a_1, a_2, \ldots, a_m\) can be obtained from \(S\), after \(x\) is added to \(S\) in the algorithm above, additional \(m+1\) kinds of hotness \(x, x \oplus a_1, x \oplus a_2, \ldots, x \oplus a_m\) is enabled, resulting in \(2m+1\) possible kinds of hotness that can be obtained from \(S \cup \lbrace x\rbrace\). Every time an element is added to \(S\), the number of kinds of hotness increases from \(m\) to \(2m+1\), so the algorithm above adds to \(S\) a spice \(N\) times.

Therefore, the problem can be solved in a total of \(\mathrm{O}(N\cdot 2^N)\) time.

The validity of the algorithm

We will show below that the algorithm described above yields the correct answer.

Let’s call a set \(S\) good if all of \(1, 2, \ldots, 2^N-1\) can be obtained from the elements of \(S\).

Suppose that we have already determined whether to add \(p_1, p_2, \ldots, p_{i-1}\) to \(S\), and now we are going to determine whether to add \(p_i\) to \(S\) or not. We will show the following two lemmas.

  1. If \(p_i\) can be obtained from the elements already contained in \(S\), then we do not have to add \(p_i\) to \(S\)
  2. If \(p_i\) cannot be obtained from the elements already contained in \(S\), then adding \(p_i\) to \(S\) does not increase the resulting cost

Proof of 1.

Assume that \(p_l\) can be obtained from some \(x_1, x_2, \ldots, x_m \in S\), that is, \(p_i = x_1 \oplus x_2 \oplus \cdots \oplus x_m\). Suppose that we added \(p_i\) to \(S\), and afterwards some of \(p_{i+1}, p_{i+2}, \ldots, p_{2^N-1}\) are added to \(S\), resulting in a good set \(\hat{S}\).

Since \(\hat{S}\) is a good set, for all \(z = 1, 2, \ldots, 2^N-1\), there exist \(y_1, y_2, \ldots, y_n \in \hat{S}\) such that \(z = y_1 \oplus y_2 \oplus \cdots \oplus y_n\). Here, even if \(y_1, y_2, \ldots, y_n\) contains \(p_i\) (without loss of generality we assume \(y_1 = p_i\)),

\[z = p_i \oplus y_2 \oplus \cdots \oplus y_n = x_1 \oplus x_2 \oplus \cdots \oplus x_m \oplus y_2 \oplus y_3 \oplus y_n,\]

so \(z\) can be obtained only from the elements of \(S \setminus \lbrace p_i \rbrace\) without using \(p_i\). Therefore, \(\hat{S} \setminus \lbrace p_i \rbrace\) is a good set too.

Hence, if we can obtain \(p_i\) from the elements already contained in \(S\), then we do not have to add \(p_i\) to \(S\).

Proof of 2.

Assume that \(p_i\) cannot be obtained from the elements of \(p_i\). Suppose that we decide not to put \(p_i\) into \(S\), and afterwards some of \(p_{i+1}, p_{i+2}, \ldots, p_{2^N-1}\) are added to \(S\), resulting in a good set \(\hat{S}\).

Since \(\hat{S}\) is a good set, there exist \(x_1, x_2, \ldots, x_m \in \hat{S}\) such that \(p_i = x_1 \oplus x_2 \oplus \cdots \oplus x_m\). Then, it holds that

\[x_1 = p_1 \oplus x_2 \oplus x_3 \oplus \cdots \oplus x_m. \]

Also, since we assume that \(p_i\) cannot be obtained from the elements of \(S\), at least one of \(x_1, x_2, \ldots, x_m\) is not contained in \(S\). Without loss of generality, we assume \(x_1 \not\in S\).

Since \(\hat{S}\) is a good set, for any \(z = 1, 2, \ldots, 2^N-1\), there exist \(y_1, y_2, \ldots, y_n \in \hat{S}\) such that \(z = y_1 \oplus y_2 \oplus \cdots \oplus y_n\). Here, even if \(x_1\) is contained in \(y_1, y_2, \ldots, y_n\) (without loss of generality we assume \(y_1 = x_1\)),

\[z = x_1 \oplus y_2 \oplus \cdots \oplus y_n = p_i \oplus x_2 \oplus \cdots \oplus x_m \oplus y_2 \oplus y_3 \oplus y_n,\]

so we can obtain \(z\) only from the elements of \((\hat{S} \cup \lbrace p_i \rbrace) \setminus \lbrace x_1 \rbrace\). Therefore, \((\hat{S} \cup \lbrace p_i \rbrace) \setminus \lbrace x_1 \rbrace\).

Also, since \(x_1 \not\in S\), \(c_{p_i} \leq c_{x_1}\), so \(C((\hat{S} \cup \lbrace p_i \rbrace) \setminus \lbrace x_1 \rbrace) \leq C(\hat{S})\).

Hence, if \(p_i\) cannot be obtained from the elements already contained in \(S\), then adding \(p_i\) to \(S\) does not increase the resulting cost.

posted:
last update: