[UOJ 354] Voting

Difficulty Ratings

Idea Creativity: 5/5
Techniques Used: 3/5 (1/5 if excluding subtask 4)
Implementation : 2/5

Problem Link

Link (Simplified Chinese) by WuHongXun

Simplified Statement

There are $N$ people. Each person has a number on his forehead, which is either $0$ or $1$. The $N$ people's objective is to vote the xor value of the $N$ numbers correctly. Each person can see numbers on every other person's forehead, but not his own. Every person has exactly one vote. Each person knows their id.

Subtask 1

$N = 15$. Design a voting strategy such that out of 32768 situations, only less than 7000 of them would result in voting the wrong answer. Note that the people can have a different strategy than other people.

Subtask 2

Same as subtask 1, but only less than 2100 of the situation would result in wrong answer.

Subtask 3

Same as subtask 1, but this time, each person can vote $x$ times, where $0 \le x \le 10^8$. Design a strategy such that, only less than 3 of them would result in voting the wrong answer. (Equal votes counts as wrong answer)

Subtask 4

(A bit complicated). Forget about above setting. Now there are ${12}\choose{7}$ people in a circle, and there is a 01-string of length $12$. Each person can see a unique subset of size 7 of the 01-string (they know which digits they are seeing). Their objective is to vote the xor value of the 01-string. Each person can vote $x$ times, where $0 \le x \le 10^8$. Design a strategy such that out of 4096 situations, only less than 80 of them would result in voting the wrong answer.

Solution

First lets look at subtask 1. It is very easy and prevents you to get zero marks. For each person, they assume that the number on their forehead is equal to the majority of the numbers that they see, and vote the resulting xor value that they assumed. If they see exactly 7 zeroes and 7 ones, assume that the number on their forehead is 0. It is easy to see that this always return the correct answer unless there are exactly 8 ones, so the number of failures is ${15}\choose{8}$ $= 6435 \lt 7000$

Then, lets look at subtask 3. It is simple yet tricky. For each person $i$, if the number on the forehead of person $1$ to $i-1$ are all 0, then he assumes that the number on his own forehead is 1 and votes $2^{i-1}$ times. Otherwise, he just don't vote. As the result of this voting is the decision of the person with largest index who voted, we can easily see that the only failing case is when everybody's number is 0.

Lets return to subtask 2. We realise that $15=1+2+4+8$. Wow, interesting fact. Maybe we can copy subtask 3's solution into here. Group the people into 4 groups with sizes 1,2,4,8 respectively. Then we can run subtask 3. If for every previous group, its xor sum is zero, then all members of the current group assume that the group's xor sum is 1 and vote. Otherwise, half of them vote 0 and half of them vote 1, then they can cancel out each other. Then, we see that the case where this strategy fails is when the xor sum of every group is 0, which happens in $\frac{1}{16}$ of the time, so the number of failures is $32768 \div 16 = 2048 \lt 2100$.

For subtask 4, dude, i have no idea of what the solution is talking about... so sad... Link to Chinese solution (scroll to the last problem) Read it yourself :P Good luck

Comments

Did you find yourself stupid after reading the solution? Don't worry, I am as stupid as you. I only got subtask 1. I dont even have a clue on subtask 3 QAQ