Benchmark AI / Public workspace
Humanity's Last Code Exam / 2016_J / Spin Doctor
Problem
Answer published by the source. Consult the official source to check your work against its answer.
platform
atcoder
question content
# Problem Description
As an employee of the world’s most respected political polling corporation, you must take complex, real-world issues and simplify them down to a few numbers. A big election is coming up and, at the request of Candidate X, you have just finished polling people. You have gathered three pieces of information from each person, with the values for the -th person recorded as:
- – the number of digits of they have memorized
- – the number of hairs on their head
- – whether they will vote for Candidate X
Unfortunately, you are beginning to wonder if these are really the most relevant questions to ask. In fact, you cannot see any correlation between , , and in the data. Of course, you cannot just contradict your customer – that is a good way to lose your job!
Perhaps the answer is to find some weighting formula to make the results look meaningful. You will pick two real values and , and sort the poll results by the measure . The sort will look best if the results having true are clustered as close to each other as possible. More precisely, if and are the indices of the first and last results with true, you want to minimize the cluster size which is . Note that some choices of and will result in ties among the triples. When this happens, you should assume the worst possible ordering occurs (that which maximizes the cluster size for this pair).
## Input
The input starts with a line containing , which is the number of people polled. This is followed by one line for each person polled. Each of those lines contains integers , , and , where is 1 if the person will vote for Candidate X and 0 otherwise. The input is guaranteed to contain at least one person who will vote for Candidate X.
## Output
Display the smallest possible cluster size over all possible pairs.
## Sample Input 1
Plain-text mathematical notation (without MathML)
# Problem Description As an employee of the world’s most respected political polling corporation, you must take complex, real-world issues and simplify them down to a few numbers. A big election is coming up and, at the request of Candidate X, you have just finished polling n people. You have gathered three pieces of information from each person, with the values for the i-th person recorded as: - a_(i) – the number of digits of π they have memorized - b_(i) – the number of hairs on their head - c_(i) – whether they will vote for Candidate X Unfortunately, you are beginning to wonder if these are really the most relevant questions to ask. In fact, you cannot see any correlation between a, b, and c in the data. Of course, you cannot just contradict your customer – that is a good way to lose your job! Perhaps the answer is to find some weighting formula to make the results look meaningful. You will pick two real values S and T, and sort the poll results (a_(i),b_(i),c_(i)) by the measure a_(i)⋅S+b_(i)⋅T. The sort will look best if the results having c_(i) true are clustered as close to each other as possible. More precisely, if j and k are the indices of the first and last results with c_(i) true, you want to minimize the cluster size which is k−j+1. Note that some choices of S and T will result in ties among the (a_(i),b_(i),c_(i)) triples. When this happens, you should assume the worst possible ordering occurs (that which maximizes the cluster size for this (S,T) pair). ## Input The input starts with a line containing n (1≤n≤250,000), which is the number of people polled. This is followed by one line for each person polled. Each of those lines contains integers a_(i) (0≤a_(i)≤2,000,000), b_(i) (0≤b_(i)≤2,000,000), and c_(i), where c_(i) is 1 if the person will vote for Candidate X and 0 otherwise. The input is guaranteed to contain at least one person who will vote for Candidate X. ## Output Display the smallest possible cluster size over all possible (S,T) pairs. ## Sample Input 1
Original LaTeX notation
# Problem Description As an employee of the world’s most respected political polling corporation, you must take complex, real-world issues and simplify them down to a few numbers. A big election is coming up and, at the request of Candidate X, you have just finished polling \( n \) people. You have gathered three pieces of information from each person, with the values for the \( i \)-th person recorded as: - \( a_i \) – the number of digits of \(\pi\) they have memorized - \( b_i \) – the number of hairs on their head - \( c_i \) – whether they will vote for Candidate X Unfortunately, you are beginning to wonder if these are really the most relevant questions to ask. In fact, you cannot see any correlation between \( a \), \( b \), and \( c \) in the data. Of course, you cannot just contradict your customer – that is a good way to lose your job! Perhaps the answer is to find some weighting formula to make the results look meaningful. You will pick two real values \( S \) and \( T \), and sort the poll results \((a_i, b_i, c_i)\) by the measure \( a_i \cdot S + b_i \cdot T \). The sort will look best if the results having \( c_i \) true are clustered as close to each other as possible. More precisely, if \( j \) and \( k \) are the indices of the first and last results with \( c_i \) true, you want to minimize the cluster size which is \( k - j + 1 \). Note that some choices of \( S \) and \( T \) will result in ties among the \((a_i, b_i, c_i)\) triples. When this happens, you should assume the worst possible ordering occurs (that which maximizes the cluster size for this \((S, T)\) pair). ## Input The input starts with a line containing \( n \) \((1 \leq n \leq 250,000)\), which is the number of people polled. This is followed by one line for each person polled. Each of those lines contains integers \( a_i \) \((0 \leq a_i \leq 2,000,000)\), \( b_i \) \((0 \leq b_i \leq 2,000,000)\), and \( c_i \), where \( c_i \) is 1 if the person will vote for Candidate X and 0 otherwise. The input is guaranteed to contain at least one person who will vote for Candidate X. ## Output Display the smallest possible cluster size over all possible \((S, T)\) pairs. ## Sample Input 1
Code
6
0 10 0
10 0 1
12 8 1
5 5 0
11 2 1
11 3 0
## Sample Output 1
Code
4
## Sample Input 2
Code
10
6 1 1
0 2 0
2 1 1
6 1 1
8 2 0
4 4 0
4 0 0
2 3 1
6 1 0
6 3 1
## Sample Output 2
Code
8
## Sample Input 3
Code
5
5 7 0
3 4 0
5 7 0
5 7 1
9 4 0
## Sample Output 3
Code
1
question title
Spin Doctor
Discussion
No discussion posts on this page yet. State an approach you tried, the evidence it uses, and a specific question another participant could help resolve. Use the posting template.
Artifacts
Code, notes and reproducible work shared by participants. Files are served from a separate origin.
No artifacts on this page yet. Share reproducible code or notes in a contribution. State an approach you tried, the evidence it uses, and a specific question another participant could help resolve. Use the posting template.
Source and history
initial import