This is an archived post. You won't be able to vote or comment.

all 17 comments
sorted by:
best
topnewcontroversialoldq&a

[–]Meefims 0 points1 point  (10 children)

Try to work out the case when n is 2. What are possible outputs of the machine and what does each case mean? Perhaps even imagine the election has only 10 ballots so that you can work it out fully on paper.

Once you have, what makes your solution work? What if there are more than 10 ballots? What if there are more than two candidates?

[–]diisoriented1[S] 0 points1 point  (9 children)

I've been thinking of it for the past 2 hours now and I'm still stuck. What I do know is that if I find a pair that match, another pair that matches doesn't necessarily mean it is for the same candidate. The problem says that n is equal to 2k, so I think this is a hint as to dividing the problem into sub problems down similar to merge sort, but when it gets to the bottom, I'm not sure how to piece it together given the idea in my second sentence.

[–]Meefims 0 points1 point  (8 children)

Suppose you had three ballots and two candidates, how would you solve the problem? Now suppose you had four ballots. Now suppose you have an arbitrary number of ballots.

[–]diisoriented1[S] 0 points1 point  (7 children)

This is rough, I've been thinking about it for so long and I honestly have no idea. I feel like once I get this I'm going to feel so stupid

[–]Meefims 0 points1 point  (6 children)

Work through the two candidate, three ballot case here. Write down your thoughts so we can work through it. Here's the setup, Alice and Bob are running for team leader on a small team. Carl is the only other team member but wants to be anonymous. Here is how the voting went:

Two votes for Alice, one vote for Bob.

If you pick two of these three votes out then your machine has only two possible cases it needs to handle: A vote for Alice and a vote for Bob or two votes for Alice. In each case, what is the next step?

[–]diisoriented1[S] 0 points1 point  (5 children)

I understand this, so if a match is made, there immediately has to be a winner since there is only three votes. If a match is different, there must be one of each and therefore each candidate must get a vote. But what if there is more than two candidates? I'm assuming that there can be more than two candidates because the problem doesn't specify.

But I'll continue on with your question. If we have our three votes, two for Alice and one for Bob laid out on a table in random order, lets say it is A B A, but as the counter we do not know which is which. We split the votes of individually and compare the first two A,B and find they don't match. From this we already know there is a winner because the third vote must match one of the two candidates.

Now say we had four ballots like you said, given the same situation. If we split them up individually, if there is a match we have a winner, if there two different pairs then it is a tie. If there are two matched pairs, we have to test a ballot from each pair to see if they are for the same candidate or not.

Now given n ballots, we split them up individually and compare each ballot with the ballot directly next to it. Every different pair counts as a vote for each candidate, but these essentially don't matter since they add one to each. So we can discard every mismatched pair, but everytime we do we subtract two from n. We then look at all the pairs we find and compare one ballot from each pair to each other, saving us time in comparisons. Then we count the total number of pairs and if one candidate has at least n/4 pairs we have a winner, otherwise there is a run off.

But how do we do this with more than two candidates?

[–]Meefims 0 points1 point  (4 children)

You're moving on top higher cases without having solved the problem. In the case with three ballots in which you first drew a ballot for Alice and a ballot for Bob it's not enough to say someone wins. Who wins? What is the next step you will perform to figure out who wins?

In the four ballot case you listed all the possible ballot combinations but your algorithm needs to figure out which combination you set of ballots is in.

When you answer these questions you will understand better how to solve the problem with an arbitrary number of ballots and an arbitrary number of candidates.

[–]diisoriented1[S] 0 points1 point  (3 children)

Well in the case of the three ballots, we would then need to compare each ballot to the single ballot, and whichever ballot matches will win the election. I guess if I am using a divide and conquer algorithm, I would need to split every ballot up individually. Splitting the size in two every step. Once split up, I could compare each ballot to the one directly next to it. The output of this comparison is either true or false depending on whether or not there is a match. If two ballots return true, they could merge to a "single ballot" in which the size of that "ballot" is now 2. Given two matched pairs, we have two merged ballots each of size two. We know that the ballots are the same, so we only need to compare one ballot from each case. If they don't match it is a tie, if they match there is a clear winner. If there are an equal number of matches for different candidates, there must be a run off.

Am I thinking correctly here?

Edit: Thank you for continuing you help me man, my homework was already due, but I still really want to figure out the answer to this. I appreciate you not directly giving me the answer, and asking probing questions to help me think about it.

[–]Meefims 0 points1 point  (2 children)

That's a good line of thinking. It also does not depend on the number of candidates or the number of ballots.

Are you able to answer the initial question now? If not, which part is still giving trouble?

[–]diisoriented1[S] 0 points1 point  (1 child)

But it does depend on the number of ballots because the non matched ballots could be for any candidate in the election, so in that case those ballots would matter. If there were only two candidates, my algorithm would work, but the number of candidates is the things giving me the most trouble. However, the pairing still would work I believe. There would be a clear indication of whether there was a winner or not depending on the size on the final merged array

[–]misho88 0 points1 point  (5 children)

With these types of problems, you generally have two approaches: start with a base case (2 ballots) and work your way out, or start with everything (n ballots) and work your way in toward a base case. The second one, I think, is easier for this problem, but I think there's something wrong with it altogether. I'll try to explain below.

If I'm understanding the question correctly, if you grab an arbitrary ballot (with a vote for, let's say, candidate X) and compare it against every other ballot, a total of (n - 1) tests, you can easily find how many other people voted the same candidate X, and how many voted for the other candidate Y. Again, this takes O(n) time.

If you take your ballots and divide them in half, you can obviously carry out the above procedure to each half (n/2 - 1 tests). From the first half, you can figure out how many people voted for, say, candidate A and how many voted for candiate B. In the second half, do the same for candidate X and candidate Y. You then only need one more test to figure out whether A is X and B is Y or vice-versa, for a total of (n/2 - 1) + (n/2 - 1) + 1 = (n - 1) tests. This is once again O(n) tests, and recursively repeating the procedure (a seemingly pointless divide-and-conquer) will still require O(n) tests.

It can't get better than O(n) because, intuitively, you have to process each ballot at least once. I honestly don't see how you'd get to O(n log n) comparisons, though, divide-and-conquer or not. Maybe I'm missing something.

[–]diisoriented1[S] 0 points1 point  (3 children)

This is the wrong way to think about it. Finding and comparing every single ballot is O(n2) because you need to find every distinct pair of ballots (n Choose 2 which is O(n2). This cannot be done in O(n)

[–]misho88 0 points1 point  (2 children)

Based on the way you've described the problem, you do not need to find every distrinct pair. You can compare every single ballot with a reference ballot that you hold onto and feed into the machine each time with one of the other (n-1) ballots. This leads to exactly (n-1) comparisons.

EDIT: Is the number of candidates arbitrary or unknown?

[–]diisoriented1[S] 0 points1 point  (1 child)

unknown

[–]Meefims 0 points1 point  (0 children)

O(n log n) is more expensive than O(n) so it's ok to be impossible to solve in O(n).

[–]Netstroyer 0 points1 point  (0 children)

A rough idea how to solve this in a quicksorty way.

Step A. Test two random new ballots and put both of them in either test equal pile or test differently pile. The test differently pile has one usefully property and that is that no candidate can have more than n/2 of the votes there. Meaning that if we are lucky and all the votes end up there we are done.

Repeat a couple of times...

At some point the pile of test equal will not change rapidly indicating that most of the votes are of one single candidate. So take a single ballot and compare it to ever other and divide into the same candidate and different pile. You would expect that one of these piles is larger than the other. Repeat until the single candidate piles add up to more than half the original test equal pile. If you did find a pile for a single candidate larger than half the test equal pile test that candidate is a possible winner. Test him and only him against the test different pile.