次のことを考えてみてください。Mary と Larry はそれぞれ配列 M [1,..., n] と L[1,..., n] を持っています。M と L の要素はすべて異なります。Mary と Larry は、組み合わせた配列の i 次統計量を見つけることに関心があります。Mary と Larry は別の都市に住んでいるため、帯域幅に関して通信制限があります。それらは、値が {0,..., n} 内に収まる一度に 1 つの整数、または M または L 配列から取得された任意の値のいずれかを相互に送信できます。各数値送信は通信としてカウントされます。これらの制約に基づいて独自のプロトコルを定義できます。この問題の 1 つの目標は、結合された i 次統計量を計算するために必要な通信の数を最小限に抑えることです。通信回数を最小化するアルゴリズムを導出します。
i 次の統計を見つける効率的な方法を考え出すのに苦労しています。問題を再帰的に解決するために Random-Select アルゴリズムを使用しようとしましたが、通信部分が私を失望させています。どんな助けでも大歓迎です。