Udostępnij za pośrednictwem

Puzzle: Xen voting algorithm

  • Artykuł

There is a huge amount of aliens living on the Xen planet who want to elect their new leader (since their previous leader died a while back). They want to switch to a very democratic voting process, through the help of a very special communication field called the “vortessence”.

One interesting property of voting through vortessence is that it can tell them whether there is a certain unique leader which is guaranteed to meet a certain percentage of votes X% (which is a number chosen ahead of time and can be considered constant in this discussion). But the vortessence cannot be used to tell who is actually the winning leader.

So these aliens will also use the help of a computer to record the voting. The rules are simple:

  1. The winner has to record at least X% votes (a unique leader is guaranteed to exist, as indicated by the vortessence)
  2. Each alien votes exactly once, by indicating the name of the proposed leader.

After the voting season, the votes are recorded in a very large unsorted log file, containing the names of the voted aliens. Now, since there are a lot of aliens, they need to use an algorithm to figure out the leader, running in O(1) in space and O(N) in time (name comparisons can be considered constant).

In what conditions is this problem solvable, and if yes, what is the minimal number of log passes?

Comments

  • The log doesn't contain timestamps.
  • The log contains votes performed only after a unique leader appears.

  • Anonymous
    November 16, 2007
    Allright - I will post the solution next week! (if there are no other comments)

  • Anonymous
    November 20, 2007
    Well, Since we already knew there is one and only one who has more votes than any others, we can find him by letting the votes "fight" each other: Picked the first one, say X1, count 1 for X1, then move on,  if X1 repeats, add count to X1. When X1 doesn't repeat, reduce the count by one, if it reaches 0, picked up the current one (say X2), and do the some counting to X2.   Keep doing this until the end. The last one left with a counting bigger than 0 is the leader: X3  X1  X1  X2  X1  X3  X3  X3  X4    ^ X3, 1 X3  X1  X1  X2  X1  X3  X3  X3  X4          ^        X3, 0 X3  X1  X1  X2  X1  X3  X3  X3  X4                ^             X1, 1 X3  X1  X1  X2  X1  X3  X3  X3  X4                      ^                    X1, 0 X3  X1  X1  X2  X1  X3  X3  X3  X4                            ^                           X1, 1 X3  X1  X1  X2  X1  X3  X3  X3  X4                                  ^                                X1, 0 X3  X1  X1  X2  X1  X3  X3  X3  X4                                        ^                                     X3, 1 X3  X1  X1  X2  X1  X3  X3  X3  X4                                              ^                                            X3, 2 X3  X1  X1  X2  X1  X3  X3  X3  X4                                                     ^                                                   X3, 1 So X3 is the winner. The condition would be the percentage X% >= 50%

  • Anonymous
    November 21, 2007
    Cool - Lailin - you got the right solution for X > 50% ! Actually the algorithm above works only if X > 50%. How about the case when X <= 50% ?

  • Anonymous
    November 26, 2007
    I think that the problem stated in one of my earlier posts is one of the most fascinating puzzles I came

  • Anonymous
    November 26, 2007
    I think that the problem stated in one of my earlier posts is one of the most fascinating puzzles I came