PROBLEM LINK:
Setter: Bogdan Ciobanu
Tester: Misha Chorniy
Editorialist: Taranpreet Singh
DIFFICULTY:
Medium
PREREQUISITES:
Linear Inequalities, Continued Fractions, Knowledge of Stern-Brocot Tree would be helpful.
PROBLEM:
Given Number of Trucks in N convoys, truck odd-numbered convoy carrying people to vote for A while others for B, we want at all times except after last truck to ensure that the number of votes to A is strictly greater than the number of votes to B. For this, we can assign truck capacities to trucks voting for A and B respectively, the Maximum capacity being bounded by C1 and C2 respectively. Either find any valid X and Y or determine if no valid pair X and Y exist for the given input.
QUICK EXPLANATION
- Let us reduce the given statement to N inequalities, All except for the last shall be of form S1*X > S2*Y translated to X/Y > P/Q where S1 is number of votes to A in prefix up to current position, while S2 is number of votes to B in prefix up to current position. Find Maximum P1/Q1 for all positions from first to last. Inequality for Truck is of form S1*X < S2*Y implying X/Y < S2/S1.
- Now, the problem is left to find a fraction P/Q such that A/B < P/Q < C/D for some fractions A/B and C/D and 1 \leq P \leq C1 and 1 \leq Q \leq C2. This can be done by representing A/B and C/D in continued fraction form to find their least common ancestor in stern Brocot Tree. If this fraction satisfies capacity requirements, this is our required answer, otherwise, no answer exists.
EXPLANATION
First of all, if N is odd, the answer is always impossible. We want Number of votes cast to A to be more than votes cast to B except after the last truck. Till second last truck, we have votes cast to A more than votes cast to B. But if N is odd, last truck people shall vote for A. This way, votes cast to B can never exceed votes cast to A, making it impossible for B to win. Hence, answer is impossible.
Suppose answer exists and is denoted by X and Y and N is even.
Let cA denotes Number of trucks containing people who’ll vote for A and CB denote the same for B.
Let us simulate the voting process. Odd numbered convoy arrive containing V[i] trucks. cA increased by B[i]. Even numbered convoy arrives, containing V[i] trucks, CB increased by V[i]. After voting by people from each truck except after last truck, we want condition cA*X > CB*Y. This gives us N-1 inequailties. Rewriting as X/Y > CB/cA for all positions from first to second last. These N-1 inequalities can be simply written as X/Y > max(cA/CB) for all positions except last. Say we call it left fraction.
For the last convoy, we want the number of votes in favor of B to be less than A, till before last truck. This means, we have another inequality cA*X > (CB-1)*Y If this fraction is greater than left, we replace left fraction by this one.
In the end, we want B to win, thus, we want cA*X < CB*Y. Rewriting it as X/Y < CB/cA. Call it the right fraction.
From the above, we get two fractions A1/B1 (left fraction) and A2/B2 (right fraction) such that X/Y should satisfy A1/B1 < X/Y < A2/B2 and also, 1 \leq X \leq C1 and 1 \leq Y \leq C2.
We can check beforehand that left fraction is smaller than the right fraction. If not, no valid solution exists.
Now, please read about Continued fractions and Stern Brocot Tree to proceed.
We want to find a fraction between these two fractions. In the Stern-Brocot tree, let us consider their paths from root to the fraction. The fraction at which the paths to both fractions diverge shall lie between two fractions. Also, That fraction shall have the minimum values of numerator and denominator possible between two fractions. So, we want to find this fraction and check capacity restrictions. If this fraction satisfies our capacity restrictions, It is our required answer, otherwise, no answer exists.
This fraction is nothing, but the fraction at the node which is LCA of nodes of both fractions except in a special case.
Click to view
In some cases, One of the fraction is the ancestor of other. In this case, since we don’t have tied allowed, we need to move one or more steps down to get the correct fraction. For example, If we want to find a fraction between 1/2 and 2/5, Required Fraction is 3/7.
Let us represent both fractions in their simple continued fraction form. This way, the LCA is given by continued fraction which has the common prefix of both fractions and last value being one more than minimum of the different values.
Consider fractions 58/75 and 57/75. We want to find a fraction with the smallest possible numerator and denominators.
Writing in continued fraction form, we have [0,1,3,2,2,2,1] and [0,1,3,5,1] respectively. The continued fraction form of required fraction shall be [0,1,3,min(2,5)+1]. The required fraction shall be generated by converting this continued fraction to normal fraction, which gives us 10/13 in this case.
There are two representations for each fraction in simple continued form. Let us use the form in which the last term is 1. The countercase for other representation given below.
Consider another example. Let the fractions be 1/2 and 2/5.
Now, these fractions are written as [0,1,1] and [0,2,1,1]. In this case, the prefix is [0,min(1,2)+1]. This is a special case because 1/2 is an ancestor of 2/5 in stern brocot tree, and thus, might cause problems in other representation.
To tackle this, we write both fractions in both forms. This way, we try to form for all 4 combinations of representations of two fractions, check fraction for all combination, and if a valid fraction is found, print it.
Time Complexity
Time complexity is O(N+log(sum(V))) per test case. log(sum(V)) for calculating continued form.
AUTHOR’S AND TESTER’S SOLUTIONS:
Setter’s solution
Tester’s solution
Editorialist’s solution
Feel free to Share your approach, If it differs. Suggestions are always welcomed. 