Hi, I'm trying to solve the problem Jeopardized Election. This was problem J in 2018 ICPC Latin America Regional Contest. No team in Latin America was able to solve it during the contest, check out the final scoreboard. I'm trying to figure out the solution but so far I can only think of the brute force approach, which is factorial and can't work. I've got a feeling that there must be a greedy strategy to solve it, but I'm not sure. It would be awesome if some of the genius minds here on Codeforces could shed some light on the solution.
Thank you very much!
Auto comment: topic has been updated by pabloskimg (previous revision, new revision, compare).
Auto comment: topic has been updated by pabloskimg (previous revision, new revision, compare).
Auto comment: topic has been updated by pabloskimg (previous revision, new revision, compare).
Auto comment: topic has been updated by pabloskimg (previous revision, new revision, compare).
This is a pretty neat problem. As you said, trying all possibilities is never going to work, so we need some observations to make the number we need to try smaller. This is a good one:
Observation: If there is an ordering such that C gets elected, then there exists an ordering such that C gets elected and C is the last one in the ordering.
Proof: Consider the ordering that gets C elected. After every candidate before C has been eliminated, C is the preferred candidate for over half of the voters, so we can move the remaining candidates before C in the ordering and none of them will ever get elected. After they are all eliminated C will be elected in the end.
This allows us to greedily construct an ordering that elects C -- put C last, then go backwards placing any candidate that would not get elected at the current position.
The only question that remains is how to find the lexicographically smallest solution, but this is pretty standard if you have an algorithm that tells you if finding an ordering is possible -- just try putting A in the first position and check if it is still possible, if that doesn't work try putting B, etc.
I don't quite understand how to do this part. If you put C last, that means you first need to remove candidates from the left side of the preference matrix until C appears in the left side in more than half of rows. Those candidates should go (and be removed) first in the ordering in order to "uncover" C. Then all other remaining candidates can go next in the ordering and finally C. So in order to generate the ordering backwards, you kind of need to simulate the whole thing forward first right? Because you need to pick ceil(R/2) rows in which you want C to appear at the left side in order to be the winner (there might be many options here, which one to choose?), which means all candidates appearing before C in these ceil(R/2) rows must be removed first, all other remaining candidates go next and finally C. So I'm not sure if any subset of ceil(R/2) rows in which you want C to appear first will work necessarily, maybe for some subsets you can't find an ordering for C but maybe with other subsets you can, I don't know.
Why do we need to worry about this? If C is last, by the time we get to C, everyone else is eliminated. So C wins in all rows.
The thing we do need to worry about is that any other candidate doesn't get selected, but if you're constructing the ordering backwards this is trivial to check (just make sure the candidates you're placing aren't first in over half of the rows).
I mean yeah, but when we simulate backwards we need to make sure our final state (C winning) is actually possible right? we need to make the moves consistent with the preference matrix, correct? So we start with C winning last, therefore the matrix must be in a state in which C appears in more than half of rows ... wait now I see it, if C is last only C appears in the matrix, so all voters prefer him and C trivially wins... Ok but then how do we avoid brute force searching the ordering of the rest of candidates backwards? Is there a greedy strategy for that too?