algorithm - n 枚の硬貨が与えられたとき、重たい硬貨の数を求めますか?

Question

n 枚の硬貨が与えられ、そのうちのいくつかはより重いものであり、O(log^2 n) の重み付けを使用して重い硬貨の数を見つけるためのアルゴリズム。すべての重いコインは同じ重量を持ち、すべての軽いコインも同じ重量を共有することに注意してください。

互いに素な 2 つのコインのサブセットの重量を比較できるバランスが与えられます。バランスは、どちらのサブセットが重いか、またはそれらの重みが等しいかどうかのみを示しており、絶対的な重みは示していないことに注意してください。

Answer 1

答えのすべてを明かすつもりはありませんが、分解するのを手伝ってあげましょう。

1. 1 枚の重いコインを見つけるO(log(n))アルゴリズムを見つけます。
2. O(log(n))セットを 2 つのセットに分割し、同数の重いカウントと軽いカウントに最大 2 つの残り物 (それぞれの量が偶数でない場合) を加えたものを見つけるアルゴリズムを見つけてください。
3. アルゴリズム #1 と #2 を組み合わせます。

ヒント：

• アルゴリズム #1 は、アルゴリズム #2 から独立しています。
• O(log(n))二分探索のヒント
• O(log^2(n))どうすれば2 つのO(log(n))アルゴリズムで終わる可能性がありますか?