Hide

Problem L
Adding Up the Votes

/problems/addingupthevotes/file/statement/en/img-0001.jpg
Not super-parallel vote counting
Author: Santwybe, CC BY 3.0 license
2022 is an exciting year! The end of the COVID-19 pandemic is inching ever closer, the Swedish Coding Cup celebrates its 5-year anniversary, and it’s election year in Sweden.

That last point is of particular interest, because computer science researchers at KTH Royal Institute of Technology, the host of the SCC 2021-2022 finals, have been studying how to count votes as quickly as possible. Given a series of votes, it’s easy to determine if any of the candidates has won a majority of votes in linear time: you just count the votes one at a time and keep a tally for each candidate. Of course, centralized single-processor algorithms are so 2021. In these modern times, an algorithm is barely of interest unless it can be parallelized to more than a thousand processors.

Your task is to determine if there is a candidate that received a strict majority of the votes in an election that $N$ citizens participated in, and if so, who. At your disposal is a super-parallel processor that can perform the following operation almost instantly. Let, for each $i$ where $1 \le i \le N$, $c_ i$ be the candidate that the $i$’th citizen cast their vote for. You can provide a sequence of integers $a_1, a_2, \dots , a_ N$ ($1 \le a_ i \le N$) and the processor will tell you whether $c_ i = c_{a_ i}$ for each $1 \le i \le N$. Your score for the problem depends on how many times you use the processor (see the Scoring sections for the details).

Interactivity

This problem is interactive; you will communicate with the grader through reading from standard in and writing to standard out. First, the grader will write a single line containing the integer $T$ ($1 \le T \le 10\, 000$), the number of times your program should count votes.

At the start of each vote counting, the grader will write a single line containing the integer $N$ ($1 \le N \le 100\, 000$), the number of citizens that participated in the election.

Next, you may use the super-parallel processor a number of times. For each use, output a single line ? a_1 a_2 ... a_N where $a_1, \dots , a_ N$ are integers between $1$ and $N$. The grader will then output a line containing a string consisting of $N$ characters 0 or 1. The $i$’th of these is $1$ if $c_ i = c_{a_ i}$ and $0$ otherwise.

Finally, you must output a single line of the form ! X where $X$ is such that candidate $c_ X$ received strictly more than half of the votes, i.e. $c_ X = c_ i$ for strictly more than half of all $1 \le i \le N$. If no such $X$ exists, you should instead output ! -1.

After this, your program should continue with the next vote counting. If this was the $T$’th vote count, your program must instead immediately exit.

The sum of all $N$ over all test cases will not exceed $100\, 000$.

It is guaranteed that the votes for each test case are fixed ahead of time and do not change adaptively in response to your queries.

Scoring

Your solution will be tested on a set of test cases. If any test case is answered incorrectly, your solution will graded as incorrect. Otherwise, let $Q$ denote the maximum number of times your program used the super-parallel processor for any vote counting. Depending on $Q$ your solution will be awarded different number of points:

Condition

Points

$19 < Q$

$0$ (judged as Wrong Answer)

$10 \le Q \le 18$

$20 + (18 - Q) \cdot 2$

$6 \le Q \le 9$

$40 + (9 - Q) \cdot 7$

$Q = 5$

$80$

$Q = 4$

$100$

$Q \le 3$

$115$

Read Sample Interaction 1 Write
 2
 5
 ? 2 1 4 5 3
 11000
 ? 1 1 1 1 1
 11010
 ! 4
 4
 ? 2 3 4 1
 1010
 ! -1

Please log in to submit a solution to this problem

Log in