Efficient divide-and-conquer algorithm

Question

At a political event, introducing 2 people determines if they represent the same party or not. Suppose more than half of the n attendees represent the same party. I'm trying to find an efficient algorithm that will identify the representatives of this party using as few introductions as possible.

A brute force solution will be to maintain two pointers over the array of attendees, introducing n attendees to n-1 other attendees in O(n²) time. I can't figure out how to improve on this.

Edit: Formally,

You are given an integer n. There is a hidden array A of size n, such that more than half of the values in A are the same. This array represents the party affiliation of each person.

You are allowed queries of the form introduce(i, j), where i≠j, and 1 <= i, j <= n, and you will get a boolean value in return: You will get back 1, if A[i] = A[j], and 0 otherwise.

Output: B ⊆ [1, 2. ... n] where |B| > n/2 and the A-value of every element in B is the same.

Hopefully this explains the problem better.

I didn't fully understand the question, but is disjoint-set what you need? — con ko
– con ko, Commented Apr 5, 2020 at 2:44
I don't think so - I have edited the post to try to explain the problem more clearly. — bollock1
– bollock1, Commented Apr 5, 2020 at 4:15
Just do a first pass of Quicksort in O(n), that's sufficient to divide an array into two sets that aren't equal in size. — Patrick Roberts
– Patrick Roberts, Commented Apr 5, 2020 at 4:28
It even makes me more puzzled. It sounds like you only needs to store a something like hash map and implement this in O(n) time, you even don't need quick sort — con ko
– con ko, Commented Apr 5, 2020 at 4:33
@PatrickRoberts Why is quicksort O(n)? Quicksort is not a linear algorithm. — con ko
– con ko, Commented Apr 5, 2020 at 4:34

CodeChef · Accepted Answer · 2020-04-05 14:43:06Z

2

This can be done in O(n) introductions using the Boyer–Moore majority vote algorithm.

Consider some arbitrary ordering of the attendees: A_1, A_2, ..., A_n. In the algorithm, you maintain a 'stored element', denoted by m. Whenever the algorithm wants to check if the current element (x) is same as the stored element or not, you introduce those two people and increment or decrement the counter accordingly. The stored element at the end will be a member of the majority party. Then, you can do another pass over all the other n - 1 people, and introduce each of them to this known person and hence find all the members of the majority party.

Thus, the total number of introductions is O(n).

answered Apr 5, 2020 at 14:43

CodeChef

1759 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Efficient divide-and-conquer algorithm

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related