Is anyone else with an automatic berth unable to register? I know JoeyWheeler and I got automatic berth and can't register but gongy qualified through round 1C and successfully registered...
Basic observations: 1. First of all just look at the exponenets, so we have n pairs of integers, and we can replace two pairs by its max, or min. 2. WLOG our goal is to get (0, 0). // by subtracting goal
Then we divide points in four categories x-axis, y-axis, center, the rest. Now:
If we have ≥ 2 centers then OK
If we have 1 center and sth on some axis then OK
If we have 1 center and maximum of all points in the rest has x, y > 0 or minimum of all points in the rest has x, y < 0 then OK.
If we have sth positive on both axis, or sth negative on both axis then OK
If all points on x-axis are positive, and all pts on y-axis are negative, and we have soem point in the rest with x < 0 and y > 0 then OK.
If all points on y-axis are positive, and all pts on x-axis are negative, and we have soem point in the rest with y < 0 and x > 0 then OK.
Can you or someone else give more intuition of these cases? How do we go from these properties to the existence of a series of moves that guarantee hitting the target?
Suppose that there is no pts in the center. First of all we have to have sth on both axis — which is clear.
The last move should be min on (+,0) and (0,+) or max on (-,0) and (0,-).
Suppose that there are points of the form P1 = (0, + ) and P2 = ( + , 0). Then replace all the rest by one point in any way, say Q = (a, b). Depending on where the Q is we can either remove Q (i.e. min(P1, Q) = P1 or etc.) or project Q on some axis (i.e. min(P1, Q) = (0, b) etc. ) to obtain two pts of the form (0, + ) and ( + , 0). And we use min on them.
In the same way we can treat the case P1 = (0, - ) and P2 = ( - , 0). (Because there is the symmetry : (x, y) – > ( - x, - y) which swaps min and max).
The remaining case is: all pts on x-axis are (+,0), and all pts on y-axis are (0,-). When we have some point of the form (-,+) then we can in first move use max((0,-),(-,+)) = (0,+). And use the previous case. So suppose that we have no pts of the form (-,+). So the upper left quarter of plane is empty. Observe that using moves we cannot get into this quarter so it is impossible to get (0,0) (which lies on the boundary of that quarter).
Ok. Now the center can be treated as point on x-axis or y-axis. Using the same arguments we can consider the cases with center too.
I had dp/backtrack with memoization, complexity about O(39) but I don't have a proof that it works. There are 9 groups of elements and I assumed that in each group we don't need more than 2 elements. So, each group contains 0, 1 or 2 elements.
Iterate over all subsets of three numbers. First do gcd operation for all numbers not in the subset, then iterate over all operation sequences for the remaining three operations. If you do not find answer this way, then its Impossible.
First, there are 9 types of numbers 2^(<a,=a,>a) * 3^(<b,=b,>b). I labeled these numbers below:
|
1 2 3
|
--4--5--6--
|
7 8 9
|
For instance 1 is 2^(<a) * 3^(>b), 2 is 2^(=a),3^(>b), 9 is 2^(>a), 3^(<b)
The lcm/gcd can be intepreted as taking two points
x.
.x
and replacing with one of
.x
x.
Or, if we have
.x
x.
We can delete one of the points.
More concretely, we can make rules like (2 and 6) can become 5 or 3. Or (6 and 3) can become 6 or 3. And so on for all 9^2 pairs of input.
Now, for the actual solution. We need (2 or 5 or 8) and (4 or 5 or 6) to be able to reach the target.
For always possible cases:
If we have 2 and 6 we can reach the goal (symmetrically 4 and 8). If we have any 1s or 4s can use the 2 to delete these (symmetrically 8s and 9s get deleted by 6). Then, we can go from (2 and 6) -> 5. The remaining 3s and 7s can be deleted by the 5.
If we have a 5 and one other number on either axis, we can combine 1,3,7,9 with something on the axis to remain on the axis, until we're left with 5 and one other number on the axis. We delete the other number to be left with a 5.
For other cases:
If we have a single 5 and nothing on either axis. It's possible if we have a 3 or 7 or both (1 and 9). First a (1 and 9) can combine to a 3 or 7, so assume we have at least one 3 or 7. We can combine use a 3 or 7 to delete any remaining 1s or 9s. Finally, we can delete any remaining 3s and 7s with the 5.
2 and 4 (symmetrically 6 and 8) If we have a 9, we can combine (4 and 9) -> 6. Then, we have 2 and 6 and we're done.
Thus, only cases we haven't covered are
5 and all 1s or all 9s
no 5,6,8,9 (symmetrically no 1,2,4,5) We can check by inspection that these are impossible.
Is anyone else with an automatic berth unable to register? I know JoeyWheeler and I got automatic berth and can't register but gongy qualified through round 1C and successfully registered...
How to solve A ? Exponential dp on power of 3 s or something?
Cases.
Basic observations: 1. First of all just look at the exponenets, so we have n pairs of integers, and we can replace two pairs by its max, or min. 2. WLOG our goal is to get (0, 0). // by subtracting goal
Then we divide points in four categories x-axis, y-axis, center, the rest. Now:
If we have ≥ 2 centers then OK
If we have 1 center and sth on some axis then OK
If we have 1 center and maximum of all points in the rest has x, y > 0 or minimum of all points in the rest has x, y < 0 then OK.
If we have sth positive on both axis, or sth negative on both axis then OK
If all points on x-axis are positive, and all pts on y-axis are negative, and we have soem point in the rest with x < 0 and y > 0 then OK.
If all points on y-axis are positive, and all pts on x-axis are negative, and we have soem point in the rest with y < 0 and x > 0 then OK.
In other cases Impossible.
Can you or someone else give more intuition of these cases? How do we go from these properties to the existence of a series of moves that guarantee hitting the target?
Suppose that there is no pts in the center. First of all we have to have sth on both axis — which is clear.
The last move should be min on (+,0) and (0,+) or max on (-,0) and (0,-).
Suppose that there are points of the form P1 = (0, + ) and P2 = ( + , 0). Then replace all the rest by one point in any way, say Q = (a, b). Depending on where the Q is we can either remove Q (i.e. min(P1, Q) = P1 or etc.) or project Q on some axis (i.e. min(P1, Q) = (0, b) etc. )
to obtain two pts of the form (0, + ) and ( + , 0). And we use min on them.
In the same way we can treat the case P1 = (0, - ) and P2 = ( - , 0). (Because there is the symmetry : (x, y) – > ( - x, - y) which swaps min and max).
The remaining case is: all pts on x-axis are (+,0), and all pts on y-axis are (0,-).
When we have some point of the form (-,+) then we can in first move use max((0,-),(-,+)) = (0,+). And use the previous case. So suppose that we have no pts of the form (-,+). So the upper left quarter of plane is empty. Observe that using moves we cannot get into this quarter so it is impossible to get (0,0) (which lies on the boundary of that quarter).
Ok. Now the center can be treated as point on x-axis or y-axis. Using the same arguments we can consider the cases with center too.
I had dp/backtrack with memoization, complexity about O(39) but I don't have a proof that it works. There are 9 groups of elements and I assumed that in each group we don't need more than 2 elements. So, each group contains 0, 1 or 2 elements.
Iterate over all subsets of three numbers. First do gcd operation for all numbers not in the subset, then iterate over all operation sequences for the remaining three operations. If you do not find answer this way, then its Impossible.
Here's a proof I had for casework:
First, there are 9 types of numbers 2^(<a,=a,>a) * 3^(<b,=b,>b). I labeled these numbers below:
For instance 1 is 2^(<a) * 3^(>b), 2 is 2^(=a),3^(>b), 9 is 2^(>a), 3^(<b)
The lcm/gcd can be intepreted as taking two points
and replacing with one of
Or, if we have
We can delete one of the points.
More concretely, we can make rules like (2 and 6) can become 5 or 3. Or (6 and 3) can become 6 or 3. And so on for all 9^2 pairs of input.
Now, for the actual solution. We need (2 or 5 or 8) and (4 or 5 or 6) to be able to reach the target.
For always possible cases:
For other cases:
Thus, only cases we haven't covered are